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.
Relaxes the edge that used to go from the from state to the to state and computes the cost of the new edge going from the from state to the merged state. The decision which is being relaxed is given by decision and the value of the not relaxed arc is cost.
Relaxes the edge that used to go from the from state to the to state and computes the cost of the new edge going from the from state to the merged state. The decision which is being relaxed is given by decision and the value of the not relaxed arc is cost.
Value parameters
cost
the cost of the not relaxed arc which used to go from the from state to the to state
decision
the decision which is being challenged
from
the origin of the relaxed arc
merged
the destination of the relaxed arc (after relaxation)
to
the destination of the relaxed arc (before relaxation)