zbMATH — the first resource for mathematics

Theoretical foundations of CP-based Lagrangian relaxation. (English) Zbl 1152.68584
Wallace, Mark (ed.), Principles and practice of constraint programming – CP 2004. 10th international conference, CP 2004, Toronto, Canada, September 27–October 1, 2004. Proceedings. Berlin: Springer (ISBN 978-3-540-23241-4/pbk). Lecture Notes in Computer Science 3258, 634-647 (2004).
Summary: CP-based Lagrangian Relaxation allows us to reason on local substructures while maintaining a global view on an entire optimization problem. While the idea of cost-based filtering with respect to systematically changing objective functions has been around for more than three years now, so far some important observations have not been explained. In this paper, we prove a simple theorem that explains a variety of effects that are encountered in practice, the most counter-intuitive being the fact that suboptimal Lagrangian multipliers can have stronger filtering abilities than optimal ones.
For the entire collection see [Zbl 1139.68008].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI