Class TSPLIB

java.lang.Object
org.cicirello.search.problems.tsp.TSPLIB
All Implemented Interfaces:
IntegerCostOptimizationProblem<Permutation>, Problem<Permutation>
public final class TSPLIB extends Object implements IntegerCostOptimizationProblem<Permutation>
Parser for TSPLIB problem instances. Initially, it supports TSPLIB problem instances that are instances of the symmetric traveling salesperson problem. Support for the other problem types provided in the TSPLIB benchmark problems may be added later.

The file format is described here: TSPLIB file specification

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

    • instanceName

      public String instanceName()
      Gets the name of the instance.
      Returns:
      the instance name

    • toString

      public String toString(Permutation p)
      Generates a String representing a tour for this problem instance in TSPLIB format.
      Parameters:
      p - the tour
      Returns:
      a String in TSPLIB's file format for a tour

    • toString

      public String toString(Permutation p, String comment)
      Generates a String representing a tour for this problem instance in TSPLIB format.
      Parameters:
      p - the tour
      comment - a comment to add in the header
      Returns:
      a String in TSPLIB's file format for a tour

    • createMinimalMemory

      public static TSPLIB createMinimalMemory(Readable instanceData)
      Parses a TSPLIB formatted file, creating the corresponding problem instance. The problem instance created by this method calculates the edge weights every time required from the node coordinates. This enables storing only the node coordinates in memory rather than an entire matrix.
      Parameters:
      instanceData - a Readble containing the contents of a TSPLIB formatted problem instance
      Returns:
      if instanceData contains an instance of a supported problem type, then this returns the TSPLIB problem instance. otherwise it returns null.

    • createFullMatrix

      public static TSPLIB createFullMatrix(Readable instanceData)
      Parses a TSPLIB formatted file, creating the corresponding problem instance. The problem instance created by this method pre-computes an edge weight matrix, requiring quadratic memory in the number of cities. If memory constraints are tight, consider using createMinimalMemory(Readable) instead.
      Parameters:
      instanceData - a Readble containing the contents of a TSPLIB formatted problem instance
      Returns:
      if instanceData contains an instance of a supported problem type, then this returns the TSPLIB problem instance. otherwise it returns null.

    • createTriangleMatrix

      public static TSPLIB createTriangleMatrix(Readable instanceData)
      Parses a TSPLIB formatted file, creating the corresponding problem instance. The problem instance created by this method pre-computes a triangular edge weight matrix, requiring quadratic memory in the number of cities, but half that of the full matrix. If memory constraints are very tight, consider using createMinimalMemory(Readable) instead.
      Parameters:
      instanceData - a Readble containing the contents of a TSPLIB formatted problem instance
      Returns:
      if instanceData contains an instance of a supported problem type, then this returns the TSPLIB problem instance. otherwise it returns null.