Linear Programming Formulation of the Boolean Satisfiability Problem
arXiv:0808.3386
Abstract
In this paper, we present a new, graph-based modeling approach and a polynomial-sized linear programming (LP) formulation of the Boolean satisfiability problem (SAT). The approach is illustrated with a numerical example.
This paper has been withdrawn. Theorem 38 and Corollary 39 are in error. The modeling needs 9-dimensional z-variables instead of the 8-dimensional variables defined in notations 24.1. The correct modeling is fully detailed in the book available at: http://www.worldscientific.com/worldscibooks/10.1142/9725