Package org.ddolib.examples.mks

Class MKSDominance

java.lang.Object
org.ddolib.examples.mks.MKSDominance
All Implemented Interfaces:
Dominance<MKSState>
public class MKSDominance extends Object implements Dominance<MKSState>
Implements a dominance relation for Multi-dimensional Knapsack (MKS) states.

In this dominance relation, one state state1 is considered dominated by or equal to another state state2 if, in every dimension, state1 has less than or equal remaining capacity compared to state2.

This is useful for pruning the search space in decision diagram optimization: dominated states can be safely discarded without losing optimality.

  • Constructor Details

    • MKSDominance

      public MKSDominance()

  • Method Details

    • getKey

      public Integer getKey(MKSState state)
      Returns a key for grouping states in dominance checks.

      Here, all states share the same key (0), meaning that all states are comparable for dominance against each other.

      Specified by:
      getKey in interface Dominance<MKSState>
      Parameters:
      state - the state
      Returns:
      the key for dominance grouping (always 0)

    • isDominatedOrEqual

      public boolean isDominatedOrEqual(MKSState state1, MKSState state2)
      Determines whether state1 is dominated by or equal to state2.

      state1 is dominated if its remaining capacity in every dimension is less than or equal to the corresponding capacity in state2.

      Specified by:
      isDominatedOrEqual in interface Dominance<MKSState>
      Parameters:
      state1 - the first state to compare
      state2 - the second state to compare
      Returns:
      true if state1 is dominated by or equal to state2, false otherwise