Package org.ddolib.examples.max2sat

Class Max2SatRelax

java.lang.Object

org.ddolib.examples.max2sat.Max2SatRelax

All Implemented Interfaces:

Relaxation<Max2SatState>

public class Max2SatRelax
extends Object
implements Relaxation<Max2SatState>

Implements a relaxation for the Maximum 2-Satisfiability (MAX2SAT) problem.

This class provides a mechanism to merge multiple Max2SatState instances into a single relaxed state, which can be used in relaxation-based search algorithms such as DDO or A*.

The merge strategy aims to be optimistic without overestimating: for each variable, if all states have the same sign of net benefit, the smallest magnitude is kept; otherwise, the net benefit is set to 0. This approach ensures that the merged state does not overestimate the achievable benefit, providing a valid lower bound for maximization.

The relaxEdge(Max2SatState, Max2SatState, Max2SatState, Decision, double) method adjusts the transition cost to account for losses of net benefit in the merged state, ensuring an over-approximation of the optimal solution.

See Also:

• Max2SatProblem
• Max2SatState
• Relaxation

Constructor Summary

Constructors

Constructor	Description
Max2SatRelax(Max2SatProblem problem)	Constructs a relaxation for the given MAX2SAT problem.

Method Summary

Modifier and Type	Method	Description
Max2SatState	mergeStates(Iterator<Max2SatState> states)	Merges multiple Max2SatState instances into a single relaxed state.
double	relaxEdge(Max2SatState from, Max2SatState to, Max2SatState merged, Decision d, double cost)	Adjusts the cost of transitioning from one state to another in the relaxed model.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Max2SatRelax

public Max2SatRelax(Max2SatProblem problem)

Constructs a relaxation for the given MAX2SAT problem.

Parameters:

problem - the MAX2SAT problem instance

Method Details

mergeStates

public Max2SatState mergeStates(Iterator<Max2SatState> states)

Merges multiple Max2SatState instances into a single relaxed state.

For each variable, if all the net benefits in the states have the same sign, the smallest magnitude is kept; otherwise, the net benefit is set to 0. The depth of the merged state corresponds to the depth of the last processed state.

Specified by:

mergeStates in interface Relaxation<Max2SatState>

Parameters:

states - an iterator over the states to merge

Returns:

a new Max2SatState representing the merged relaxed state

relaxEdge

public double relaxEdge(Max2SatState from,
 Max2SatState to,
 Max2SatState merged,
 Decision d,
 double cost)

Adjusts the cost of transitioning from one state to another in the relaxed model.

The method compensates for potential losses in net benefits when using a merged state, ensuring that the transition cost maintains an over-approximation of the optimal solution.

Specified by:

relaxEdge in interface Relaxation<Max2SatState>

Parameters:

from - the original state before the transition

to - the original state after the transition

merged - the merged relaxed state

d - the decision taken

cost - the original transition cost

Returns:

the adjusted transition cost in the relaxed model