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

Abstract

We investigate how well the graph of a bilinear function 𝑏 : [0,1] ⁿ →R can be approximated by its McCormick relaxation. In particular, we are interested in the smallest number 𝑐 such that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is at most 𝑐 times the difference between the concave and convex envelopes. Answering a question of Luedtke, Namazifar and Linderoth, we show that this factor 𝑐 cannot be bounded by a constant independent of 𝑛. More precisely, we show that for a random bilinear function 𝑏 we have asymptotically almost surely 𝑐 ≥ √𝑛/4. On the other hand, we prove that 𝑐 ≤ 600√𝑛, 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 𝑏 for which the McCormick relaxation is equal to the convex hull.