Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
复制标题
限制双线性函数的麦考密克松弛和凸包之间的差距
DOI：
10.1007/s10107-016-1031-5
复制
发表时间：
2015
影响因子：
2.7
通讯作者：
F. Rigterink
中科院分区：
文献类型：
--
作者：
N. Boland;Santanu S. Dey;T. Kalinowski;M. Molinaro;F. Rigterink
我们研究双线性函数$$B{：}\;[0，1]^n\rightarrow \mathbb {R}$$B：[0，1]n→R的图形可以通过其麦考密克松弛来逼近。特别是，我们感兴趣的最小数c，使得从麦考密克松弛方法获得的凹上界和凸下界函数之间的差至多是凹包络和凸包络之间的差的c倍。通过讨论Luedtke、Namazifar和Linderoth的一个问题，我们证明了这个因子c不能被一个与n无关的常数所约束。更精确地说，我们证明了对于一个随机双线性函数B，我们有渐近几乎必然的$$c\geqslane\sqrt{n}/4$$c n/4。另一方面，我们证明了$$c\leqslant 600\sqrt{n}$$c ≠ 600 n，这改进了Luedtke，Namazifar和Linderoth证明的线性上界。此外，我们还给出了Misener，Smadbeck和Floudas特征函数B的McCormick松弛等于凸船体的一个结果的另一种证明.
We investigate how well the graph of a bilinear function $$b{:}\;[0,1]^n\rightarrow \mathbb {R}$$b:[0,1]n→R can be approximated by its McCormick relaxation. In particular, we are interested in the smallest number c such that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is at most c times the difference between the concave and convex envelopes. Answering a question of Luedtke, Namazifar and Linderoth, we show that this factor c cannot be bounded by a constant independent of n. More precisely, we show that for a random bilinear function b we have asymptotically almost surely $$c\geqslant \sqrt{n}/4$$c⩾n/4. On the other hand, we prove that $$c\leqslant 600\sqrt{n}$$c⩽600n, which improves the linear upper bound proved by Luedtke, Namazifar and Linderoth. In addition, we present an alternative proof for a result of Misener, Smadbeck and Floudas characterizing functions b for which the McCormick relaxation is equal to the convex hull.