Aggregation and mixed integer rounding to solve MIPs.pdf

CORE DISCUSSION PAPER9839AGGREGATION and MIXED INTEGER ROUNDING toSOLVE MIPsHugues Marchand1 and Laurence A: Wolsey2June 1998AbstractA separation heuristic for mixed integer programs is presented thattheoretically allows one to derive several families of \strong valid in-equalities for specic models and computationally gives results as goodas or better than those obtained from several existing separation rou-tines including ow cover and integer cover inequalities. The heuristicis based on aggregation of constraints of the original formulation andmixed integer rounding inequalities.Keywords: mixed integer programming, cutting planes, Gomory mixedinteger cuts. 1CORE, Universite catholique de Louvain. E-mail hmarchand@core.ucl.ac.be2CORE and INMA, Universite catholique de Louvain. E-mail wolsey@core.ucl.ac.beThe rst author was supported by a doctoral fellowship from College Interuniversitairepour les Sciences du Management (CIM). This text presents research results of the BelgianProgram on Interuniversity Poles of Attraction initiated by the Belgian State, PrimeMinisters Oce, Science Policy Programming. The scientic responsability is assumedby the authors. 1 IntroductionGomory mixed integer cuts were proposed forty years ago, but, in spite ofa nite convergence theorem, have apparently been little used in practice.More recently a variety of results and observations encourage the view thatthese inequalities or variants of these inequalities are \strong. Acceptingthis hypothesis, the question addressed here is whether and how such in-equalities can be used eectively. Our conclusion is that using a constraintand bound aggregation procedure, and mixed integer rounding inequalities,it is possible to derive many strong valid inequalities that have been pro-posed for specic models in the literature, and also to obtain computationalresults as good as or better than those obtained with several existing separa-tion routines such as those generating ow cover, and surro