Package org.ddolib.examples.tsp

Class TSPFastLowerBound

java.lang.Object
org.ddolib.examples.tsp.TSPFastLowerBound
All Implemented Interfaces:
FastLowerBound<TSPState>
public class TSPFastLowerBound extends Object implements FastLowerBound<TSPState>
Implementation of a fast lower bound for the Traveling Salesman Problem (TSP).

This lower bound estimates the minimum additional cost required to complete a partial tour. For each unvisited node, it considers the smallest incident edge (minimum distance to any other node) and sums these minimum distances. It also includes the starting node (assumed as node 0) to account for the final return to the origin.

The bound is not guaranteed to be tight but is computed very efficiently, making it suitable for heuristic or branch-and-bound algorithms where fast estimations are required.

Usage: 

 TSPFastLowerBound lbCalculator = new TSPFastLowerBound(problem);
 double lb = lbCalculator.fastLowerBound(state, unassignedNodes);

  • Constructor Details

    • TSPFastLowerBound

      public TSPFastLowerBound(TSPProblem problem)
      Constructs a fast lower bound calculator for the given TSP problem.
      Parameters:
      problem - The TSP problem instance containing the distance matrix. It is assumed that the matrix is symmetric and distances are non-negative.

  • Method Details

    • fastLowerBound

      public double fastLowerBound(TSPState state, Set<Integer> unassignedVariables)
      Computes a fast lower bound on the cost to complete the TSP tour from the given state.

      The bound is computed by summing the smallest incident edges for each unvisited node, including the starting node to account for returning to the origin.

      Specified by:
      fastLowerBound in interface FastLowerBound<TSPState>
      Parameters:
      state - The current state of the tour, containing the set of nodes yet to visit.
      unassignedVariables - The set of variables (nodes) not yet assigned in the tour.
      Returns:
      A fast-computed lower bound on the remaining tour cost.