Package org.ddolib.examples.pigmentscheduling

Class PSRelax

java.lang.Object

org.ddolib.examples.pigmentscheduling.PSRelax

All Implemented Interfaces:

Relaxation<PSState>

public class PSRelax
extends Object
implements Relaxation<PSState>

Implements the relaxation mechanism used in the DDO framework for the Pigment Scheduling Problem (PSP).

The PSRelax class defines how multiple PSState objects can be merged into a single relaxed state during the search process. Relaxation is a key component of the DDO algorithm, enabling the merging of similar or compatible states to reduce the size of the search graph while preserving admissibility.

In this implementation, the relaxation rule merges states by:

• Taking the earliest time index among all merged states;
• Taking the minimum value of previousDemands for each item type, effectively under-approximating remaining demands;
• Setting the machine to the PSProblem.IDLE state, as the specific pigment context is lost during merging.

The resulting relaxed state is less constrained (hence "relaxed"), which allows the solver to reason over fewer states while maintaining lower-bound consistency.

See Also:

• PSProblem
• PSState
• Relaxation
• PSDdoMain

Constructor Summary

Constructors

Constructor	Description
PSRelax(PSProblem problem)	Constructs a relaxation operator associated with a given PSP problem.

Method Summary

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

Methods inherited from class java.lang.Object

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

Constructor Details

PSRelax

public PSRelax(PSProblem problem)

Constructs a relaxation operator associated with a given PSP problem.

Parameters:

problem - the PSProblem instance that defines the scheduling parameters, costs, and demands.

Method Details

mergeStates

public PSState mergeStates(Iterator<PSState> states)

Merges multiple PSP states into a single relaxed state.

The merging process:

• Takes the minimum time index among the given states;
• For each item type, takes the smallest (earliest) previous demand index;
• Sets the resulting state to the idle production mode.

This method effectively creates an under-approximation of the merged states, representing a superset of their feasible continuations.

Specified by:

mergeStates in interface Relaxation<PSState>

Parameters:

states - an iterator over the PSState instances to be merged

Returns:

a new relaxed PSState representing the merged configuration

relaxEdge

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

Returns the relaxed transition cost between two PSP states.

In this simple implementation, the relaxation does not alter the transition cost and simply returns the original value. More advanced relaxations could, however, modify this cost to tighten the lower bounds.

Specified by:

relaxEdge in interface Relaxation<PSState>

Parameters:

from - the originating state

to - the destination state

merged - the merged (relaxed) state

d - the decision leading to the transition

cost - the original transition cost

Returns:

the (possibly modified) transition cost after relaxation