Package org.ddolib.examples.knapsack

Class KSFastLowerBound

java.lang.Object
org.ddolib.examples.knapsack.KSFastLowerBound
All Implemented Interfaces:
FastLowerBound<Integer>
public class KSFastLowerBound extends Object implements FastLowerBound<Integer>
Fast lower bound heuristic for the Knapsack Problem (KS).

This class implements a quick estimation of the lower bound of the optimal solution for a given knapsack state. The heuristic uses a greedy strategy based on the profit-to-weight ratio of items, selecting the most profitable items first until the remaining capacity is exhausted.

The returned value is negated to be compatible with solvers that minimize the objective function.

  • Constructor Details

    • KSFastLowerBound

      public KSFastLowerBound(KSProblem problem)
      Constructs a new fast lower bound heuristic for the given Knapsack problem.
      Parameters:
      problem - the Knapsack problem instance

  • Method Details

    • fastLowerBound

      public double fastLowerBound(Integer state, Set<Integer> variables)
      Computes a fast lower bound for the given knapsack state.
      Specified by:
      fastLowerBound in interface FastLowerBound<Integer>
      Parameters:
      state - the current remaining capacity of the knapsack
      variables - the set of available item indices
      Returns:
      a fast estimate of the lower bound (negated)