Two paradigms for combining optimization and satisfiability : Maximum satisfiability and optimum satisfiability problems

Maximum satisfiability (MaxSAT) and optimum satisfiability (OptSAT) problems are two optimization versions of the NP-complete Boolean satisfiability problem. In the literature, these versions have been described and tackled separately by using specialized solvers for each problem. This paper investigates a connection between MaxSAT and OptSAT where each problem can be reduced to the other. We consider several heuristic solvers and different sets of benchmark instances for each problem and investigate whether one class of solvers can tackle instances of the other problem with competitive results. Through computational experiments, we conclude that specialized solvers for one of the problems cannot compete with specialized solvers for the other problem and point out potential improvements of the solvers that are needed to successfully address a wider range of problem instances.