Package org.ddolib.examples.lcs

Class LCSLnsMain

java.lang.Object

org.ddolib.examples.lcs.LCSLnsMain

public class LCSLnsMain
extends Object

Entry point for solving the Longest Common Subsequence (LCS) problem using a Large Neighborhood Search (LNS) approach combined with Decision Diagram Optimization (DDO).

The Longest Common Subsequence problem consists in finding the longest sequence of symbols that appears in the same relative order (not necessarily contiguous) in a set of input sequences.

This class demonstrates how to:

• Load an LCS instance from a file
• Define a LnsModel with problem-specific components
• Use a lower bound heuristic to guide the search
• 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 an LCS instance file. If not provided, a default test instance is loaded from:

 src/test/resources/LCS/LCS_3_3_10_test.txt
 

Model Components

• LCSProblem – defines the LCS instance
• LCSFastLowerBound – provides a fast lower bound on the LCS length
• LCSRanking – ranks states during decision diagram compilation

Search Configuration

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

Note that no dominance rule or width heuristic is explicitly defined here, meaning default behaviors (if any) from the underlying framework are used.

Output

The program prints:

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

See Also:

• LCSProblem
• LCSState
• LCSFastLowerBound
• LCSRanking
• 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
LCSLnsMain()

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

LCSLnsMain

public LCSLnsMain()

Method Details

main

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

Main entry point of the program.

Loads an LCS instance, configures the LNS model with problem-specific heuristics, and runs the optimization process.

Parameters:

args - optional command-line arguments:

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

Throws:

IOException - if the instance file cannot be read