Package org.ddolib.examples.mcp

Class MCPRelax

java.lang.Object

org.ddolib.examples.mcp.MCPRelax

All Implemented Interfaces:

Relaxation<MCPState>

public class MCPRelax
extends Object
implements Relaxation<MCPState>

Implements a relaxation strategy for the Maximum Cut Problem (MCP).

This relaxation is used in dynamic programming or branch-and-bound algorithms to merge multiple states into a single optimistic state while preserving bounds.

The merging strategy works as follows:

• If all net benefits for a variable are positive, the merged state keeps the smallest value.
• If all net benefits for a variable are negative, the merged state keeps the largest value.
• If net benefits have mixed signs, the merged value is set to 0.

The relaxEdge(MCPState, MCPState, MCPState, Decision, double) method adjusts the transition cost to ensure the relaxation remains an over-approximation of the true cost.

See Also:

• MCPProblem
• MCPState
• Relaxation

Constructor Summary

Constructors

Constructor	Description
MCPRelax(MCPProblem problem)	Constructs a relaxation for the given MCP problem.

Method Summary

Modifier and Type	Method	Description
MCPState	mergeStates(Iterator<MCPState> states)	Merges multiple MCP states into a single optimistic state.
double	relaxEdge(MCPState from, MCPState to, MCPState merged, Decision d, double cost)	Computes the relaxed transition cost from one state to another given a merged state.

Methods inherited from class java.lang.Object

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

Constructor Details

MCPRelax

public MCPRelax(MCPProblem problem)

Constructs a relaxation for the given MCP problem.

Parameters:

problem - the MCP problem instance

Method Details

mergeStates

public MCPState mergeStates(Iterator<MCPState> states)

Merges multiple MCP states into a single optimistic state.

The merged state keeps a conservative estimate of net benefits for remaining decision variables in order to maintain an over-approximation of the optimal solution.

Specified by:

mergeStates in interface Relaxation<MCPState>

Parameters:

states - an iterator over states to merge

Returns:

a new MCPState representing the merged state

relaxEdge

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

Computes the relaxed transition cost from one state to another given a merged state.

This method adjusts the cost to account for the differences between the actual net benefits in the target state and the merged state, ensuring that the relaxation remains optimistic.

Specified by:

relaxEdge in interface Relaxation<MCPState>

Parameters:

from - the initial state

to - the target state

merged - the merged state used for relaxation

d - the decision applied to reach the target state

cost - the original transition cost

Returns:

the relaxed transition cost