DOS Seminar - Juan Pablo Vielma

Event Details
  • Date/Time:
    • Friday October 16, 2015
      12:00 pm
  • Location: Advisory Board Room, GC 402
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: DOS Seminar - Juan Pablo Vielma

Full Summary: No summary paragraph submitted.

TITLE:  Embedding Formulations and Complexity for Unions of Polyhedra


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.

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
Undergraduate students, Faculty/Staff, Graduate students
No keywords were submitted.
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Oct 12, 2015 - 6:12am
  • Last Updated: Apr 13, 2017 - 5:17pm