Package org.ddolib.examples.boundedknapsack

package org.ddolib.examples.boundedknapsack
This package implements the acs, astar and ddo models for the Bounded Knapsack Problem (BKS). A bounded knapsack problem is a variation of the classic knapsack problem where each item can be included in the knapsack a limited number of times. Given a knapsack having a maximum (weight) capacity, a set of items {1, ... ,n} where all items of type i have a profit value values_i, a weight weights_i and a quantity quantity_i of identical copies of this item. The goal is to select quantities of each item i, such that the total weight of the selected items does not exceed the knapsack capacity and the total profit is maximized.
  • Class
    Description
    BKSAcsMain
    Bounded Knapsack Problem (BKS) with Acs.
    BKSAstarMain
    Bounded Knapsack Problem (BKS) with AsTar.
    BKSDdoMain
    Bounded Knapsack Problem (BKS) with Ddo.
    BKSDominance
    Implementation of a dominance rule for the Bounded Knapsack (BKS) problem.
    BKSFastLowerBound
    A fast lower bound implementation for the BKSProblem (Bounded Knapsack Problem).
    BKSLnsMain
    Entry point for solving the Bounded Knapsack Problem (BKS) using a Large Neighborhood Search (LNS) approach combined with Decision Diagram Optimization (DDO).
    BKSProblem
    Represents an instance of the Bounded Knapsack Problem (BKP).
    BKSProblem.InstanceType
    Enumeration defining possible correlation types between item weights and profits when generating random instances.
    BKSRanking
    A default state ranking implementation for the Bounded Knapsack Problem (BKP).
    BKSRelax
    A relaxation strategy for the Bounded Knapsack Problem (BKP) used in relaxed decision diagrams.