Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions |
| |
Authors: | Natashia Boland,Santanu S. Dey,Thomas Kalinowski,Marco Molinaro,Fabian Rigterink author-information" > |
| |
Affiliation: | 1.Georgia Institute of Technology,Atlanta,USA;2.University of Newcastle,Callaghan,Australia;3.PUC-Rio,Rio de Janeiro,Brazil |
| |
Abstract: | We investigate how well the graph of a bilinear function (b{:};[0,1]^nrightarrow mathbb {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 (cgeqslant sqrt{n}/4). On the other hand, we prove that (cleqslant 600sqrt{n}), 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|