A Constraint Composite Graph-Based ILP Encoding of the Boolean Weighted CSP
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.
[full text] [slides] [code] [BibTeX▼]
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.