Package org.ddolib.examples.misp

Class MispLnsMain

java.lang.Object

org.ddolib.examples.misp.MispLnsMain

public class MispLnsMain
extends Object

Entry point for solving the Maximum Independent Set Problem (MISP) using a Large Neighborhood Search (LNS) approach combined with Decision Diagram Optimization (DDO).

The Maximum Independent Set problem consists in selecting a largest possible subset of vertices in a graph such that no two selected vertices are adjacent. In other words, the selected vertices form an independent set.

This class demonstrates how to:

• Load a graph instance (in DOT format)
• Define a LnsModel with problem-specific components
• Use a lower bound heuristic to guide the search
• Apply 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 MISP instance file. If not provided, a default instance is loaded from:

 data/MISP/tadpole_4_2.dot
 

Model Components

• MispProblem – defines the graph structure
• MispFastLowerBound – provides a fast lower bound on the independent set size
• MispDominance – defines dominance relations between states
• SimpleDominanceChecker – applies dominance pruning
• MispRanking – ranks states during decision diagram compilation

Search Configuration

• Search strategy: Large Neighborhood Search (LNS)
• Time limit: 100 milliseconds

No width heuristic is explicitly specified, so default behavior (if provided by the framework) is used.

Output

The program prints:

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

See Also:

• MispProblem
• MispFastLowerBound
• MispDominance
• MispRanking
• 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
MispLnsMain()

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

MispLnsMain

public MispLnsMain()

Method Details

main

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

Main entry point of the program.

Loads a Maximum Independent Set 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 MISP instance file

Throws:

IOException - if the instance file cannot be read