Package org.ddolib.examples.boundedknapsack

Class BKSFastLowerBound

java.lang.Object
org.ddolib.examples.boundedknapsack.BKSFastLowerBound
All Implemented Interfaces:
FastLowerBound<Integer>
public class BKSFastLowerBound extends Object implements FastLowerBound<Integer>
A fast lower bound implementation for the BKSProblem (Bounded Knapsack Problem).

This class computes a lower bound on the optimal solution value from a given state and a subset of variables (items) using a fractional knapsack relaxation. The algorithm sorts the remaining items by their value-to-weight ratio and greedily fills the remaining capacity to approximate the best possible completion from the current partial solution.

The lower bound is returned as a negative value (following the solver convention where the objective is to minimize the total cost or maximize the profit).

Example:


 BKSProblem problem = new BKSProblem(values, weights, quantities, capacity);
 FastLowerBound<Integer> flb = new BKSFastLowerBound(problem);
 double bound = flb.fastLowerBound(currentCapacity, remainingItems);
See Also:

  • Constructor Details

    • BKSFastLowerBound

      public BKSFastLowerBound(BKSProblem problem)
      Constructs a fast lower bound evaluator for the given bounded knapsack problem.
      Parameters:
      problem - the knapsack problem instance containing item values, weights, and capacities

  • Method Details

    • fastLowerBound

      public double fastLowerBound(Integer state, Set<Integer> variables)
      Computes a fast lower bound for the given state and remaining variables.

      The algorithm:

      1. Computes the value-to-weight ratio for each remaining item.
      2. Sorts the items in descending order of their ratio (most efficient items first).
      3. Greedily fills the remaining capacity using as many units as possible of each item, possibly using a fractional last item (relaxation).
      4. Returns the negative of the total achievable value as the lower bound estimate.
      Specified by:
      fastLowerBound in interface FastLowerBound<Integer>
      Parameters:
      state - the current capacity remaining in the knapsack
      variables - the set of indices of remaining items to consider
      Returns:
      a fast lower bound estimate (as a negative value) of the optimal solution