Robert Hildebrand

A Mixed Integer Linear Program (MILP) is an op-timization problem where you maximize a linear function sub-ject to linear constraints and the constraint that some of thevariables must take integer values. Both computationally andtheoretically, MILPs requiring only few variables to be integercan be solved efficiently whereas problems with many integervariables can be difficult to solve. We investigate how to refor-mulate Integer Programs (having all integer variables) as equiv-alent MILPs in order to give efficient algorithms to solve them.We will discuss two main results: a generalization of total uni-modulariy, and lower bounds for the extension complexity ofthe matching polytope in the context of mixed integer extendedformulations.