Solving Constraint Optimization Problems in Anytime Contexts

Samir Loudni, Patrice BoizumaultIJCAI 2003

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:

  1. 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.
  2. 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.
  3. 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.
Influence of discrepancy and propagation scheme on algorithm performance.

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.

Comparison of VNS/LDS+CP against Simulated Annealing and LNS variants on CELAR Instance 6.

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

BibTeX
@inproceedings{loudni2003solving,
  author = {Samir Loudni and Patrice Boizumault},
  title = {{Solving Constraint Optimization Problems in Anytime Contexts}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
}
Figure