Package org.ddolib.examples.alp

Class ALPRelax

java.lang.Object

org.ddolib.examples.alp.ALPRelax

All Implemented Interfaces:

Relaxation<ALPState>

public class ALPRelax
extends Object
implements Relaxation<ALPState>

Relaxation operator for ALPState in the Aircraft Landing Problem (ALP).

This class defines how multiple states are merged into a single relaxed state when building a relaxed decision diagram. The relaxation helps to limit the size of the decision diagram while maintaining bounds on the optimal solution.

The merged state is computed by:

• For each aircraft class, taking the minimum number of remaining aircraft among all merged states.
• For each runway, taking the minimum previous landing time among all merged states.

This ensures that the merged state is a valid under-approximation of the original states.

See Also:

• ALPState
• Relaxation

Constructor Summary

Constructors

Constructor	Description
ALPRelax(ALPProblem problem)	Constructs a relaxation operator for the given ALP problem.

Method Summary

Modifier and Type	Method	Description
ALPState	mergeStates(Iterator<ALPState> states)	Merges multiple states into a single relaxed state.
double	relaxEdge(ALPState from, ALPState to, ALPState merged, Decision d, double cost)	Returns the relaxed cost of a transition (edge) between states.

Methods inherited from class java.lang.Object

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

Constructor Details

ALPRelax

public ALPRelax(ALPProblem problem)

Constructs a relaxation operator for the given ALP problem.

Parameters:

problem - the ALP problem instance

Method Details

mergeStates

public ALPState mergeStates(Iterator<ALPState> states)

Merges multiple states into a single relaxed state.

The merged state takes the minimum remaining aircraft count per class and the minimum previous landing time per runway.

Specified by:

mergeStates in interface Relaxation<ALPState>

Parameters:

states - an iterator over the states to merge

Returns:

the merged relaxed state

relaxEdge

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

Returns the relaxed cost of a transition (edge) between states.

In this default implementation, the edge cost remains unchanged.

Specified by:

relaxEdge in interface Relaxation<ALPState>

Parameters:

from - the source state

to - the destination state

merged - the merged state

d - the decision leading to this transition

cost - the original cost of the transition

Returns:

the relaxed cost of the edge