Package org.ddolib.examples.mks

package org.ddolib.examples.mks
The Multidimensional Knapsack Problem (MKP) is a generalization of the KP to multiple capacity constraints: $n$ items and $m$ dimensions of the knapsack are given, each dimension with capacity bound $(C_1,\ldots ,C_m)$. An item $j$ occupies a weight dimension $w^i_j$ in the knapsack for $i\in\{1,\ldots , m\}$ for a value of $v_j$. The goal is to select a subset of items whose sum of profits is maximized so that all the capacity bound constraints hold simultaneously.
  • Classes
    Class
    Description
    MKSDDoMain
    Main class to demonstrate the application of Decision Diagram Optimization (DDO) on a Multi-dimensional Knapsack (MKS) problem instance.
    MKSDistance
    Computes a normalized distance between Multi-dimensional Knapsack (MKS) states.
    MKSDominance
    Implements a dominance relation for Multi-dimensional Knapsack (MKS) states.
    MKSFastLowerBound
    Provides a fast lower bound estimation for Multi-dimensional Knapsack (MKS) states.
    MKSProblem
    Represents a Multi-dimensional Knapsack Problem (MKS) as a Problem for decision diagram optimization.
    MKSRanking
    Ranking strategy for multi-dimensional Knapsack (MKS) states.
    MKSRelax
    Relaxation strategy for the multi-dimensional Knapsack problem (MKS) states.
    MKSState
    Represents the state of a multi-dimensional Knapsack problem (MKS) in terms of the remaining capacities of each knapsack dimension.