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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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