×

Quality of LP-based approximations for highly combinatorial problems. (English) Zbl 1152.68564

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, 377-392 (2004).
Summary: We study the quality of LP-based approximation methods for pure combinatorial problems. We found that the quality of the LP-relaxation is a direct function of the underlying constrainedness of the combinatorial problem. More specifically, we identify a novel phase transition phenomenon in the solution integrality of the relaxation. The solution quality of approximation schemes degrades substantially near phase transition boundaries. Our findings are consistent over a range of LP-based approximation schemes. We also provide results on the extent to which LP relaxations can provide a global perspective of the search space and therefore be used as a heuristic to guide a complete solver.
For the entire collection see [Zbl 1139.68008].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI