CSPSAT 2014 – Fourth International Workshop on the Cross-Fertilization Between CSP and SAT
July 18, 2014 · Vienna, Austria
MaxSat and SoftCSPs
Fahiem Bacchus, University of Toronto, Canada
The formalisms for MaxSat and SoftCSPs are strongly related
much like SAT and CP. Both address the problem of constrained
optimization. The formalism that is the 800-kg gorilla of this area is
Mixed Integer Programming (MIPS). Of these three formalisms the
technology for solving MIPs is the most developed, although MaxSat and
SoftCSP solvers have also made significant progress. All three
formalisms have focused on exploiting quite distinct algorithmic
methods, and empirical evidence indicates that each of these
formalisms can dominate the others on particular problems. A
promising research direction is to explore the hybridization of these
formalisms, and in this talk I will discuss some of the work that has
been done and that is yet to be done in exploiting the disparate
strengths of these formalisms.