Efficient Binary Linear Programming Formulations for Boolean Functions
Efficient Binary Linear Programming Formulations for Boolean Functions
复制标题
布尔函数的高效二元线性规划公式
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Frank Gurski
中科院分区：
文献类型：
--
作者：
Frank Gurski
在为优化问题设计线性规划时，一个非常有用的工具是通过线性规划约束来制定逻辑运算。利用n+1个布尔变量x1，...，给出了重要的n元布尔函数f（x_1，ldots，x_n）=x_{n+1}（如合取、析取、等价、蕴涵等）的有效线性规划公式，x_{n+1}。对于值f（x1，...，xn），我们甚至给出了更紧凑的公式。我们的公式表明，每个二元布尔函数f（x1，x2）=x3可以实现的只有三个布尔变量x1，x2，x3和最多四个线性规划约束。
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.