Package org.ddolib.examples.tsp

Class TSPProblem

java.lang.Object
org.ddolib.examples.tsp.TSPProblem
All Implemented Interfaces:
Problem<TSPState>
public class TSPProblem extends Object implements Problem<TSPState>
Class representing an instance of the Traveling Salesman Problem (TSP).

This class provides functionality to:

  • Store the number of nodes and the distance matrix.
  • Evaluate the cost of a given TSP tour.
  • Create TSP instances from a distance matrix (double[][]) or from an XML file following XML-TSPLIB.
  • Provide the initial state, variable domains, and transition costs for search algorithms.
  • Optionally store the optimal solution value for benchmarking purposes.

Example usage: 

     double[][] distMatrix = ...;
     TSPProblem problem = new TSPProblem(distMatrix);
     double cost = problem.eval(new int[]{0,1,2,3});
See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    final double[][]
    distanceMatrix
    Distance matrix between nodes

  • Constructor Summary

    Constructors
    Constructor
    Description
    TSPProblem(double[][] distanceMatrix)
    Constructs a TSP instance from a given distance matrix.
    TSPProblem(double[][] distanceMatrix, double optimal)
    Constructs a TSP instance from a given distance matrix and known optimal value.
    TSPProblem(String fname)
    Constructs a TSP instance by reading an XML file in the XML-TSPLIB format.

  • Method Summary

    Modifier and Type
    Method
    Description
    Iterator<Integer>
    domain(TSPState state, int var)
    Returns the domain of possible decisions for a given state and variable index.
    double
    eval(int[] solution)
    Evaluates the total tour cost for a given solution.
    double
    evaluate(int[] solution)
    Given a solution such that solution[i] is the value of the variable x_i, returns the value of this solution and checks if the solution respects the problem's constraints.
    TSPState
    initialState()
    Returns the initial state for a search algorithm.
    double
    initialValue()
    Returns the initial cost of the problem, which is 0.
    int
    nbVars()
    Returns the number of decision variables in the problem.
    Optional<Double>
    optimalValue()
    Returns the optimal value of the instance if known.
    BitSet
    singleton(int singletonValue)
    Creates a BitSet containing only a single node.
    String
    toString()
    Returns a string representation of the instance.
    TSPState
    transition(TSPState state, Decision decision)
    Computes the next state after making a decision from the current state.
    double
    transitionCost(TSPState state, Decision decision)
    Computes the transition cost of moving from the current state to the next state by visiting a given node.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • distanceMatrix

      public final double[][] distanceMatrix
      Distance matrix between nodes

  • Constructor Details

    • TSPProblem

      public TSPProblem(double[][] distanceMatrix)
      Constructs a TSP instance from a given distance matrix.
      Parameters:
      distanceMatrix - the distance matrix of the instance

    • TSPProblem

      public TSPProblem(double[][] distanceMatrix, double optimal)
      Constructs a TSP instance from a given distance matrix and known optimal value.
      Parameters:
      distanceMatrix - the distance matrix of the instance
      optimal - the optimal solution value

    • TSPProblem

      public TSPProblem(String fname) throws IOException
      Constructs a TSP instance by reading an XML file in the XML-TSPLIB format.
      Parameters:
      fname - the path to the XML file
      Throws:
      IOException - if an error occurs while reading or parsing the file

  • Method Details

    • eval

      public double eval(int[] solution)
      Evaluates the total tour cost for a given solution.
      Parameters:
      solution - an array representing the node visit order
      Returns:
      the total cost of the tour including return to the starting node

    • nbVars

      public int nbVars()
      Returns the number of decision variables in the problem.
      Specified by:
      nbVars in interface Problem<TSPState>
      Returns:
      number of variables (equal to number of nodes)

    • initialState

      public TSPState initialState()
      Returns the initial state for a search algorithm. The initial state starts at node 0, with all other nodes unvisited.
      Specified by:
      initialState in interface Problem<TSPState>
      Returns:
      the initial TSPState

    • initialValue

      public double initialValue()
      Returns the initial cost of the problem, which is 0.
      Specified by:
      initialValue in interface Problem<TSPState>
      Returns:
      0.0

    • domain

      public Iterator<Integer> domain(TSPState state, int var)
      Returns the domain of possible decisions for a given state and variable index. The last variable represents returning to the starting node.
      Specified by:
      domain in interface Problem<TSPState>
      Parameters:
      state - the current state
      var - the variable index
      Returns:
      an iterator over possible node indices

    • transition

      public TSPState transition(TSPState state, Decision decision)
      Computes the next state after making a decision from the current state.
      Specified by:
      transition in interface Problem<TSPState>
      Parameters:
      state - the current TSPState
      decision - the decision made
      Returns:
      the resulting TSPState after applying the decision

    • transitionCost

      public double transitionCost(TSPState state, Decision decision)
      Computes the transition cost of moving from the current state to the next state by visiting a given node.
      Specified by:
      transitionCost in interface Problem<TSPState>
      Parameters:
      state - the current TSPState
      decision - the decision to move to a node
      Returns:
      the cost of the transition

    • optimalValue

      public Optional<Double> optimalValue()
      Returns the optimal value of the instance if known.
      Specified by:
      optimalValue in interface Problem<TSPState>
      Returns:
      an Optional containing the optimal value, or empty if unknown

    • evaluate

      public double evaluate(int[] solution) throws InvalidSolutionException
      Description copied from interface: Problem
      Given a solution such that solution[i] is the value of the variable x_i, returns the value of this solution and checks if the solution respects the problem's constraints.

      Note: For maximization problems, the returned value is minus the computed value.

      Specified by:
      evaluate in interface Problem<TSPState>
      Parameters:
      solution - A solution of the problem.
      Returns:
      The value of the input solution
      Throws:
      InvalidSolutionException - If the solution does not respect problem's constraints.

    • singleton

      public BitSet singleton(int singletonValue)
      Creates a BitSet containing only a single node.
      Parameters:
      singletonValue - the node to include
      Returns:
      a BitSet with only the specified node set

    • toString

      public String toString()
      Returns a string representation of the instance. If a name is set, it returns the name; otherwise, it prints the size and distance matrix.
      Overrides:
      toString in class Object
      Returns:
      string representation of the TSPProblem