Searching for Optimization through Satisfiability

This book studies two optimization problems, maximum satisfiability and planing of satisfiability. The maximum satisfiability problem (max-SAT) is the optimization counterpart of the satisfiability problem (SAT). The goal of max-SAT is to maximize the number of clauses satisfied. planning as satisfiability is a class of planning aiming to achieve a plan with optimal resource, cost, or makespan by using the SAT approach. We present a mix- SAT formulation for these two optimization problems and examine to extend the Davis-Putnam-Logemann- Loveland (DPLL) procedure, which is the basic framework for the original SAT problem, for this mix- SAT formulation. We progressively develop a series of algorithms and reconsider many general SAT techniques for these two optimization problems.