The Logic behind Weighted CSP

Carlos Ansotegui, Maria Luisa Bonet, Jordi Levy, Felip Manya

We define a translation from Weighted CSP to signed Max-SAT, and a complete resolution-style calculus for solving signed Max-SAT. Based on these results, we then describe an original exact algorithm for solving Weighted CSP. Finally, we define several derived rules and prove that they enforce the main soft arc consistency defined in the literature when applied to Weighted CSP instances.

Subjects: 15.2 Constraint Satisfaction; 3. Automated Reasoning

Submitted: Oct 16, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.