Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case
Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case
复制标题
多项式零一优化对二次情况的有效约简
DOI：
--
复制
发表时间：
2007
影响因子：
3.1
通讯作者：
G. Rinaldi
中科院分区：
文献类型：
--
作者：
C. Buchheim;G. Rinaldi
我们解决的问题，优化多项式的真实的系数超过二进制变量。我们表明，一个完整的多面体描述的线性化这样的问题，可以推导出一个简单的方式从多面体描述的线性化的一些二次优化问题。后一种线性化方法中的变量数仅略大于前一种线性化方法。如果多项式约束存在于原始问题中，则它们的线性化对应物保持不变地转移到线性化二次问题。如果原问题的配方不包含任何约束，我们得到一个减少无约束二次零一优化，这是等价于研究最大割问题。一般无约束多项式零一优化的分离问题，从而减少到分离问题的切割多面体。这使我们能够通过深入的研究，特别是已经开发的复杂的分离技术，转移后一个多面体所获得的全部知识。我们报告的初步实验结果，得到了一个简单的实现这种方法。
We address the problem of optimizing a polynomial with real coefficients over binary variables. We show that a complete polyhedral description of the linearization of such a problem can be derived in a simple way from the polyhedral description of the linearization of some quadratic optimization problem. The number of variables in the latter linearization is only slightly larger than in the former. If polynomial constraints are present in the original problem, then their linearized counterparts carry over to the linearized quadratic problem unchanged. If the original problem formulation does not contain any constraints, we obtain a reduction to unconstrained quadratic zero-one optimization, which is equivalent to the well-studied max-cut problem. The separation problem for general unconstrained polynomial zero-one optimization thus reduces to the separation problem for the cut polytope. This allows us to transfer the entire knowledge gained for the latter polytope by intensive research and, in particular, the sophisticated separation techniques that have been developed. We report preliminary experimental results obtained with a straightforward implementation of this approach.