Package org.ddolib.examples.maximumcoverage

Class MaxCoverLnsMain

java.lang.Object

org.ddolib.examples.maximumcoverage.MaxCoverLnsMain

public class MaxCoverLnsMain
extends Object

Entry point for solving the Maximum Coverage (MaxCover) problem using a Large Neighborhood Search (LNS) approach combined with Decision Diagram Optimization (DDO).

The Maximum Coverage problem consists in selecting at most k subsets from a collection such that the number of covered elements is maximized. Each subset covers a portion of the universe, and the objective is to maximize the union of the selected subsets.

This class demonstrates how to:

• Generate or load a MaxCover instance
• Define a LnsModel with problem-specific components
• Use a ranking heuristic and a lower bound to guide the search
• Control the decision diagram width
• Run a Large Neighborhood Search (LNS) optimization
• Print intermediate and final solutions

Instance Configuration

By default, a random instance is generated with:

• 30 elements (universe size)
• 30 subsets
• Maximum of 7 subsets selected
• Density parameter: 0.1
• Random seed: 42

Alternative constructors (commented in the code) allow using smaller instances or loading from a file.

Model Components

• MaxCoverProblem – defines the MaxCover instance
• MaxCoverRanking – ranks states during decision diagram compilation
• MaxCoverFastLowerBound – provides a fast lower bound on coverage
• FixedWidth – limits the decision diagram width

Search Configuration

• Search strategy: Large Neighborhood Search (LNS)
• Time limit: 1000 milliseconds
• Width heuristic: fixed width of 1000 nodes per layer
• DOT export: disabled

No dominance rule is explicitly defined, so default behavior (if any) from the framework is used.

Output

The program prints:

• The generated problem instance
• Intermediate solutions during the search
• The final best solution found

See Also:

• MaxCoverProblem
• MaxCoverState
• MaxCoverRanking
• MaxCoverFastLowerBound
• 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
MaxCoverLnsMain()

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

MaxCoverLnsMain

public MaxCoverLnsMain()

Method Details

main

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

Main entry point of the program.

Builds or loads a Maximum Coverage instance, configures the LNS model with problem-specific heuristics, and runs the optimization process.

Parameters:

args - command-line arguments (currently unused)

Throws:

IOException - if an input file is used and cannot be read