Package org.ddolib.examples.boundedknapsack

Class BKSProblem

java.lang.Object
org.ddolib.examples.boundedknapsack.BKSProblem
All Implemented Interfaces:
Problem<Integer>
public class BKSProblem extends Object implements Problem<Integer>
Represents an instance of the Bounded Knapsack Problem (BKP).

This class implements the Problem interface and can be used by generic optimization solvers such as Dynamic Decision Diagrams (DD), A*, or Anytime Column Search (ACS).

See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static enum 
    BKSProblem.InstanceType
    Enumeration defining possible correlation types between item weights and profits when generating random instances.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    final int
    capacity
     
    final int[]
    quantities
     
    final int[]
    values
     
    final int[]
    weights
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    BKSProblem(int capacity, int[] values, int[] weights, int[] quantities)
    Constructs a bounded knapsack problem from explicitly given parameters.
    BKSProblem(int n, int range, BKSProblem.InstanceType type, long seed)
    Randomly generates an instance of the bounded knapsack problem.

  • Method Summary

    Modifier and Type
    Method
    Description
    Iterator<Integer>
    domain(Integer state, int var)
    Returns the domain (set of possible values) for a given variable (item), given the current remaining capacity.
    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, which corresponds to the remaining capacity of the knapsack before adding any items.
    double
    initialValue()
    Returns the initial objective value of the problem.
    int
    nbVars()
    Returns the number of variables (items) in the knapsack.
    String
    toString()
     
    Integer
    transition(Integer state, Decision decision)
    Computes the next state after making a decision on an item.
    double
    transitionCost(Integer state, Decision decision)
    Computes the transition cost associated with a decision.

    Methods inherited from class java.lang.Object

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

    Methods inherited from interface org.ddolib.modeling.Problem

    optimalValue

  • Field Details

    • capacity

      public final int capacity

    • values

      public final int[] values

    • weights

      public final int[] weights

    • quantities

      public final int[] quantities

  • Constructor Details

    • BKSProblem

      public BKSProblem(int capacity, int[] values, int[] weights, int[] quantities)
      Constructs a bounded knapsack problem from explicitly given parameters.
      Parameters:
      capacity - the total capacity of the knapsack
      values - an array containing the profit (value) of each item
      weights - an array containing the weight of each item
      quantities - an array containing the maximum available quantity of each item

    • BKSProblem

      public BKSProblem(int n, int range, BKSProblem.InstanceType type, long seed)
      Randomly generates an instance of the bounded knapsack problem.

      The generated instance is controlled by a type of correlation between item weights and values, as described in BKSProblem.InstanceType.

      Parameters:
      n - the number of items
      range - the upper bound for weights and profits
      type - the correlation type between weight and profit
      seed - the random seed used for reproducibility

  • Method Details

    • nbVars

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

    • initialState

      public Integer initialState()
      Returns the initial state of the problem, which corresponds to the remaining capacity of the knapsack before adding any items.
      Specified by:
      initialState in interface Problem<Integer>
      Returns:
      the initial remaining capacity

    • initialValue

      public double initialValue()
      Returns the initial objective value of the problem.
      Specified by:
      initialValue in interface Problem<Integer>
      Returns:
      the initial value (0.0)

    • domain

      public Iterator<Integer> domain(Integer state, int var)
      Returns the domain (set of possible values) for a given variable (item), given the current remaining capacity.

      For each item, the decision variable represents the number of copies to include in the knapsack, constrained by both available quantity and remaining capacity.

      Specified by:
      domain in interface Problem<Integer>
      Parameters:
      state - the current remaining capacity
      var - the index of the item
      Returns:
      an iterator over possible quantities for the given item

    • transition

      public Integer transition(Integer state, Decision decision)
      Computes the next state after making a decision on an item.
      Specified by:
      transition in interface Problem<Integer>
      Parameters:
      state - the current remaining capacity
      decision - the decision specifying which item and how many copies to include
      Returns:
      the updated remaining capacity after including the chosen number of items

    • transitionCost

      public double transitionCost(Integer state, Decision decision)
      Computes the transition cost associated with a decision.

      Since this problem is typically formulated as a maximization, this method returns the negative profit to fit a minimization framework.

      Specified by:
      transitionCost in interface Problem<Integer>
      Parameters:
      state - the current remaining capacity
      decision - the decision specifying which item and how many copies to include
      Returns:
      the negative profit of the chosen items

    • 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.

    • toString

      public String toString()
      Overrides:
      toString in class Object