Proceedings

Improved CP-Based Lagrangian Relaxation Approach with an Application to the TSP

Raphaël Boudreault, Claude-Guy Quimper

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 1374-1380.

https://doi.org/10.24963/ijcai.2021/190

Keywords

  • Constraints and SAT: Constraints: Modeling, Solvers, Applications
  • Constraints and SAT: Constraint Optimization
  • Constraints and SAT: Global Constraints

Abstract

CP-based Lagrangian relaxation (CP-LR) is an efficient optimization technique that combines cost-based filtering with Lagrangian relaxation in a constraint programming context. The state-of-the-art filtering algorithms for the WeightedCircuit constraint that encodes the traveling salesman problem (TSP) are based on this approach. In this paper, we propose an improved CP-LR approach that locally modifies the Lagrangian multipliers in order to increase the number of filtered values. We also introduce two new algorithms based on the latter to filter WeightedCircuit. The experimental results on TSP instances show that our algorithms allow significant gains on the resolution time and the size of the search space when compared to the state-of-the-art implementation.

Raphaël Boudreault, and Claude-Guy Quimper. 2021. Improved CP-Based Lagrangian Relaxation Approach with an Application to the TSP. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 1374–1380. https://doi.org/10.24963/ijcai.2021/190
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards