Package org.ddolib.modeling

Interface Dominance<T>

Type Parameters:
T - the type representing the problem state
All Known Implementing Classes:
BKSDominance, KSDominance, MaxCoverDominance, MispDominance, MKSDominance, MSCTDominance, SMICDominance, TSPTWDominance
public interface Dominance<T>
Defines a dominance relation used to compare and prune states during the exploration of decision diagrams or search spaces.

A Dominance relation provides a way to determine whether one state of the problem is at least as good as (i.e., dominates) another, allowing the solver to discard redundant or inferior subproblems.

The dominance check is an essential optimization mechanism in decision diagram–based solvers, as it helps reduce the search space by recognizing equivalent or dominated states that do not need to be further expanded.

  • Method Summary

    Modifier and Type
    Method
    Description
    Object
    getKey(T state)
    Returns a canonical key associated with a given state.
    boolean
    isDominatedOrEqual(T state1, T state2)
    Tests whether state1 is dominated by or equivalent to state2.

  • Method Details

    • getKey

      Object getKey(T 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.

      Parameters:
      state - the state for which a dominance key is requested
      Returns:
      an object uniquely (or canonically) representing the given state

    • isDominatedOrEqual

      boolean isDominatedOrEqual(T state1, T state2)
      Tests 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.

      Parameters:
      state1 - the first state to compare
      state2 - the second state to compare against
      Returns:
      true if state1 is dominated by or equivalent to state2; false otherwise