Efficient Binary Linear Programming Formulations for Boolean Functions
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.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
