CSPSAT 2014: Invited Talk

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.