Mixed integer programming formulations for unions of polyhedra or (polyhedral) disjunctive constraints
can be divided into extended formulations that use both 0-1 and continuous auxiliary variables, and non-
extended formulations that only use the 0-1 variables that are strictly necessary to construct a valid formula-
tion. Standard extended formulations have sizes that are linear on the sizes of the polyhedra and have linear
programming relaxations with extreme points that naturally satisfy the appropriate integrality constraints
(such formulations are usually denoted ideal and are as strong as possible). In contrast, for non-extended
formulation there usually is an important trade-o between strength and size. However, a
exible use of
the 0-1 variables that signal the selection among the polyhedra can lead to non-extended formulations that
are ideal and smaller than the best extended alternative. Furthermore, these formulations have been shown
to provide a signicant computation advantage. This paper attempts to explain and expand the success
of such formulations by introducing a geometric characterization of them. This characterization is based
on an embedding of the polyhedra in a higher dimensional space and provides a systematic procedure to
construct ideal formulations. Furthermore, the characterization naturally leads to two notions of formulation
complexity for unions of polyhedra: 1) the size of the smallest non-extended formulation, and 2) the size of
the smallest ideal non-extended formulations. We analyze such measures for various disjunctions of practical
interest by providing (nearly) matching upper and lower bounds, with special emphasis on the number of
general inequalities (i.e. those that are not variable bounds). In particular, when analyzing Special Order
Sets of type 2 (SOS2) we show optimality with respect to the number of general inequalities of an existing
ideal formulation and introduce a non-ideal formulation that only uses a constant number of of general
inequalities. Finally, we consider how adding redundancy to the disjunction can simplify the construction of
ideal formulations and compare the formulation complexity measures to other complexity notions such as
the size of the convex hull of the union of the polyhedra and the extension complexity of this convex hull