Package org.ddolib.examples.pigmentscheduling

Class PSFastLowerBound

java.lang.Object
org.ddolib.examples.pigmentscheduling.PSFastLowerBound
All Implemented Interfaces:
FastLowerBound<PSState>
public class PSFastLowerBound extends Object implements FastLowerBound<PSState>
Computes a fast lower bound for the Pigment Sequencing Problem (PSP).

This class implements the FastLowerBound interface for PSState and combines two complementary lower-bound estimations:

  • A changeover cost lower bound derived from a precomputed Travelling Salesman Problem (TSP) lower bound on all subsets of items.
  • A stocking cost lower bound computed using the Wagner-Whitin approach on the remaining items to produce.

These estimations follow the principle presented in the PhD Thesis of Vianney Coppe (2024), which states that since the two cost components (changeover and stocking) do not overlap, their respective lower bounds can be summed to produce a stronger Relaxed Lower Bound (RLB) for the PSP.

Key idea: The changeover costs are bounded using a TSP-like structure, while the stocking costs are bounded based on the minimal inventory holding costs required to satisfy all pending demands.

  • Constructor Details

    • PSFastLowerBound

      public PSFastLowerBound(PSProblem problem)
      Constructs a fast lower bound evaluator for a given PSP instance.

      During initialization, the TSP lower bounds for all subsets of item types are precomputed using the TSPLowerBound.lowerBoundForAllSubsets(int[][]) method, which allows for fast lookup during the search.

      Parameters:
      problem - the PSP instance for which this lower bound will be computed

  • Method Details

    • fastLowerBound

      public double fastLowerBound(PSState state, Set<Integer> variables)
      Computes a fast (but admissible) lower bound on the remaining production cost for the given PSP state.

      The bound combines:

      • A changeover cost lower bound obtained from a precomputed TSP bound on the subset of item types that remain to be produced.
      • A stocking cost lower bound derived from the minimal inventory cost required to satisfy future demands, following a Wagner-Whitin formulation.

      This heuristic offers an efficient way to estimate the minimal achievable cost without solving the entire subproblem, thus improving pruning during the search.

      Specified by:
      fastLowerBound in interface FastLowerBound<PSState>
      Parameters:
      state - the current partial PSP state
      variables - the set of decision variables yet to be assigned
      Returns:
      a non-negative lower bound on the remaining total cost