For mixed-integer sets, we study extended formulations of their LP relaxations and study the effect of adding cutting planes in the extended space. In terms of optimization, extended LP formulations do not lead to better bounds as their projection onto the original space is precisely the original LP relaxation. However, we show that applying split cuts to such extended formulations can be more effective than applying split cuts to the original formulation. For any 0-1 mixed-integer set with $n$ integer and $k$ continuous variables, we construct an extended formulation with $2n+k-1$ variables whose elementary split closure is integral. We extend this idea to general mixed-integer sets and construct the best extended formulation with respect to split cuts. This is joint work with Sanjeeb Dash and Oktay Gunluk from IBM Research.

Merve Bodur is an Assistant Professor in the Department of Mechanical and Industrial Engineering at the University of Toronto. She also holds a Dean's Spark Professorship in the Faculty of Applied Science and Engineering. She obtained her Ph.D. from University of Wisconsin-Madison and did a postdoc at Georgia Institute of Technology. She received her B.S. in Industrial Engineering and B.A. in Mathematics from Bogazici University, Turkey. Her research interests include theory and applications of stochastic programming, integer programming, multiobjective integer programming and combinatorial optimization.