Package org.ddolib.examples.srflp

Class SRFLPRelax

java.lang.Object

org.ddolib.examples.srflp.SRFLPRelax

All Implemented Interfaces:

Relaxation<SRFLPState>

public class SRFLPRelax
extends Object
implements Relaxation<SRFLPState>

Implementation of a relaxation for the Single Row Facility Layout Problem (SRFLP).

In this relaxation, multiple SRFLP states can be merged into a single state to reduce the search space. The merged state over-approximates the possible states by combining the "must" and "maybe" sets and taking minimal cut values.

This class implements the Relaxation interface and is typically used in decision diagram or DDO-based algorithms for SRFLP to enable state merging and efficient pruning.

Constructor Summary

Constructors

Constructor	Description
SRFLPRelax(SRFLPProblem problem)	Constructs a new relaxation instance for a given SRFLP problem.

Method Summary

Modifier and Type	Method	Description
SRFLPState	mergeStates(Iterator<SRFLPState> states)	Merges multiple SRFLP states into a single relaxed state.
double	relaxEdge(SRFLPState from, SRFLPState to, SRFLPState merged, Decision d, double cost)	Relaxation of an edge cost between two states.

Methods inherited from class java.lang.Object

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

Constructor Details

SRFLPRelax

public SRFLPRelax(SRFLPProblem problem)

Constructs a new relaxation instance for a given SRFLP problem.

Parameters:

problem - The SRFLP problem instance to which this relaxation applies.

Method Details

mergeStates

public SRFLPState mergeStates(Iterator<SRFLPState> states)

Merges multiple SRFLP states into a single relaxed state.

The merged state:

• Intersects the "must" sets of all input states.
• Unites the "must" and "maybe" sets into the merged "maybe" set.
• Takes the minimal cut values for each department.
• Uses the maximum depth among all merged states.

Specified by:

mergeStates in interface Relaxation<SRFLPState>

Parameters:

states - An iterator over the states to merge.

Returns:

A new SRFLPState representing the merged relaxation of the input states.

relaxEdge

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

Relaxation of an edge cost between two states.

In this implementation, the edge cost is not modified by the relaxation and is returned as-is.

Specified by:

relaxEdge in interface Relaxation<SRFLPState>

Parameters:

from - The source state.

to - The target state.

merged - The merged state containing this edge.

d - The decision taken to move from from to to.

cost - The original cost of the edge.

Returns:

The relaxed cost of the edge, which in this case is equal to cost.