2024/07/21 by Qu, Yushan, Lee, Jon
#Combinatorics (math.CO) #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2407.15244
We study the natural extended-variable formulation for the disjunction of n+1 polytopes in ℝd. We demonstrate that the convex hull D in the natural extended-variable space ℝd+n is given by full optimal big-M lifting (i) when d≤ 2 (and that it is not generally true for d≥ 3), and also (ii) under some technical conditions, when the polytopes have a common facet-describing constraint matrix, for arbitrary d≥ 1 and n≥ 1. We give a broad family of examples with d≥ 3 and n=1, where the convex hull is not described after employing all full optimal big-M lifting inequalities, but it is described after one round of MIR inequalities. Additionally, we give some general results on the polyhedral structure of D, and we demonstrate that all facets of D can be enumerated in polynomial time when d is fixed.