Carla P. Gomes and David Shmoys
In recent years we have seen the development of suc-cessful methods for solving optimization problems by inte-grating techniques from Constraint Programming (CP) and Operations research (OR). Such hybrid approaches draw the individual strengths of these different paradigms: OR heavily relies on mathematical programming formulations such as integer and linear programming, while CP uses constrained-based search and inference methods. This is particularly true 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. Nevertheless, in a purely combinatorial setting, so far it has been suprisingly difficult to integrate LP-based and CSP-based techniques. For example, despite a significant amount of work on using LP relaxations to solve Boolean satisfia-bility (SAT) problems, practical state-of-the-art solvers not incorporate LP relaxation techniques. From a practical point of view, the challenge is how to integrate such tech-niques into practical solvers. The basic idea is to use the information from LP relaxations to guide the combinatorial search process. A key issue is whether the LP relaxation provides useful additional information that is not already un-covered by constraint propagation and inference techniques. Of course, also the cost of solving the LP relaxation should not outweigh the benefits in terms of reduction in search cost. We present a complete randomized backtrack search method that tightly couples CSP propagation techniques with randomized LP rounding. Our approach draws on re-cent results on some of the best approximation algorithms with theoretical guarantees based on LP relaxations and ran-domized rounding techniques, as well on results that uncov-ered the extreme variance or "unpredictability" in the run-ning time of complete search procedures, often explained by the phenomenon of heavy-tailed cost distributions.