Package org.ddolib.examples.knapsack

Class KSRelax

java.lang.Object

org.ddolib.examples.knapsack.KSRelax

All Implemented Interfaces:

Relaxation<Integer>

public class KSRelax
extends Object
implements Relaxation<Integer>

Relaxation for the Knapsack Problem (KS).

This class implements a simple relaxation of the state space for relaxed decision diagrams. The merged state corresponds to the maximum remaining capacity among all states being merged.

The edge relaxation does not modify the cost: it simply returns the original cost.

See Also:

• Relaxation

Constructor Summary

Constructors

Constructor	Description
KSRelax()

Method Summary

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

Methods inherited from class java.lang.Object

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

Constructor Details

KSRelax

public KSRelax()

Method Details

mergeStates

public Integer mergeStates(Iterator<Integer> states)

Merges multiple states into a single relaxed state.

For the Knapsack problem, the merged state is defined as the maximum remaining capacity among the states being merged.

Specified by:

mergeStates in interface Relaxation<Integer>

Parameters:

states - an iterator over the states to merge

Returns:

the merged state representing the maximum remaining capacity

relaxEdge

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

Relaxes the cost of an edge between states in the decision diagram.

For the Knapsack problem, the cost is not modified by the relaxation.

Specified by:

relaxEdge in interface Relaxation<Integer>

Parameters:

from - the starting state

to - the ending state

merged - the merged state after relaxation

d - the decision associated with the edge

cost - the original cost of the edge

Returns:

the relaxed cost (identical to the original cost in this implementation)