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 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 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.