Abstract
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.
This work was supported by the Intelligent Information Systems Institute, Cornell University (AFOSR grant F49620-01-1-0076).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahuja, R.K., Magnati, T.L., Orlin, J.B.: Network Flows. Prentice-Hall, Englewood Cliffs (1993)
Apt, K.R.: The Rough Guide to Constraint Propagation. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 1–23. Springer, Heidelberg (1999)
Barahona, F., Anbil, R.: The Volume Algorithm: producing primal solutions with a subgradient algorithm. Mathematical Programming 87, 385–399 (2000)
Caseau, Y., Laburthe, F.: Solving Small TSPs with Constraints. In: 14th International Conference on Logic Programming (ICLP), pp. 316–330. The MIT Press, Cambridge (1997)
Crowder, H.: Computational improvements for subgradient optimization. Symposia Mathematica XIX, 357–372 (1976)
Everett, H.: Generalized lagrange multiplier method for solving problems of optimum allocation of resource. Operations Research 11, 399–417 (1963)
Fahle, T., Sellmann, M.: Cost-Based Filtering for the Constrained Knapsack Problem. Annals of Operations Research 115, 73–93 (2002)
Focacci, F., Lodi, A., Milano, M.: Cutting Planes in Constraint Programming: an hybrid approach. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 187–201. Springer, Heidelberg (2000)
Focacci, F., Lodi, A., Milano, M.: Cost-Based Domain Filtering. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 189–203. Springer, Heidelberg (1999)
Focacci, F., Lodi, A., Milano, M.: Solving TSP through the Integration of OR and CP Techniques. In: Workshop on Large Scale Combinatorial Optimization and Constraints. Electronic Notes in Discrete Mathematics (1998)
Frangioni, A.: A Bundle type Dual-ascent Approach to Linear Multi-Commodity Min Cost Flow Problems. Technical Report, Dipartimento di Informatica, Universita di Pisa, TR-96-01 (1996)
Frangioni, A.: Dual Ascent Methods and Multicommodity Flow Problems. Doctoral Thesis, Dipartimento di Informatica, Universita di Pisa, TD-97-05 (1997)
Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees. Operations Research 18, 1138–1162 (1970)
Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees: Part II. Mathematical Programming 1, 6–25 (1971)
Kelley, J.E.: The Cutting Plane Method for Solving Convex Programs. Journal of the SIAM 8, 703–712 (1960)
Kliewer, G., Sellmann, M., Koberstein, A.: Solving the capacitated network design problem in parallel. In: 3rd meeting of the PAREO Euro working group on Parallel Processing in Operations Research, PAREO (2002)
Martello, S., Toth, P.: An exact algorithm for the Two-Constraint 0-1 Knapsack Problem. Operations Research 51, 826–835 (2003)
Ottosson, G., Thorsteinsson, E.S.: Linear Relaxation and Reduced-Cost Based Propagation of Continuous Variable Subscripts. 2nd International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR), Paderborn Center for Parallel Computing, Technical Report tr-001-2000, pp. 129–138 (2000)
Sellmann, M.: The Practice of Approximated Consistency for Knapsack Constraints. In: National Conference on Artificial Intelligence, AAAI (2004) (to appear)
Sellmann, M.: Approximated Consistency for Knapsack Constraints. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 679–693. Springer, Heidelberg (2003)
Sellmann, M.: Cost-Based Filtering for Shorter Path Constraints. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 694–708. Springer, Heidelberg (2003)
Sellmann, M.: Pruning Techniques in Constraint Programming and Combinatorial Optimization. Ph.D. Thesis, University of Paderborn (2002)
Sellmann, M., Fahle, T.: CP-Based Lagrangian Relaxation for a Multimedia Application. In: 3rd International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR), pp. 1–14 (2001)
Sellmann, M., Fahle, T.: Coupling Variable Fixing Algorithms for the Automatic Recording Problem. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 134–145. Springer, Heidelberg (2001)
Sellmann, M., Fahle, T.: Constraint Programming Based Lagrangian Relaxation for the Automatic Recording Problem. Annals of Operations Research 118, 17–33 (2003)
Sellmann, M., Kliewer, G., Koberstein, A.: Lagrangian Cardinality Cuts and Variable Fixing for Capacitated Network Design. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 845–858. Springer, Heidelberg (2002)
Trick, M.: A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints. In: 3rd International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR), pp. 113–124 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sellmann, M. (2004). Theoretical Foundations of CP-Based Lagrangian Relaxation. In: Wallace, M. (eds) Principles and Practice of Constraint Programming – CP 2004. CP 2004. Lecture Notes in Computer Science, vol 3258. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30201-8_46
Download citation
DOI: https://doi.org/10.1007/978-3-540-30201-8_46
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23241-4
Online ISBN: 978-3-540-30201-8
eBook Packages: Springer Book Archive