Approximations and randomization to boost constraint satisfaction problem techniques

Approximations and randomization to boost constraint satisfaction problem techniques

0.00 Avg rating0 Votes
Article ID: iaor2005741
Country: Netherlands
Volume: 130
Issue: 1
Start Page Number: 117
End Page Number: 141
Publication Date: Aug 2004
Journal: Annals of Operations Research
Authors: ,
Keywords: constraint programming
Abstract:

In recent years we have seen an increasing interest in combining constraint satisfaction problem (CSP) formulations and linear programming (LP) based techniques for solving hard computational problems. While considerable progress has been made in the integration of these techniques for solving problems that exhibit a mixture of linear and combinatorial constraints, it has been surprisingly difficult to successfully integrate LP-based and CSP-based methods in a purely combinatorial setting. Our approach draws on recent results on approximation algorithms based on LP relaxations and randomized rounding techniques, with theoretical guarantees, as well as on results that provide evidence that the runtime distributions of combinatorial search methods are often heavy-tailed. We propose a complete randomized backtrack search method for combinatorial problems that tightly couples CSP propagation techniques with randomized LP-based approximations. We present experimental results that show that our hybrid CSP/LP backtrack search method outperforms the pure CSP and pure LP strategies on instances of a hard combinatorial problem.

Reviews

Required fields are marked *. Your email address will not be published.