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 $b:[0,1{]}^n\to \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⩾\sqrt{n}/4$. On the other hand, we prove that $c⩽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.

12 pages

Cited by in corpus (6)

• Extended formulations for convex hulls of graphs of bilinear functions
• Error bounds for monomial convexification in polynomial optimization
• 2x2 convexifications for convex quadratic optimization with indicator variables
• Efficient treatment of bilinear forms in global optimization
• Strong Formulations for Quadratic Optimization with M-matrices and Indicator Variables
• Convexification of box-constrained polynomial optimization problems via monomial patterns