Package org.ddolib.examples.knapsack

Class KSLnsMain

java.lang.Object

org.ddolib.examples.knapsack.KSLnsMain

public class KSLnsMain
extends Object

Entry point for solving the 0/1 Knapsack Problem (KS) using a Large Neighborhood Search (LNS) approach combined with Decision Diagram Optimization (DDO).

The 0/1 Knapsack Problem consists in selecting a subset of items, each with a weight and a profit, such that the total weight does not exceed the knapsack capacity while maximizing the total profit. Each item can be selected at most once.

This class demonstrates how to:

• Load a knapsack instance from a file
• Define a LnsModel with problem-specific components
• Use dominance rules to prune suboptimal states
• Run a Large Neighborhood Search (LNS) optimization
• Print intermediate and final solutions

Execution

The program accepts an optional command-line argument specifying the path to a knapsack instance file. If not provided, a default instance is loaded from:

 data/Knapsack/instance_n1000_c1000_10_5_10_5_0
 

Model Components

• KSProblem – defines the knapsack instance
• KSFastLowerBound – provides a fast lower bound estimation
• KSDominance – defines dominance relations between states
• SimpleDominanceChecker – applies dominance pruning
• KSRanking – ranks states during decision diagram compilation
• FixedWidth – limits the decision diagram width

Search Configuration

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

Output

The program prints:

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

See Also:

• KSProblem
• KSFastLowerBound
• KSDominance
• KSRanking
• 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
KSLnsMain()

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

KSLnsMain

public KSLnsMain()

Method Details

main

public static void main(String[] args)
                 throws IOException

Main entry point of the program.

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

Parameters:

args - optional command-line arguments:

• args[0] – path to the knapsack instance file

Throws:

IOException - if the instance file cannot be read