17
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

14
$\begingroup$

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 negative 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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.