Package org.ddolib.examples.mks

Class MKSFastLowerBound

java.lang.Object
org.ddolib.examples.mks.MKSFastLowerBound
All Implemented Interfaces:
FastLowerBound<MKSState>
public class MKSFastLowerBound extends Object implements FastLowerBound<MKSState>
Provides a fast lower bound estimation for Multi-dimensional Knapsack (MKS) states.

This class implements FastLowerBound and computes a simple, fast lower bound on the negative total profit that can be achieved by a given set of variables (items). The lower bound does not consider capacities or interactions between dimensions, but only sums the profits of the candidate items.

  • Constructor Details

    • MKSFastLowerBound

      public MKSFastLowerBound(MKSProblem problem)
      Constructs a fast lower bound evaluator for the given MKS problem.
      Parameters:
      problem - the multi-dimensional knapsack problem

  • Method Details

    • fastLowerBound

      public double fastLowerBound(MKSState state, Set<Integer> variables)
      Computes a fast lower bound for a given state and a set of variables (items).

      The bound is calculated as the negated sum of the profits of the variables, ignoring capacity constraints.

      Specified by:
      fastLowerBound in interface FastLowerBound<MKSState>
      Parameters:
      state - the current MKS state
      variables - the set of variable indices (items) to consider
      Returns:
      a lower bound on the cost (negative total profit) achievable