Aggregation and mixed integer rounding to solve MIPs

Abstract

A separation heuristic for mixed integer programs is presented that theoretically allows one to derive several families of "strong" valid inequalities for specific models and computationally gives results as good as or better than those obtained from several existing separation routines including flow cover and integer cover inequalities. The heuristic is based on aggregation of constraints of the original formulation and mixed integer rounding inequalities. Keywords: mixed integer programming, cutting planes, Gomory mixed integer cuts. 1 CORE, Universite catholique de Louvain. E-mail [e-mail] 2 CORE and INMA, Universite catholique de Louvain. E-mail [e-mail] The first author was supported by a doctoral fellowship from College Interuniversitaire pour les Sciences du Management (CIM). This text presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's O#ce, Science Policy Programming. The scientific responsability is assumed by the authors. 1