Package org.ddolib.util

Class TSPLowerBound

java.lang.Object
org.ddolib.util.TSPLowerBound
public class TSPLowerBound extends Object
Utility class to compute lower bounds for the Traveling Salesman Problem (TSP).

This class provides methods to compute a simple yet effective lower bound on the cost of visiting subsets of nodes in a TSP instance, based on the minimum incident edges for each node in the subset.

The lower bound is used in more complex problems (like Production Scheduling Problem) where the TSP component appears in the calculation of minimum changeover costs.

  • Constructor Details

    • TSPLowerBound

      public TSPLowerBound()

  • Method Details

    • lowerBoundForAllSubsets

      public static int[] lowerBoundForAllSubsets(int[][] costMatrix)
      Computes a lower-bound for all subsets of a set of nodes based on the given cost matrix.

      For a given cost matrix, this method calculates a lower bound for each subset of nodes {0, ..., n-1}, where n is the size of the matrix. The lower bound is computed by summing the minimum incident edge of each node in the subset, considering only edges connecting nodes within the subset.

      Each subset of nodes is represented by an integer using its binary representation: the i-th bit is 1 if node i is included in the subset, 0 otherwise.

      Parameters:
      costMatrix - a square matrix of size n x n representing the cost between nodes
      Returns:
      an array of integers where the i-th element represents the lower bound for the subset corresponding to the binary representation of i