java.lang.Object
All Implemented Interfaces:
`IntegerCostOptimizationProblem<Permutation>`, `Problem<Permutation>`

public final class QuadraticAssignmentProblem extends Object implements IntegerCostOptimizationProblem<Permutation>
This class is an implementation of the Quadratic Assignment Problem (QAP), an NP-Hard optimization problem. In this implementation, both the cost and distance matrices are integer-valued. This class uses factory methods, rather than constructors to better support a variety of ways of generating random instances. The class supports generating uniform random instances via the `createUniformRandomInstance` method, as well as creating instances by directly specifying the cost and distance matrices via the `createInstance`.
• ## Method Summary

Modifier and Type
Method
Description
`int`
`cost(Permutation candidate)`
Computes the cost of a candidate solution to the problem instance.
`static QuadraticAssignmentProblem`
```createInstance(int[][] cost, int[][] distance)```
Creates an instance of the QAP problem from given cost and distance matrices.
`static QuadraticAssignmentProblem`
```createUniformRandomInstance(int size, int minCost, int maxCost, int minDistance, int maxDistance)```
Creates an instance of the QAP problem with cost and distance matrices formed from uniformly random integers.
`static QuadraticAssignmentProblem`
```createUniformRandomInstance(int size, int minCost, int maxCost, int minDistance, int maxDistance, long seed)```
Creates an instance of the QAP problem with cost and distance matrices formed from uniformly random integers.
`int`
```getCost(int i, int j)```
Gets an element of the cost matrix.
`int`
```getDistance(int i, int j)```
Gets an element of the distance matrix.
`int`
`minCost()`
A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.
`int`
`size()`
Gets the size of the instance.
`int`
`value(Permutation candidate)`
Computes the value of the candidate solution within the usual constraints and interpretation of the problem.

### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

### Methods inherited from interface org.cicirello.search.problems.IntegerCostOptimizationProblem

`costAsDouble, getSolutionCostPair, isMinCost`
• ## Method Details

• ### cost

public int cost(Permutation candidate)
Description copied from interface: `IntegerCostOptimizationProblem`
Computes the cost of a candidate solution to the problem instance. The lower the cost, the more optimal the candidate solution.
Specified by:
`cost` in interface `IntegerCostOptimizationProblem<Permutation>`
Parameters:
`candidate` - The candidate solution to evaluate.
Returns:
The cost of the candidate solution. Lower cost means better solution.
• ### value

public int value(Permutation candidate)
Description copied from interface: `IntegerCostOptimizationProblem`
Computes the value of the candidate solution within the usual constraints and interpretation of the problem.
Specified by:
`value` in interface `IntegerCostOptimizationProblem<Permutation>`
Parameters:
`candidate` - The candidate solution to evaluate.
Returns:
The actual optimization value of the candidate solution.
• ### minCost

public int minCost()
Description copied from interface: `IntegerCostOptimizationProblem`
A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution. The default implementation returns Integer.MIN_VALUE.
Specified by:
`minCost` in interface `IntegerCostOptimizationProblem<Permutation>`
Returns:
A lower bound on the minimum theoretical cost of the problem instance.
• ### size

public int size()
Gets the size of the instance.
Returns:
the size of the instance.
• ### getCost

public int getCost(int i, int j)
Gets an element of the cost matrix.
Parameters:
`i` - The row index.
`j` - The column index.
Returns:
The cost of cell i, j.
Throws:
`IndexOutOfBoundsException` - if either i or j is less than 0, or if either i or j is greater than or equal to size().
• ### getDistance

public int getDistance(int i, int j)
Gets an element of the distance matrix.
Parameters:
`i` - The row index.
`j` - The column index.
Returns:
The distance of cell i, j.
Throws:
`IndexOutOfBoundsException` - if either i or j is less than 0, or if either i or j is greater than or equal to size().
• ### createInstance

public static QuadraticAssignmentProblem createInstance(int[][] cost, int[][] distance)
Creates an instance of the QAP problem from given cost and distance matrices. Note that the `cost` and `value` methods assume that the diagonal is always 0.
Parameters:
`cost` - The cost matrix which must be square.
`distance` - The distance matrix which must be square and of the same dimensions as the cost matrix.
Returns:
an instance of the QAP problem from the specified cost and distance matrices
Throws:
`IllegalArgumentException` - if the cost and distance matrices are not square or not of the same dimensions
• ### createUniformRandomInstance

public static QuadraticAssignmentProblem createUniformRandomInstance(int size, int minCost, int maxCost, int minDistance, int maxDistance)
Creates an instance of the QAP problem with cost and distance matrices formed from uniformly random integers. Note that the diagonal is always 0.
Parameters:
`size` - Create a size by size instance.
`minCost` - Costs are uniform at random from an interval with minCost as the minimum.
`maxCost` - Costs are uniform at random from an interval with maxCost as the maximum.
`minDistance` - Distances are uniform at random from an interval with minDistance as the minimum.
`maxDistance` - Distances are uniform at random from an interval with maxDistance as the maximum.
Returns:
an instance of the QAP problem with uniform random cost and distance matrices
Throws:
`IllegalArgumentException` - if size is less than 1, or maxCost is less than minCost, or maxDistance is less than minDistance.
• ### createUniformRandomInstance

public static QuadraticAssignmentProblem createUniformRandomInstance(int size, int minCost, int maxCost, int minDistance, int maxDistance, long seed)
Creates an instance of the QAP problem with cost and distance matrices formed from uniformly random integers. Note that the diagonal is always 0.
Parameters:
`size` - Create a size by size instance.
`minCost` - Costs are uniform at random from an interval with minCost as the minimum.
`maxCost` - Costs are uniform at random from an interval with maxCost as the maximum.
`minDistance` - Distances are uniform at random from an interval with minDistance as the minimum.
`maxDistance` - Distances are uniform at random from an interval with maxDistance as the maximum.
`seed` - The seed for the random number generator.
Returns:
an instance of the QAP problem with uniform random cost and distance matrices
Throws:
`IllegalArgumentException` - if size is less than 1, or maxCost is less than minCost, or maxDistance is less than minDistance.