MinSAT versus MaxSAT for Optimization Problems

Despite their similarities, MaxSAT and MinSAT use different encodings and solving techniques to cope with optimization problems. In this paper we describe a new weighted partial MinSAT solver, define original MinSAT encodings for relevant combinatorial problems, propose a new testbed for evaluating MinSAT, report on an empirical investigation comparing MinSAT with MaxSAT, and provide new insights into the duality between MinSAT and MaxSAT. © 2013 Springer-Verlag.Peer Reviewe