On Disjunction Convex Hulls by Lifting

We study the natural extended-variable formulation for the disjunction of \(n+1\) polytopes in \(\mathbb {R}^d\) . We demonstrate that the convex hull \(\mathcal {D}\) in the natural extended-variable space \(\mathbb {R}^{d+n}\) is given by full optimal big-M lifting (i) when \(d\le 2\) (and that it is not generally true for \(d\ge 3\) ), and also (ii) when the polytopes are all axis-aligned hyper-rectangles. We give further results on the polyhedral structure of \(\mathcal {D}\) , emphasizing the role of full optimal big-M lifting.