Abstract
Recent years have witnessed the emergence of a new area involving hybrid solvers integrating CP- and OR-based methods. The LP relaxation provides bounds on overall solution quality and can be used for pruning in a branch-and-bound approach, especially in domains where we have a combination of linear constraints, well-suited for linear programming (LP) formulations, and discrete constraints, suited for constraint satisfaction problem (CSP) formulations. However, in a purely combinatorial setting, so far it has been surprisingly difficult to integrate LP-based and CSP-based techniques.
We study the behavior of heuristics based on the LP relaxation with respect to the underlying constraindness of the problem. Our study focuses on the Latin square (or quasigroup) completion problem as a prototype for highly combinatorial problems. This problem is NP-hard and it exhibits an easy-hard-easy pattern in complexity, measured in the runtime (backtracks) to find a completion [1]. In our previous work [2] we report an interesting phase transition phenomenon in the solution integrality of the LP relaxation for this problem.
We find that simple techniques based on the LP relaxation of the problem provide satisfactory guidance for under- and over-constrained instances. In the critically constrained region, the performance of such simple techniques degrades, due to the inherit hardness of the problem. In this setting, we examine a technique that recomputes the LP relaxation every time a variable is set. This leads to a significant increase in performance, suggesting that carefully designed “one step at a time” LP-based heuristics could provide suitable guidance even for the hardest instances. We examine the quality of the guidance provided by the LP relaxation as a function of the structure of the problem, i.e., we characterize the performance of LP heuristics across different constraindness regions in the search space.
Research supported by the Intelligent Information Systems Institute, Cornell University (AFOSR grant F49620-01-1-0076).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Achlioptas, D., Gomes, C., Kautz, H., Selman, B.: Generating Satisfiable Instances. In: Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI 2000), New Providence, RI. AAAI Press, Menlo Park (2000)
Leahu, L., Gomes, C.: Quality of lp-based approximations for highly combinatorial problems. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 377–392. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Leahu, L., Gomes, C. (2005). LP as a Global Search Heuristic Across Different Constrainedness Regions. In: van Beek, P. (eds) Principles and Practice of Constraint Programming - CP 2005. CP 2005. Lecture Notes in Computer Science, vol 3709. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11564751_91
Download citation
DOI: https://doi.org/10.1007/11564751_91
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29238-8
Online ISBN: 978-3-540-32050-0
eBook Packages: Computer ScienceComputer Science (R0)