Implementation of a dominance relation for the Maximum Independent Set Problem (MISP).
In this context, one state state1 is considered dominated by another state state2 if all vertices selected in state1 are also selected in state2. This allows pruning suboptimal states during the search.
Test whether state1 is dominated by or equivalent to state2.
Test whether state1 is dominated by or equivalent to state2.
A state state1 is said to be dominated by state2 if every feasible continuation from state1 cannot yield a better objective value than one from state2. In other words, state2 is at least as good as state1 in all relevant aspects of the problem.
Value parameters
state1
the first state to compare
state2
the second state to compare against
Attributes
Returns
true if state1 is dominated by or equivalent to state2
Returns a canonical key associated with a given state.
Returns a canonical key associated with a given state.
This key is typically used to identify equivalent states or to group states that share the same dominance characteristics. Implementations should ensure that two states with identical keys are comparable under the same dominance criteria.
Value parameters
state
the state for which a dominance key is requested
Attributes
Returns
an object uniquely (or canonically) representing the given state