Package org.ddolib.examples.boundedknapsack

Class BKSLnsMain

java.lang.Object

org.ddolib.examples.boundedknapsack.BKSLnsMain

public class BKSLnsMain
extends Object

Entry point for solving the Bounded Knapsack Problem (BKS) using a Large Neighborhood Search (LNS) approach combined with Decision Diagram Optimization (DDO).

The Bounded Knapsack Problem consists in selecting quantities of items (each with a profit, weight, and upper bound) such that the total weight does not exceed the knapsack capacity while maximizing the total profit.

This class demonstrates how to:

• Generate a synthetic BKS instance
• Define a LnsModel with problem-specific components
• Incorporate dominance rules to prune the search space
• Run a Large Neighborhood Search (LNS) optimization
• Print intermediate and final solutions

Instance Configuration

• Number of items: 35
• Knapsack capacity: 100
• Instance type: strongly correlated profits and weights
• Random seed: 0

Model Components

• BKSProblem – defines the knapsack instance
• BKSFastLowerBound – provides a fast lower bound estimation
• BKSDominance – defines dominance relations between states
• SimpleDominanceChecker – applies dominance pruning
• BKSRanking – ranks states during decision diagram compilation
• FixedWidth – limits the decision diagram width

Search Configuration

• Search strategy: Large Neighborhood Search (LNS)
• Time limit: 10,000 milliseconds
• Width heuristic: fixed width of 100 nodes per layer

Output

The program prints:

• Intermediate solutions during the search
• Final solution statistics
• The best solution found

See Also:

• BKSProblem
• BKSFastLowerBound
• BKSDominance
• BKSRanking
• LnsModel
• Solvers.minimizeLns(org.ddolib.modeling.LnsModel<T>, java.util.function.Predicate<org.ddolib.common.solver.SearchStatistics>, java.util.function.BiConsumer<int[], org.ddolib.common.solver.SearchStatistics>)
• Solution

Constructor Summary

Constructors

Constructor	Description
BKSLnsMain()

Method Summary

Modifier and Type	Method	Description
static void	main(String[] args)	Main entry point of the program.

Methods inherited from class java.lang.Object

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

Constructor Details

BKSLnsMain

public BKSLnsMain()

Method Details

main

public static void main(String[] args)

Main entry point of the program.

Builds a BKS instance, configures the LNS model with problem-specific heuristics and dominance rules, and runs the optimization process.

Parameters:

args - command-line arguments (currently unused)