Package org.ddolib.examples.msct

Class MSCTRelax

java.lang.Object

org.ddolib.examples.msct.MSCTRelax

All Implemented Interfaces:

Relaxation<MSCTState>

public class MSCTRelax
extends Object
implements Relaxation<MSCTState>

Implements the relaxation operator for the MSCTProblem in the context of Decision Diagram Optimization (DDO) algorithms.

The relaxation defines how multiple MSCTState objects (representing partial scheduling solutions) can be merged into a single abstract state in order to control the width of the decision diagram and maintain computational tractability.

Relaxation principle:

• The merged state’s set of remaining jobs is the union of all jobs that remain in the input states.
• The merged state’s current time is the minimum of the current times across all merged states. This heuristic keeps the relaxation optimistic (i.e., it underestimates the completion times).

This relaxation is typically used in DDO to merge similar states that share overlapping sets of remaining jobs, reducing diagram width while ensuring that no feasible solution is lost (i.e., maintaining validity of the lower bound).

See Also:

• MSCTProblem
• MSCTState
• Relaxation
• MSCTDdoMain

Constructor Summary

Constructors

Constructor	Description
MSCTRelax(MSCTProblem problem)	Constructs a relaxation operator for the given MSCT problem instance.

Method Summary

Modifier and Type	Method	Description
MSCTState	mergeStates(Iterator<MSCTState> states)	Merges several MSCTState objects into a single relaxed state.
double	relaxEdge(MSCTState from, MSCTState to, MSCTState merged, Decision d, double cost)	Computes the relaxed cost associated with transitioning from one state to another.

Methods inherited from class java.lang.Object

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

Constructor Details

MSCTRelax

public MSCTRelax(MSCTProblem problem)

Constructs a relaxation operator for the given MSCT problem instance.

Parameters:

problem - the instance of the MSCTProblem to which this relaxation applies.

Method Details

mergeStates

public MSCTState mergeStates(Iterator<MSCTState> states)

Merges several MSCTState objects into a single relaxed state.

The resulting state represents an optimistic combination of the input states: it includes all remaining jobs that could appear in any of them, and uses the minimum current time among them to avoid overestimating the cost.

Specified by:

mergeStates in interface Relaxation<MSCTState>

Parameters:

states - an iterator over the states to merge.

Returns:

a new MSCTState representing the relaxed merged state.

relaxEdge

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

Computes the relaxed cost associated with transitioning from one state to another.

In this implementation, no additional relaxation is applied to the edge cost; the cost remains identical to the original transition cost.

Specified by:

relaxEdge in interface Relaxation<MSCTState>

Parameters:

from - the origin state.

to - the target state.

merged - the merged (relaxed) state resulting from the combination of states.

d - the decision made during the transition.

cost - the original transition cost.

Returns:

the relaxed transition cost (identical to cost here).