1. On disjunction convex hulls by lifting
- Author
-
Qu, Yushan and Lee, Jon
- Subjects
Mathematics - Optimization and Control ,Mathematics - Combinatorics - Abstract
We study the natural extended-variable formulation for the disjunction of $n+1$ polytopes in $R^d$. We demonstrate that the convex hull $D$ in the natural extended-variable space $R^{d+n}$ is given by full optimal big-M lifting (i) when $d\leq 2$ (and that it is not generally true for $d\geq 3$), and also (ii) under some technical conditions, when the polytopes have a common facet-describing constraint matrix, for arbitrary $d\geq 1$ and $n\geq 1$. Additionally, we give further results on the polyhedral structure of $D$, and we demonstrate that all facets of $D$ can be enumerated in polynomial time., Comment: Short preliminary version appeared in ISCO 2024
- Published
- 2024