Package org.ddolib.examples.talentscheduling

Class TSFastLowerBound

java.lang.Object
org.ddolib.examples.talentscheduling.TSFastLowerBound
All Implemented Interfaces:
FastLowerBound<TSState>
public class TSFastLowerBound extends Object implements FastLowerBound<TSState>
Implementation of a fast lower bound for the Talent Scheduling Problem (TSP).

This class computes a heuristic lower bound on the total cost of a partially scheduled solution, based on the method described in Garcia et al.. It takes into account both the duration of scenes and the actor costs for scenes that are not yet scheduled.

The bound is computed in two main steps:

  1. Compute a contribution for each unscheduled scene based on actors present and their costs.
  2. Adjust for cumulative actor contributions using ratios and sort actors to estimate the remaining cost.
The result is rounded up to handle floating-point errors.

This lower bound is intended for use with search algorithms (e.g., ACS, A*, DDO) to prune suboptimal branches efficiently.

  • Constructor Details

    • TSFastLowerBound

      public TSFastLowerBound(TSProblem problem)
      Constructs a fast lower bound calculator for a given TSP problem.
      Parameters:
      problem - The Talent Scheduling Problem instance.

  • Method Details

    • fastLowerBound

      public double fastLowerBound(TSState state, Set<Integer> variables)
      Computes a fast lower bound on the total cost from the given partial state.
      Specified by:
      fastLowerBound in interface FastLowerBound<TSState>
      Parameters:
      state - The current state of the scheduling problem.
      variables - The set of variables (scenes) still to be scheduled.
      Returns:
      The computed lower bound on the total cost, rounded up.