Package org.ddolib.examples.smic

Class SMICRelax

java.lang.Object

org.ddolib.examples.smic.SMICRelax

All Implemented Interfaces:

Relaxation<SMICState>

public class SMICRelax
extends Object
implements Relaxation<SMICState>

The SMICRelax class implements a relaxation operator for the SMICProblem, used in Decision Diagram Optimization (DDO)-based solvers.

The relaxation defines how to merge multiple SMICState instances representing similar subproblems into a single aggregated state, in order to reduce the diagram size while maintaining an admissible relaxation (i.e., not underestimating the true cost).

This specific relaxation merges states by:

• Taking the union of their remaining jobs,
• Taking the minimum of their current times (earliest time reached),
• Taking the maximum of their minimum inventory levels,
• Taking the minimum of their maximum inventory levels.

If the resulting inventory interval becomes infeasible (i.e., minCurrentInventory > maxCurrentInventory), the merged state uses the same value for both bounds to ensure consistency.

The relaxEdge(SMICState, SMICState, SMICState, Decision, double) method does not alter the transition cost — it returns the same value as the original edge, meaning this relaxation focuses on state aggregation only.

See Also:

• SMICState
• SMICProblem
• Relaxation

Constructor Summary

Constructors

Constructor	Description
SMICRelax(SMICProblem problem)	Constructs a relaxation operator for the given SMICProblem.

Method Summary

Modifier and Type	Method	Description
SMICState	mergeStates(Iterator<SMICState> states)	Merges several SMICState objects into a single relaxed state.
double	relaxEdge(SMICState from, SMICState to, SMICState merged, Decision d, double cost)	Relaxes the cost of an edge between two states.

Methods inherited from class java.lang.Object

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

Constructor Details

SMICRelax

public SMICRelax(SMICProblem problem)

Constructs a relaxation operator for the given SMICProblem.

Parameters:

problem - the problem definition providing data and constraints

Method Details

mergeStates

public SMICState mergeStates(Iterator<SMICState> states)

Merges several SMICState objects into a single relaxed state.

The merged state conservatively approximates the set of original states, ensuring that no feasible solution is lost while potentially combining multiple subproblems to reduce computational complexity.

Specified by:

mergeStates in interface Relaxation<SMICState>

Parameters:

states - an iterator over the states to be merged

Returns:

a new relaxed SMICState combining the information of all inputs

relaxEdge

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

Relaxes the cost of an edge between two states.

In this implementation, the relaxation does not modify the edge cost; the returned cost is identical to the input cost.

Specified by:

relaxEdge in interface Relaxation<SMICState>

Parameters:

from - the source state before applying the decision

to - the target state after applying the decision

merged - the merged state resulting from relaxation

d - the decision applied

cost - the original transition cost

Returns:

the relaxed (possibly modified) edge cost, unchanged in this implementation