Package org.ddolib.examples.boundedknapsack

Class BKSRelax

java.lang.Object

org.ddolib.examples.boundedknapsack.BKSRelax

All Implemented Interfaces:

Relaxation<Integer>

public class BKSRelax
extends Object
implements Relaxation<Integer>

A relaxation strategy for the Bounded Knapsack Problem (BKP) used in relaxed decision diagrams.

This class implements the Relaxation interface, providing a way to merge multiple states and optionally relax edge costs in the construction of a relaxed decision diagram (DD).

Merge strategy: the merged state is the maximum remaining capacity among the given states. This ensures that the relaxation over-approximates the remaining capacity and maintains feasibility in the relaxed DD.

Edge relaxation: the cost of transitions is not modified and returned unchanged. This simple strategy preserves the original objective value.

See Also:

• Relaxation
• BKSProblem

Constructor Summary

Constructors

Constructor	Description
BKSRelax()	Default constructor.

Method Summary

Modifier and Type	Method	Description
Integer	mergeStates(Iterator<Integer> states)	Merges a set of states into a single representative state for a relaxed DD.
double	relaxEdge(Integer from, Integer to, Integer merged, Decision d, double cost)	Optionally relaxes the edge cost when transitioning from a state to a merged state.

Methods inherited from class java.lang.Object

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

Constructor Details

BKSRelax

public BKSRelax()

Default constructor.

Method Details

mergeStates

public Integer mergeStates(Iterator<Integer> states)

Merges a set of states into a single representative state for a relaxed DD.

For BKP, this implementation returns the maximum remaining capacity among the given states.

Specified by:

mergeStates in interface Relaxation<Integer>

Parameters:

states - an iterator over the states to merge

Returns:

the merged state

relaxEdge

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

Optionally relaxes the edge cost when transitioning from a state to a merged state.

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

Specified by:

relaxEdge in interface Relaxation<Integer>

Parameters:

from - the origin state

to - the destination state

merged - the merged state after relaxation

d - the decision taken to move from from to to

cost - the original cost of the edge

Returns:

the relaxed cost (unchanged in this implementation)