Cutting Planes from Extended LP Formulations

For mixed-integer sets defined by linear inequalities and integrality requirements on some of the variables, we study extended formulations of their LP relaxations. In terms of optimization, these extended formulations do not lead to better bounds than the original LP relaxation itself but they sometimes lead to stronger bounds after the addition of cutting planes. In this paper we show that for every 0-1 mixed-integer set with n integer and k continuous variables, there is an extended formulation with 2n + k variables whose split closure is integral. The proof is constructive but it requires an inner description of the LP relaxation. We also extend this idea to general mixed-integer sets and construct the best extended formulation for such sets with respect to lattice-free cuts. We consider adding 0-1 split cuts to the Lovasz-Schrijver extended formulation and show that this operation is significantly stronger than the original procedure. We also present computational results showing the strength of cutting planes derived from extended LP formulations.