Package org.ddolib.examples.srflp

Class SRFLPFastLowerBound

java.lang.Object
org.ddolib.examples.srflp.SRFLPFastLowerBound
All Implemented Interfaces:
FastLowerBound<SRFLPState>
public class SRFLPFastLowerBound extends Object implements FastLowerBound<SRFLPState>
Provides a fast lower-bound estimation for the Single-Row Facility Layout Problem (SRFLP) based on the current state of the solution.

The lower bound is decomposed into two components:

  • Free lower bound: under-approximates the traffic between departments that must still be placed (free departments).
  • Fixed lower bound: accounts for the traffic between already placed (fixed) departments and the remaining free ones.

Internally, the class precomputes:

  • Pairs of departments sorted by their flow in decreasing order,
  • Departments sorted by their lengths in increasing order.

The class implements FastLowerBound and can be used in A* or decision diagram-based solvers to prune suboptimal branches efficiently.

See Also:

  • Constructor Details

    • SRFLPFastLowerBound

      public SRFLPFastLowerBound(SRFLPProblem problem)
      Constructs a fast lower-bound estimator for the given SRFLP problem.
      Parameters:
      problem - the SRFLP problem instance

  • Method Details

    • fastLowerBound

      public double fastLowerBound(SRFLPState state, Set<Integer> variables)
      Computes a fast lower bound for a given state and a set of variables.
      Specified by:
      fastLowerBound in interface FastLowerBound<SRFLPState>
      Parameters:
      state - the current SRFLP state
      variables - the set of variables to consider
      Returns:
      a lower bound on the cost of completing the solution from the current state