Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
Lists
Only you see this
Abstract
We investigate how well the graph of a bilinear function \(b{:}\;[0,1]^n\rightarrow \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 \(c\geqslant \sqrt{n}/4\). On the other hand, we prove that \(c\leqslant 600\sqrt{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.
BibTeX
@article{boland2017bounding,
author = {Natashia Boland and Santanu S. Dey and Thomas Kalinowski and Marco Molinaro and Fabian Rigterink},
title = {{Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions}},
journal = {Math. Program.},
year = {2017},
doi = {10.1007/s10107-016-1031-5},
}Loading related content...