file.pdf (280.98 kB)
Download file

On Solving Boolean Combinations of UTVPI Constraints

Download (280.98 kB)
journal contribution
posted on 01.06.2006, 00:00 by Sanjit A. Seshia, K. Subramani, Randal E. Bryant
We consider the satis fiability problem for Boolean combinations of unit two variable per inequality (UTVPI) constraints. Our result can be used in a nite instantiation-based approach to deciding satis ability of UTVPI formulas. An experimental evaluation demonstrates the eciency of such an approach. One of our key results is to show that an integer point inside a UTVPI polyhedron, if one exists, can be obtained by rounding a vertex. As a corollary of this result, we also obtain a polynomial-time algorithm for approximating optima of UTVPI integer programs to within an additive factor.