TITLE:  Embedding Formulations and Complexity for Unions of Polyhedra

ABSTRACT:

We consider a systematic procedure to construct small but strong Mixed Integer Programming (MIP) formulations for unions of polyhedra. A key of the procedure is the flexible use of 0-1 variables that signal the selection among the polyhedra. This flexibility is achieved by considering several possible embeddings of the polyhedra in a higher dimensional space. An important characteristic of these formulations is that they do not use auxiliary variables other than the 0-1 variables strictly needed to construct a formulation (in contrast to "extended" formulations, which are allowed to use any number of auxiliary variables). Nonetheless, the formulations obtained through this embedding procedure can be smaller that the smallest known alternative formulation (extended or not). Furthermore, the Linear Programming (LP) relaxation of these formulations often have extreme points that naturally satisfy the appropriate integrality constraints (such formulations are usually denoted "ideal"). These characteristics allow some versions of these formulations to provide a significant computational advantage over alternative formulations. 

The embedding formulation approach leads to two notions of 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 give upper and lower bounds for these complexity measures for several classes of polyhedra. We also study how the embedding selection affects the sizes of the associated formulations. Finally, we compare these 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.