Package org.ddolib.examples.maximumcoverage

Class MaxCoverFastLowerBound

java.lang.Object
org.ddolib.examples.maximumcoverage.MaxCoverFastLowerBound
All Implemented Interfaces:
FastLowerBound<MaxCoverState>
public class MaxCoverFastLowerBound extends Object implements FastLowerBound<MaxCoverState>
Fast lower bound computation for the Maximum Coverage problem.

This class implements FastLowerBound and provides a cheap and optimistic lower bound on the objective value from a given state. The bound is based on the maximum cardinality of any subset in the instance.

The lower bound assumes that each remaining decision variable can cover at most maxCardSet new items, which yields a fast but coarse estimate.

  • Constructor Details

    • MaxCoverFastLowerBound

      public MaxCoverFastLowerBound(MaxCoverProblem problem)
      Constructs a fast lower bound evaluator for a given MaxCover problem.

      During construction, the maximum subset cardinality is precomputed to allow constant-time bound evaluation.

      Parameters:
      problem - the MaxCover problem instance

  • Method Details

    • fastLowerBound

      public double fastLowerBound(MaxCoverState state, Set<Integer> variables)
      Computes a fast lower bound on the objective value from a given state.

      The bound is computed by assuming that each remaining variable can contribute at most maxCardSet additional covered items. The result is returned as a negative value to match the minimization formulation of the problem.

      Specified by:
      fastLowerBound in interface FastLowerBound<MaxCoverState>
      Parameters:
      state - the current state (not explicitly used in this bound)
      variables - the set of remaining decision variables
      Returns:
      a fast, optimistic lower bound on the objective value