*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
