Efficient Binary Linear Programming Formulations for Boolean Functions

  • Frank Gurski University of Duesseldorf

Abstract

A very useful tool when designing linear programs for optimization problems is the formulation of logical operations by linear programming constraints. We give efficient linear programming formulation of important n-ary boolean functions f(x_1,\ldots,x_n)=x_{n+1} such as conjunction, disjunction, equivalence, and implication using n+1 boolean variables x1,...,x_{n+1}. For the case that the value f(x1, ...,xn) is not needed for further computations,  we even give more compact formulation. Our formulations show that every binary boolean function f(x1,x2)=x3 can be realized by the only three boolean variables x1,x2,x3 and at most four linear programming constraints.  

References

A.W. Appel and L. George. Optimal Spilling for CISC Machines with Few Registers. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, PLDI ’01, pages 243–253. ACM, 2001.

D.-S. Chen, R.G. Batson, and Y. Dang. Applied Integer Programming: Modeling and Solution. Wiley, New York, 2010.

V. Chvátal. Linear Programming. W. H. Freeman and Company, New York, 1983.

FICOTM. MIP formulations and linearizations - Quick reference. Technical report, Fair Isaac Corporation, Warwickshire CV32 5YN, UK, 2009.

M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco, 1979.

M. Jünger, T.M. Liebling, D. Naddef, G.L. Nemhauser, W.R. Pulleyblank, G. Reinelt, G. Rinaldi, and L.A. Wolsey, editors. 50 Years of Integer Programming 1958-2008. Springer-Verlag, 2010.

J. Luttamaguzi, M. Pelsmajer, Z. Shen, and B. Yang. Integer programming methods for several optimization problems in graph theory. In Proceedings of the International Conference on Computers and Their Applications, CATA 2005, pages 50–55. ISCA, 2005.

R. Vanderbei. Linear Programming. Springer-Verlag, Berlin, 2008.

Published
2014-11-21
How to Cite
Gurski, F. (2014). Efficient Binary Linear Programming Formulations for Boolean Functions. Statistics, Optimization & Information Computing, 2(4), 274-279. https://doi.org/10.19139/soic.v2i4.83
Section
Research Articles