Package org.ddolib.examples.mks

Class MKSRelax

java.lang.Object

org.ddolib.examples.mks.MKSRelax

All Implemented Interfaces:

Relaxation<MKSState>

public class MKSRelax
extends Object
implements Relaxation<MKSState>

Relaxation strategy for the multi-dimensional Knapsack problem (MKS) states.

This class implements the Relaxation interface and provides a way to merge multiple MKS states into a single relaxed state for use in decision diagrams. The relaxation ensures that the merged state overestimates the remaining capacities, which is safe for optimization purposes.

Constructor Summary

Constructors

Constructor	Description
MKSRelax()

Method Summary

Modifier and Type	Method	Description
MKSState	mergeStates(Iterator<MKSState> states)	Merges multiple MKS states into a single relaxed state.
double	relaxEdge(MKSState from, MKSState to, MKSState merged, Decision d, double cost)	Returns the cost of an edge in the relaxed decision diagram.

Methods inherited from class java.lang.Object

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

Constructor Details

MKSRelax

public MKSRelax()

Method Details

mergeStates

public MKSState mergeStates(Iterator<MKSState> states)

Merges multiple MKS states into a single relaxed state.

The merged state takes the maximum capacity along each dimension across all input states. This produces a relaxed state that safely overestimates the remaining capacities.

Specified by:

mergeStates in interface Relaxation<MKSState>

Parameters:

states - an iterator over the states to merge

Returns:

a new MKSState representing the relaxed merged state

relaxEdge

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

Returns the cost of an edge in the relaxed decision diagram.

For this relaxation, the edge cost is unchanged and simply returns the original cost.

Specified by:

relaxEdge in interface Relaxation<MKSState>

Parameters:

from - the source state

to - the destination state

merged - the merged state corresponding to the relaxation

d - the decision taken along this edge

cost - the original cost of the edge

Returns:

the relaxed edge cost, equal to cost