Package org.ddolib.examples.knapsack

Class KSProblem

java.lang.Object
org.ddolib.examples.knapsack.KSProblem
All Implemented Interfaces:
Problem<Integer>
public class KSProblem extends Object implements Problem<Integer>
Represents an instance of the Knapsack Problem (KS).

The state of the problem is the remaining capacity of the knapsack (represented as an Integer). Decisions correspond to selecting or not selecting a specific item (1 for selected, 0 for not selected).

This class supports creating instances from:

  • Explicit arrays of profits and weights, with or without a known optimal value.
  • A file formatted with the number of items, capacity, (optional) optimal value, and a list of item profits and weights.

Costs are negated profits to allow using solvers designed for minimization.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    final int
    capa
    Maximum capacity of the knapsack.
    final Optional<String>
    name
    Optional name of the instance (usually the filename).
    final Optional<Double>
    optimal
    Optional known optimal solution value.
    final int[]
    profit
    Profits of the items.
    final int[]
    weight
    Weights of the items.

  • Constructor Summary

    Constructors
    Constructor
    Description
    KSProblem(int capa, int[] profit, int[] weight)
    Constructs a Knapsack problem with given capacity, profits, and weights.
    KSProblem(int capa, int[] profit, int[] weight, double optimal)
    Constructs a Knapsack problem with given capacity, profits, weights, and known optimal value.
    KSProblem(String fname)
    Constructs a Knapsack problem from a file.

  • Method Summary

    Modifier and Type
    Method
    Description
    Iterator<Integer>
    domain(Integer state, int var)
    Returns the domain of possible values for a given variable when applied to a specific state.
    double
    evaluate(int[] solution)
    Given a solution such that solution[i] is the value of the variable x_i, returns the value of this solution and checks if the solution respects the problem's constraints.
    Integer
    initialState()
    Returns the initial state of the problem.
    double
    initialValue()
    Returns the initial objective value associated with the initial state.
    int
    nbVars()
     
    Optional<Double>
    optimalValue()
    Returns the known optimal value of the problem, if available.
    String
    toString()
     
    Integer
    transition(Integer state, Decision decision)
    Applies a decision to a state, computing the next state according to the problem's transition function.
    double
    transitionCost(Integer state, Decision decision)
    Computes the change in objective value resulting from applying a decision to a given state.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • capa

      public final int capa
      Maximum capacity of the knapsack.

    • profit

      public final int[] profit
      Profits of the items.

    • weight

      public final int[] weight
      Weights of the items.

    • optimal

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

    • name

      public final Optional<String> name
      Optional name of the instance (usually the filename).

  • Constructor Details

    • KSProblem

      public KSProblem(int capa, int[] profit, int[] weight, double optimal)
      Constructs a Knapsack problem with given capacity, profits, weights, and known optimal value.
      Parameters:
      capa - maximum capacity of the knapsack
      profit - array of item profits
      weight - array of item weights
      optimal - known optimal value

    • KSProblem

      public KSProblem(int capa, int[] profit, int[] weight)
      Constructs a Knapsack problem with given capacity, profits, and weights. No optimal value is provided.
      Parameters:
      capa - maximum capacity of the knapsack
      profit - array of item profits
      weight - array of item weights

    • KSProblem

      public KSProblem(String fname) throws IOException
      Constructs a Knapsack problem from a file.

      The file format should contain:

      • First line: number of items, capacity, (optional) optimal value.
      • Following lines: item profit and weight for each item.
      Parameters:
      fname - path to the file
      Throws:
      IOException - if an I/O error occurs while reading the file

  • Method Details

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • nbVars

      public int nbVars()
      Specified by:
      nbVars in interface Problem<Integer>
      Returns:
      the total number of decision variables in this problem

    • initialState

      public Integer initialState()
      Description copied from interface: Problem
      Returns the initial state of the problem.
      Specified by:
      initialState in interface Problem<Integer>
      Returns:
      the state representing the starting point of the optimization

    • initialValue

      public double initialValue()
      Description copied from interface: Problem
      Returns the initial objective value associated with the initial state.
      Specified by:
      initialValue in interface Problem<Integer>
      Returns:
      the starting value of the objective function

    • domain

      public Iterator<Integer> domain(Integer state, int var)
      Description copied from interface: Problem
      Returns the domain of possible values for a given variable when applied to a specific state.
      Specified by:
      domain in interface Problem<Integer>
      Parameters:
      state - the current state
      var - the variable index whose domain is queried
      Returns:
      an iterator over all feasible values for the variable in this state

    • transition

      public Integer transition(Integer state, Decision decision)
      Description copied from interface: Problem
      Applies a decision to a state, computing the next state according to the problem's transition function.
      Specified by:
      transition in interface Problem<Integer>
      Parameters:
      state - the state from which the transition originates
      decision - the decision to apply
      Returns:
      the resulting state after applying the decision

    • transitionCost

      public double transitionCost(Integer state, Decision decision)
      Description copied from interface: Problem
      Computes the change in objective value resulting from applying a decision to a given state.
      Specified by:
      transitionCost in interface Problem<Integer>
      Parameters:
      state - the state from which the transition originates
      decision - the decision to apply
      Returns:
      the incremental objective cost/value associated with this decision

    • optimalValue

      public Optional<Double> optimalValue()
      Description copied from interface: Problem
      Returns the known optimal value of the problem, if available.

      Note: This value should correspond to the expected output of the solver. For maximization problems, be careful with negative values.

      Specified by:
      optimalValue in interface Problem<Integer>
      Returns:
      an Optional containing the known optimal value, or empty if unknown

    • evaluate

      public double evaluate(int[] solution) throws InvalidSolutionException
      Description copied from interface: Problem
      Given a solution such that solution[i] is the value of the variable x_i, returns the value of this solution and checks if the solution respects the problem's constraints.

      Note: For maximization problems, the returned value is minus the computed value.

      Specified by:
      evaluate in interface Problem<Integer>
      Parameters:
      solution - A solution of the problem.
      Returns:
      The value of the input solution
      Throws:
      InvalidSolutionException - If the solution does not respect problem's constraints.