Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions

• 成果类型: Article
• 署名作者: Boland, Natashia; Dey, Santanu S.; Kalinowski, Thomas; Molinaro, Marco; Rigterink, Fabian
• 署名单位: University System of Georgia; Georgia Institute of Technology; University of Newcastle; Pontificia Universidade Catolica do Rio de Janeiro
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1031-5
• 发表日期: 2017
• 页码: 523-535
• 关键词: multilinear functions

摘要

We investigate how well the graph of a bilinear function 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 . On the other hand, we prove that , 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.