MIP: Theory and practice -- closing the gap (Q2712822)

The authors show how dramatic progress in solving mixed-integer-programs in recent years has been achieved.NEWLINENEWLINENEWLINEFirst they hint to remarkable progress in solving ordinary Linear Programs (LP): ``long step'' dual simplex method, fast pricing update, better ordering algorithms for Cholesky factorization, exploiting level-two cache for solving large LPs etc.NEWLINENEWLINENEWLINEThen a ``barrage'' of different techniques and refinements are discussed. The authors focus on good default implementations, such that their combination often produces results that would not have been possible with any one technique, while turning off techniques, which don't pay off, in an early state of computation.NEWLINENEWLINENEWLINEEspecially node presolve (bound strengthening, coefficient reduction), node heuristics, and six kinds of cutting planes (knapsack covers, GUB covers, flow covers, cliques, implied bounds, Gomory mixed-integer cuts) are incorporated.NEWLINENEWLINENEWLINEExtensive experimental results, using CPLEX 6.0 as well as CPLEX 6.5, are reported, and surprising consequences are drawn.NEWLINENEWLINEFor the entire collection see [Zbl 0946.00028].