Efficient Binary Linear Programming Formulations for Boolean Functions
Frank Gurski · Statistics Optimization & Information Computing · 2014
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.