Package org.ddolib.common.dominance

Class SimpleDominanceChecker<T>

java.lang.Object

org.ddolib.common.dominance.DominanceChecker<T>

org.ddolib.common.dominance.SimpleDominanceChecker<T>

Type Parameters:

T - The type of the states managed by the dominance relation.

public class SimpleDominanceChecker<T>
extends DominanceChecker<T>

The SimpleDominanceChecker class implements a straightforward dominance management mechanism used in search algorithms based on Multi-valued Decision Diagrams (MDDs), such as DDO (Decision Diagram Optimization).

It maintains, for each depth level of the MDD, a collection of non-dominated states, according to a user-defined Dominance relation. When a new state is explored, this checker determines whether it is dominated by an existing state, or if it dominates others already stored in the same level.

The class uses a nested structure of:

• A list indexed by depth (one per decision variable or time step),
• For each depth, a map associating a key (computed from the state) to a set of non-dominated states,
• Each state is wrapped in a SimpleDominanceChecker<T>.org.ddolib.common.dominance.SimpleDominanceChecker.ValueState object containing its associated objective value and a deterministic ID for ordering.

The goal is to avoid exploring redundant or inferior states during optimization, which significantly reduces the search space and improves efficiency.

See Also:

• Dominance
• DominanceChecker
• SimpleDominanceChecker<T>.org.ddolib.common.dominance.SimpleDominanceChecker.ValueState

Field Summary

Fields inherited from class org.ddolib.common.dominance.DominanceChecker

dominance

Constructor Summary

Constructors

Constructor	Description
SimpleDominanceChecker(Dominance<T> dominance, int nVars)	Constructs a SimpleDominanceChecker with the given dominance relation and number of decision variables.

Method Summary

Modifier and Type	Method	Description
boolean	updateDominance(T state, int depth, double objValue)	Updates the dominance front at a given depth level based on the provided state.

Methods inherited from class java.lang.Object

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

Constructor Details

SimpleDominanceChecker

public SimpleDominanceChecker(Dominance<T> dominance,
 int nVars)

Constructs a SimpleDominanceChecker with the given dominance relation and number of decision variables.

Parameters:

dominance - the Dominance relation used to compare states

nVars - the number of decision variables or depth levels in the MDD

Method Details

updateDominance

public boolean updateDominance(T state,
 int depth,
 double objValue)

Updates the dominance front at a given depth level based on the provided state.

The method performs the following steps:

1. Retrieves the dominance front corresponding to the given depth.
2. Checks whether the state is dominated by an existing one: if yes, returns true (no insertion).
3. If not dominated, removes all states dominated by the new one, then inserts the new state in the front.

Specified by:

updateDominance in class DominanceChecker<T>

Parameters:

state - the state to evaluate for dominance

depth - the depth (or variable index) in the MDD

objValue - the objective value associated with this state

Returns:

true if the state is dominated and should not be added; false if the state is non-dominated and has been added