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.

Dr. Xing received his Ph.D. degree from Washington University in St. Louis in 2008. His research interests include heuristic search, SAT, and AI planning. He is the author of more than 15 refereed publications, and a winner of International Planning Competitions. In his spare time, Dr. Xing likes swimming, history, and value investing.