*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.