TitleThe Logic behind Weighted CSP
Publication TypeConference Paper
Year of Publication2007
AuthorsAnsótegui C, Bonet MLuisa, Levy J, Manyà F
Conference NameProc. of the 20th International Joint Conference on Artificial Intelligence, IJCAI'07
PublisherAAAI Press

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.