Package org.ddolib.examples.mks

Class MKSProblem

java.lang.Object
org.ddolib.examples.mks.MKSProblem
All Implemented Interfaces:
Problem<MKSState>
public class MKSProblem extends Object implements Problem<MKSState>
Represents a Multi-dimensional Knapsack Problem (MKS) as a Problem for decision diagram optimization.

Each instance defines a set of items, their profits, and weights along multiple dimensions, along with the capacities of the knapsacks. This class supports evaluation of solutions, state transitions, and generation of variable domains.

States in this problem are represented by MKSState, which tracks the remaining capacities in each dimension.

The problem can be constructed either programmatically or loaded from a file. The class also provides an optional known optimal solution for testing purposes.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    final Optional<Double>
    optimal
    Optional known optimal solution value.

  • Constructor Summary

    Constructors
    Constructor
    Description
    MKSProblem(double[] capa, int[] profit, int[][] weight, double optimal)
    Constructs an MKSProblem with the given capacities, profits, and weights.
    MKSProblem(String fname)
    Loads an MKSProblem from a text file.

  • Method Summary

    Modifier and Type
    Method
    Description
    Iterator<Integer>
    domain(MKSState state, int var)
    Returns an iterator over the domain of a variable (item) in a given state.
    double
    evaluate(int[] solution)
    Evaluates the cost of a given solution.
    MKSState
    initialState()
    Returns the initial state for this problem, representing full capacities.
    double
    initialValue()
    Returns the initial value associated with the initial state.
    int
    nbVars()
    Returns the number of decision variables (items).
    Optional<Double>
    optimalValue()
    Returns the optional optimal value (negated to follow minimization conventions in DDO).
    String
    toString()
    Returns a human-readable string representation of the problem, including capacities, items' profits, weights, and known optimal value.
    MKSState
    transition(MKSState state, Decision decision)
    Computes the state resulting from taking a decision in the current state.
    double
    transitionCost(MKSState state, Decision decision)
    Computes the cost of taking a decision in a given state.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • optimal

      public final Optional<Double> optimal
      Optional known optimal solution value.

  • Constructor Details

    • MKSProblem

      public MKSProblem(double[] capa, int[] profit, int[][] weight, double optimal)
      Constructs an MKSProblem with the given capacities, profits, and weights.
      Parameters:
      capa - the capacities of each knapsack dimension
      profit - the profit of each item
      weight - the weight of each item along each dimension
      optimal - the known optimal solution value

    • MKSProblem

      public MKSProblem(String fname) throws IOException
      Loads an MKSProblem from a text file.

      The file format is expected to contain:

      • First line: number of items, number of dimensions, optional optimal value
      • Second line: capacities of each dimension
      • Next lines: profit and weights of each item (profit first, then weights)
      Parameters:
      fname - the path to the file
      Throws:
      IOException - if the file cannot be read

  • Method Details

    • nbVars

      public int nbVars()
      Returns the number of decision variables (items).
      Specified by:
      nbVars in interface Problem<MKSState>
      Returns:
      number of items

    • initialState

      public MKSState initialState()
      Returns the initial state for this problem, representing full capacities.
      Specified by:
      initialState in interface Problem<MKSState>
      Returns:
      initial MKSState

    • initialValue

      public double initialValue()
      Returns the initial value associated with the initial state.
      Specified by:
      initialValue in interface Problem<MKSState>
      Returns:
      0

    • domain

      public Iterator<Integer> domain(MKSState state, int var)
      Returns an iterator over the domain of a variable (item) in a given state.

      An item can be either taken (1) or not taken (0), depending on remaining capacities.

      Specified by:
      domain in interface Problem<MKSState>
      Parameters:
      state - the current MKS state
      var - the index of the variable (item)
      Returns:
      iterator over possible decisions (0 or 1)

    • transition

      public MKSState transition(MKSState state, Decision decision)
      Computes the state resulting from taking a decision in the current state.
      Specified by:
      transition in interface Problem<MKSState>
      Parameters:
      state - the current MKS state
      decision - the decision to apply
      Returns:
      the resulting MKSState after the decision

    • transitionCost

      public double transitionCost(MKSState state, Decision decision)
      Computes the cost of taking a decision in a given state.

      The cost is equal to the negative profit if the item is taken, or 0 otherwise.

      Specified by:
      transitionCost in interface Problem<MKSState>
      Parameters:
      state - the current MKS state
      decision - the decision applied
      Returns:
      the transition cost

    • optimalValue

      public Optional<Double> optimalValue()
      Returns the optional optimal value (negated to follow minimization conventions in DDO).
      Specified by:
      optimalValue in interface Problem<MKSState>
      Returns:
      optional negated optimal value

    • evaluate

      public double evaluate(int[] solution) throws InvalidSolutionException
      Evaluates the cost of a given solution.

      Checks that the solution respects knapsack capacities; if violated, an InvalidSolutionException is thrown.

      Specified by:
      evaluate in interface Problem<MKSState>
      Parameters:
      solution - the selection vector of items (1 = taken, 0 = not taken)
      Returns:
      the negated total profit of the solution
      Throws:
      InvalidSolutionException - if the solution is invalid

    • toString

      public String toString()
      Returns a human-readable string representation of the problem, including capacities, items' profits, weights, and known optimal value.
      Overrides:
      toString in class Object
      Returns:
      string representation of the problem