# When is the McCormick envelope exact?

I know that given $$S$$ of the form $$S = \{ (x,y,z) \in \mathbb R^3: \ell_x \leq x \leq u_x; \ell_y \leq y \leq u_y; z = xy\}$$ with finite lower and upper bounds, the McCormick envelope of $$S$$ gives the convex hull of $$S$$.

Are there other such known families of sets where the McCormick envelope gives the convex hull?

## 1 Answer

For a function $$f:[0,1]^n\to\mathbb{R}$$ of the form $$f(x_1,\dots,x_n)=\sum_{ij\in E}a_{ij}x_ix_j$$, where $$E$$ is the edge set of a graph $$G$$ on the vertex set $$\{1,\dots,n\}$$, the McCormick envelope gives the convex hull if and only if every cycle in $$G$$ has an even number of positive edges and an even number of odd edges (where an edge $$ij$$ is called positive or negative depending on the sign of the coefficient $$a_{ij}$$). In particular, $$G$$ needs to be bipartite. This is a direct consequence of Theorem 3.10 in

Misener, R., Smadbeck, J.B., Floudas, C.A.: Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2. Optim. Methods Softw. 30(1), 215--249 (2014)

An alternative proof can be found in (Theorem 4)

N. Boland, S. Dey, T. Kalinowski, M. Molinaro, F. Rigterink: Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions, Mathematical programming 162 (2017), https://arxiv.org/abs/1507.08703