TL;DR
This paper introduces DD-LNS, a novel approach that combines Large Neighborhood Search (LNS) with Decision Diagrams (DDs) to efficiently solve complex combinatorial optimization problems. By leveraging DDs to explore large neighborhoods, DD-LNS offers a more generic and potentially optimality-proving alternative to traditional LNS methods, demonstrating competitive performance on challenging scheduling and routing problems.
What Problem Does This Paper Address?
Combinatorial optimization problems, such as finding the best routes for delivery trucks or scheduling production efficiently, are notoriously difficult to solve. Traditional local search methods often get stuck in suboptimal solutions. While techniques like metaheuristics or designing large, problem-specific neighborhoods can help, they often require significant expertise. This paper addresses the challenge of exploring these large neighborhoods in a more generic and automated way, aiming to improve solution quality and even prove optimality for certain instances.
Methods
The core innovation is the DD-LNS approach, which integrates Large Neighborhood Search (LNS) with Decision Diagrams (DDs).
- Large Neighborhood Search (LNS): This is a metaheuristic that works by iteratively destroying a portion of the current solution and then re-optimizing the remaining problem to find a better solution. The key is how it defines and explores the "large neighborhood."
- Decision Diagrams (DDs): DDs are a compact graphical representation of solutions to discrete optimization problems, derived from dynamic programming formulations. They can represent exponentially many solutions in a polynomial space.
- DD-LNS: This method uses DDs to explore the large neighborhood in LNS. Specifically, it compiles a restricted DD from the current best solution. This restricted DD represents a set of solutions that are "close" to the current best. The algorithm then finds the best solution within this DD-generated neighborhood.
- Restricted DDs: To manage the potentially exponential size of DDs, the paper uses "restricted" DDs. These are compiled with a width-bounding procedure that limits the number of nodes at each layer, heuristically selecting the most promising paths. This allows for a trade-off between exploration breadth and computational cost.
- Rough Lower Bounds (RLBs): The approach also incorporates RLBs to prune the search space within the DD compilation. If a partial path in the DD is guaranteed to lead to a solution worse than the current best known, it can be discarded. This helps tighten bounds and potentially prove optimality.
Datasets
The paper evaluates DD-LNS on two types of problems:
- Discrete Lot Sizing and Scheduling Problem (DSLP): The authors used 500 generated instances of DSLP, which were challenging for existing methods. These instances had varying numbers of item types and time horizons.
- Traveling Salesman Problem with Time Windows (TSPTW): For TSPTW, they used 467 instances from standard benchmark suites, which are commonly used to evaluate TSPTW solvers.
Key Insights and Ideas
- DDs as a Generic Neighborhood Explorer: The paper demonstrates that DDs, typically used for exact optimization, can be effectively repurposed as a generic tool to explore large neighborhoods within an LNS framework. This reduces the need for problem-specific neighborhood design.
- Optimality Proof Potential: A significant insight is that DD-LNS can sometimes prove the optimality of solutions. This is achieved when the DD compilation can be performed without restriction (i.e., the DD is "exact") and the best solution found is indeed optimal. This is a rare capability for metaheuristic approaches.
- Tunable Diversification: The maximum width parameter (
W) used in restricted DD compilation provides a direct knob to control the trade-off between intensification (exploring deeper into promising areas) and diversification (exploring wider, different areas of the solution space). - RLBs Enhance Pruning: The integration of rough lower bounds significantly improves the efficiency of DD compilation by allowing for earlier pruning of unpromising solution paths.
Key Results
- DSLP Performance: DD-LNS performed competitively with state-of-the-art Mixed Integer Programming (MIP) models for DSLP, even outperforming simpler MIP formulations. It successfully solved instances that were challenging for other methods.
- TSPTW Performance: DD-LNS showed a slight edge over a constraint programming (CP) based LNS for TSPTW. It proved the optimality of 105 instances and identified 75 new solutions matching the best known. In a separate experiment, it also found 8 improving solutions on standard benchmarks.
- Scalability: The performance generally improved with increasing maximum layer width (
W) up to a certain point, indicating the effectiveness of the tunable diversification.
Limitations and Future Work
- Predicting Optimality Proofs: The paper acknowledges that predicting whether DD-LNS will succeed in proving optimality is undecidable. The success depends on a trade-off between the pruning power of RLBs and the maximum layer width.
- Computational Cost: While DDs offer compactness, their construction can still be computationally intensive, especially for very large problems or when high precision is required.
- Future Work: The authors suggest exploring other relaxation schemes and parameters for DD compilation. Further investigation into how to best leverage RLBs and manage the width-bounding procedure for different problem types would also be valuable. The potential to combine DD-LNS with other metaheuristics or exact methods is also an open avenue.
Summary updated