Videos

On disjunction convex hulls by lifting

Presenter
August 27, 2024
Abstract
In the study of disjunctive programming, a critical aspect is the exploration of feasible regions formed by the union of multiple convex sets. The `big-M' method is well-established and often used (and abused) for formulating multiple-choice constraints. It is well-known that such formulations can be rather weak and also suffer from numerical instability, even when the big-M coefficients are chosen optimally. So, MILP/MINLP solvers often struggle with these formulations, while they are ubiquitous in MILP/MINLP applications. On the other hand, sometimes these formulations are best possible; that is, the inequalities can give a complete description of the convex-hull of the mixed-integer solutions, and we considered broad and useful situations where this is indeed the case. In such situations, the `big-M' inequalities can be derived by optimally lifting facet-describing inequalities of the disjunctive pieces. Specifically, we study the natural extended-variable formulation for the disjunction of n+1 polytopes in dimension d. We demonstrate that the convex hull D in the natural extended-variable space in dimension d+n is given by full optimal big-M lifting (i) when d = 3), and also (ii) when the polytopes are all axis-aligned hyper-rectangles. We note that both of these cases are very natural for applications and within spatial branch-and-bound, the main algorithmic paradigm for mixed-integer nonlinear optimization. Additionally, we give further results on the polyhedral structure of D, giving very general conditions under which it is full dimensional and when the full optimal big-M liftings of the facet-describing inequalities for the individual polytopes describe facets of D.