Package org.ddolib.examples.misp

Class MispRelax

java.lang.Object

org.ddolib.examples.misp.MispRelax

All Implemented Interfaces:

Relaxation<BitSet>

public class MispRelax
extends Object
implements Relaxation<BitSet>

Implements a relaxation strategy for the Maximum Independent Set Problem (MISP) to be used in decision diagram optimization (DDO) algorithms.

This relaxation defines how to merge multiple states and how to adjust transition costs when exploring the relaxed search space.

In this implementation:

• The merged state is computed as the union of all given states, meaning all nodes that are available in at least one state are considered available in the merged state.
• The edge relaxation does not modify the transition cost; it returns the original cost.

Constructor Summary

Constructors

Constructor	Description
MispRelax(MispProblem problem)	Constructs a relaxation for the given MISP problem instance.

Method Summary

Modifier and Type	Method	Description
BitSet	mergeStates(Iterator<BitSet> states)	Merges multiple states into a single relaxed state.
double	relaxEdge(BitSet from, BitSet to, BitSet merged, Decision d, double cost)	Adjusts the transition cost when moving from one state to another in the relaxed space.

Methods inherited from class java.lang.Object

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

Constructor Details

MispRelax

public MispRelax(MispProblem problem)

Constructs a relaxation for the given MISP problem instance.

Parameters:

problem - the Maximum Independent Set problem instance

Method Details

mergeStates

public BitSet mergeStates(Iterator<BitSet> states)

Merges multiple states into a single relaxed state.

The merged state is the union of all input states: a node is considered available if it is available in at least one of the states.

Specified by:

mergeStates in interface Relaxation<BitSet>

Parameters:

states - an iterator over the states to merge

Returns:

the merged state representing an over-approximation of all input states

relaxEdge

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

Adjusts the transition cost when moving from one state to another in the relaxed space.

In this implementation, the relaxation does not modify the cost and simply returns it.

Specified by:

relaxEdge in interface Relaxation<BitSet>

Parameters:

from - the source state

to - the destination state

merged - the merged state

d - the decision applied

cost - the original transition cost

Returns:

the relaxed transition cost (here equal to cost)