Module org.cicirello.chips_n_salsa
Package org.cicirello.search.problems
Class QuadraticAssignmentProblem
java.lang.Object
org.cicirello.search.problems.QuadraticAssignmentProblem
 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 NPHard
optimization problem. In this implementation, both the cost and distance matrices are
integervalued. 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 TypeMethodDescriptionint
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
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 interfaceIntegerCostOptimizationProblem<Permutation>
 Parameters:
candidate
 The candidate solution to evaluate. Returns:
 The cost of the candidate solution. Lower cost means better solution.

value
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 interfaceIntegerCostOptimizationProblem<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 interfaceIntegerCostOptimizationProblem<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
Creates an instance of the QAP problem from given cost and distance matrices. Note that thecost
andvalue
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.
