Introduction
In many real-world scenarios, optimization problems must be solved under strict time constraints. Whether managing dynamic computer networks or scheduling emergency services, decision-makers often require high-quality solutions almost immediately. This paper introduces VNS/LDS+CP, a hybrid algorithm designed specifically for these "anytime" contexts, where the goal is to provide the best possible solution at any moment of interruption.
The Anytime Challenge
Traditional Constraint Programming (CP) excels at proving optimality but often struggles to find even an initial feasible solution quickly in large search spaces. Conversely, stochastic local search methods are fast but prone to getting trapped in local minima and lack the pruning power of CP. The authors, Samir Loudni and Patrice Boizumault, bridge this gap by combining the global exploration of metaheuristics with the rigorous search and pruning capabilities of CP.
The VNS/LDS+CP Hybrid
The core of the proposed method is an intertwined hybridization of three techniques:
- Variable Neighborhood Search (VNS): Acts as the outer loop, starting with an initial solution and iteratively "relaxing" (unassigning) a subset of variables. If the search plateaus, VNS increases the neighborhood size to explore broader regions of the solution space.
- Limited Discrepancy Search (LDS): Used to rebuild the relaxed portion of the solution. LDS follows a greedy heuristic but allows for a controlled number of deviations (discrepancies), effectively exploring the most promising branches of the search tree first.
- Constraint Propagation (CP): Integrated into the rebuilding phase to calculate lower bounds. By pruning branches that cannot improve upon the current best solution, CP significantly reduces the computational effort required for local moves.
The effectiveness of this hybrid approach is highly dependent on its parameters. As shown in the figure above, the authors identified that a discrepancy limit of d=4 typically offers the best balance between exploration and exploitation. Furthermore, the choice of propagation scheme (e.g., PFC-DAC) plays a crucial role in the algorithm's ability to prune the search space effectively.
Experimental Evaluation
The authors evaluated VNS/LDS+CP using two primary benchmarks:
- CELAR Benchmarks: Standard industry problems based on the Radio Link Frequency Assignment Problem (RLFAP), specifically instances 6, 7, and 6-Sub 1.
- ATM Network Resource Allocation: A real-world connection demand planning problem provided by France Telecom R&D.
Key Results and Insights
The experimental results demonstrate that VNS/LDS+CP consistently outperforms standard methods like Simulated Annealing (SA) and other Large Neighborhood Search (LNS) variants.
Key findings include:
- Superior Convergence: On CELAR Instance 6, the method achieved a 9% quality improvement in just 2 seconds compared to standard LNS. The algorithm exhibits a desirable "diminishing returns" property, finding high-quality solutions very rapidly before entering a refinement phase.
- Real-World Impact: In the ATM network application, the algorithm successfully rerouted connections to accept 67% of demands that were previously rejected by greedy approaches.
- Robustness: The optimal parameter settings remained stable across different problem instances, indicating that the method is robust and does not require extensive per-problem tuning.
Conclusion and Future Work
VNS/LDS+CP represents a significant step forward in anytime optimization, proving that the integration of CP-based pruning into local search can yield dramatic performance gains. While the algorithm eventually reaches a plateau, future work could involve implementing intelligent restart mechanisms, using "nogoods" to avoid redundant search, or developing meta-level controllers to adapt the search strategy dynamically.
Summary updated