Module org.cicirello.chips_n_salsa
Package org.cicirello.search.problems.tsp

Class RandomTSPMatrix.Integer

java.lang.Object
org.cicirello.search.problems.tsp.BaseTSP
org.cicirello.search.problems.tsp.RandomTSPMatrix
org.cicirello.search.problems.tsp.RandomTSPMatrix.Integer
All Implemented Interfaces:
IntegerCostOptimizationProblem<Permutation>, Problem<Permutation>
Enclosing class:
RandomTSPMatrix
public static final class RandomTSPMatrix.Integer extends RandomTSPMatrix implements IntegerCostOptimizationProblem<Permutation>
This class implements the Traveling Salesperson Problem (TSP), and its variant, the Asymmetric Traveling Salesperson Problem (ATSP), by generating a random distance matrix, with integer cost edges. It supports both the TSP and ATSP, and also provides the option to control whether or not the distance matrix satisfies the triangle inequality.

The random distance matrix is generated via an approach based on that of the paper: Cirasella J., Johnson D.S., McGeoch L.A., Zhang W. (2001) The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests. In Algorithm Engineering and Experimentation (ALENEX 2001). There are some minor differences between the approach described in that paper and the approach of this class. This class generates random distances with a minimum of 1, whereas the approach described in that paper allows distances of 0.

  • Nested Class Summary

    Nested classes/interfaces inherited from class org.cicirello.search.problems.tsp.RandomTSPMatrix

    RandomTSPMatrix.Double, RandomTSPMatrix.Integer

  • Constructor Summary

    Constructors
    Constructor
    Description
    Integer(int[][] distance)
    Although the focus of this class is generating random TSP and ATSP instances, this constructor enables specifying the distance matrix directly.
    Integer(int n, int maxDistance)
    Generates a random instance of either the TSP.
    Integer(int n, int maxDistance, boolean symmetric)
    Generates a random instance of either the TSP or ATSP.
    Integer(int n, int maxDistance, boolean symmetric, boolean triangleInequality)
    Generates a random instance of either the TSP or ATSP.
    Integer(int n, int maxDistance, boolean symmetric, boolean triangleInequality, long seed)
    Generates a random instance of either the TSP or ATSP.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    cost(Permutation candidate)
    Computes the cost of a candidate solution to the problem instance.
    final int
    getDistance(int i, int j)
    Gets the distance (i.e., cost) of an edge.
    final int
    length()
    Gets the number of cities in the TSP instance.
    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
    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

  • Constructor Details

    • Integer

      public Integer(int n, int maxDistance)
      Generates a random instance of either the TSP. The instances generated by this constructor may not satisfy the triangle inequality. If you desire an instance that satisfies the triangle inequality, see the other constructors. The distance matrix generated by this constructor is symmetric. See the other constructors for the ATSP.
      Parameters:
      n - The number of cities.
      maxDistance - The maximum distance between cities. The edge costs between pairs of cities are uniform in the interval [1, maxDistance].
      Throws:
      IllegalArgumentException - if n < 2.
      IllegalArgumentException - if maxDistance < 1.

    • Integer

      public Integer(int n, int maxDistance, boolean symmetric)
      Generates a random instance of either the TSP or ATSP. The instances generated by this constructor may not satisfy the triangle inequality. If you desire an instance that satisfies the triangle inequality, see the other constructors.
      Parameters:
      n - The number of cities.
      maxDistance - The maximum distance between cities. The edge costs between pairs of cities are uniform in the interval [1, maxDistance].
      symmetric - Pass true for the TSP, or false for the ATSP.
      Throws:
      IllegalArgumentException - if n < 2.
      IllegalArgumentException - if maxDistance < 1.

    • Integer

      public Integer(int n, int maxDistance, boolean symmetric, boolean triangleInequality)
      Generates a random instance of either the TSP or ATSP.
      Parameters:
      n - The number of cities.
      maxDistance - The maximum distance between cities. The edge costs between pairs of cities are uniform in the interval [1, maxDistance].
      symmetric - Pass true for the TSP, or false for the ATSP.
      triangleInequality - Pass true if you want the generated distance matrix to respect the triangle inequality, or false for purely random distances.
      Throws:
      IllegalArgumentException - if n < 2.
      IllegalArgumentException - if maxDistance < 1.

    • Integer

      public Integer(int n, int maxDistance, boolean symmetric, boolean triangleInequality, long seed)
      Generates a random instance of either the TSP or ATSP.
      Parameters:
      n - The number of cities.
      maxDistance - The maximum distance between cities. The edge costs between pairs of cities are uniform in the interval [1, maxDistance].
      symmetric - Pass true for the TSP, or false for the ATSP.
      triangleInequality - Pass true if you want the generated distance matrix to respect the triangle inequality, or false for purely random distances.
      seed - The seed for the random number generator to enable reproducing the same instance for experiment reproducibility.
      Throws:
      IllegalArgumentException - if n < 2.
      IllegalArgumentException - if maxDistance < 1.

    • Integer

      public Integer(int[][] distance)
      Although the focus of this class is generating random TSP and ATSP instances, this constructor enables specifying the distance matrix directly.
      Parameters:
      distance - The distance matrix, such that distance[i][j] is the distance from city i to city j. The distance matrix must be square, with same number of rows as columns, and whose dimension determines number of cities. Dimensions must be at least 2 by 2.
      Throws:
      IllegalArgumentException - if distance is not at least a 2 by 2 array.
      IllegalArgumentException - if number of rows is not same as number of columns, or if rows don't all have same length.

  • Method Details

    • getDistance

      public final int getDistance(int i, int j)
      Gets the distance (i.e., cost) of an edge.
      Parameters:
      i - The source city.
      j - The destination city.
      Returns:
      The distance from i to j

    • length

      public final int length()
      Gets the number of cities in the TSP instance.
      Specified by:
      length in class BaseTSP
      Returns:
      number of cities

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