TITLE:  Cutting Planes from Extended LP Formulations

ABSTRACT:

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.