Package org.ddolib.examples.max2sat

Class Max2SatFastLowerBound

java.lang.Object
org.ddolib.examples.max2sat.Max2SatFastLowerBound
All Implemented Interfaces:
FastLowerBound<Max2SatState>
public class Max2SatFastLowerBound extends Object implements FastLowerBound<Max2SatState>
Implementation of a fast lower bound heuristic for the Maximum 2-Satisfiability (MAX2SAT) problem.

This class provides a quick computation of a lower bound on the best possible solution from a given partial assignment (state) in a MAX2SAT instance. It is designed to be used in branch-and-bound, A*, or DDO algorithms to prune suboptimal branches efficiently.

The heuristic combines:

  • A ranking of the current state using Max2SatRanking.
  • Precomputed contributions from unary clauses (single variable) that only depend on the variable's depth.
  • An over-approximation of the optimal solution for the remaining subproblem (pairwise interactions of remaining variables).

Precomputations are performed once during construction to speed up repeated lower bound queries.

See Also:

  • Constructor Details

    • Max2SatFastLowerBound

      public Max2SatFastLowerBound(Max2SatProblem problem)
      Constructs the fast lower bound for a given MAX2SAT problem instance.
      Parameters:
      problem - the MAX2SAT problem instance

  • Method Details

    • fastLowerBound

      public double fastLowerBound(Max2SatState state, Set<Integer> variables)
      Computes the fast lower bound for a given state and set of remaining variables.
      Specified by:
      fastLowerBound in interface FastLowerBound<Max2SatState>
      Parameters:
      state - the current MAX2SAT state (partial assignment)
      variables - the set of remaining variable indices (not yet assigned)
      Returns:
      a fast lower bound on the best possible solution from this state