Package org.ddolib.examples.knapsack

Class KSDominance

java.lang.Object
org.ddolib.examples.knapsack.KSDominance
All Implemented Interfaces:
Dominance<Integer>
public class KSDominance extends Object implements Dominance<Integer>
Dominance relation for the Knapsack Problem (KS).

This dominance checker is used to prune the search space in a decision diagram or other solver by identifying states that are dominated and can therefore be discarded.

In this implementation:

  • getKey(Integer) always returns 0, indicating a single dominance key for all states.
  • isDominatedOrEqual(Integer, Integer) considers a state capa1 dominated by capa2 if capa1 <= capa2, i.e., a knapsack state with less or equal remaining capacity is dominated by one with more remaining capacity.

  • Constructor Details

    • KSDominance

      public KSDominance()

  • Method Details

    • getKey

      public Integer getKey(Integer capa)
      Returns the key used for grouping states in the dominance checker.
      Specified by:
      getKey in interface Dominance<Integer>
      Parameters:
      capa - the current state (remaining capacity)
      Returns:
      0, indicating a single key for all states

    • isDominatedOrEqual

      public boolean isDominatedOrEqual(Integer capa1, Integer capa2)
      Checks whether one state is dominated by another.
      Specified by:
      isDominatedOrEqual in interface Dominance<Integer>
      Parameters:
      capa1 - the first state (remaining capacity)
      capa2 - the second state (remaining capacity)
      Returns:
      true if capa1 <= capa2, otherwise false