Package org.ddolib.examples.misp

Class MispFastLowerBound

java.lang.Object
org.ddolib.examples.misp.MispFastLowerBound
All Implemented Interfaces:
FastLowerBound<BitSet>
public class MispFastLowerBound extends Object implements FastLowerBound<BitSet>
Computes a fast lower bound for the Maximum Independent Set Problem (MISP).

This implementation of FastLowerBound estimates the best possible solution from a given state by considering all remaining vertices optimistically. The bound is used in search algorithms to prune suboptimal branches efficiently.

  • Constructor Details

    • MispFastLowerBound

      public MispFastLowerBound(MispProblem problem)
      Constructs a fast lower bound calculator for a given MISP problem.
      Parameters:
      problem - the MISP problem instance

  • Method Details

    • fastLowerBound

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

      The method sums the weights of all vertices already selected in the current state and returns its negation, which corresponds to the maximal independent set assumption.

      Specified by:
      fastLowerBound in interface FastLowerBound<BitSet>
      Parameters:
      state - the current state of the solution as a BitSet
      variables - the set of remaining variable indices (unused in this implementation)
      Returns:
      a fast lower bound on the optimal solution value