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

Natashia Boland, Thomas Kalinowski, Fabian Rigterink

Published 2015-07-30Version 1

We investigate how well the graph of a bilinear function $b:[0,1]^n\to\reals$ 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$. In addition we characterize the functions $b$ such that the McCormick relaxation is equal to the convex hull.