Hong Xu, Sven Koenig, and T. K. Satish Kumar. A constraint composite graph-based ILP encoding of the Boolean weighted CSP. In Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming (CP), 630–638. 2017. doi:10.1007/978-3-319-66158-2_40.
[full text] [slides] [BibTeX▼]

Abstract

The weighted constraint satisfaction problem (WCSP) occurs in the crux of many real-world applications of operations research, artificial intelligence, bioinformatics, etc. Despite its importance as a combinatorial substrate, many attempts for building an efficient WCSP solver have been largely unsatisfactory. In this paper, we introduce a new method for encoding a (Boolean) WCSP instance as an integer linear program (ILP). This encoding is based on the idea of the constraint composite graph (CCG) associated with a WCSP instance. We show that our CCG-based ILP encoding of the Boolean WCSP is significantly more efficient than previously known ILP encodings. Theoretically, we show that the CCG-based ILP encoding has a number of interesting properties. Empirically, we show that it allows us to solve many hard Boolean WCSP instances that cannot be solved by ILP solvers with previously known ILP encodings.

Presentation

Full Text

Your browser does not support viewing the PDF file inline. Please click the link below to download the file.

[download]