×

zbMATH — the first resource for mathematics

MIP: Theory and practice – closing the gap. (English) Zbl 0986.90025
Powell, M. J. D. et al., System modelling and optimization. Methods, theory and applications. 19th IFIP TC7 conference, Cambridge, GB, July 12-16, 1999. Boston: Kluwer Academic Publishers. IFIP, Int. Fed. Inf. Process. 46, 19-49 (2000).
The authors show how dramatic progress in solving mixed-integer-programs in recent years has been achieved.
First 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.
Then 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.
Especially 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.
Extensive experimental results, using CPLEX 6.0 as well as CPLEX 6.5, are reported, and surprising consequences are drawn.
For the entire collection see [Zbl 0946.00028].

MSC:
90C11 Mixed integer programming
Software:
LINGO; OSL; XPRESS; CPLEX; KORBX; MIPLIB
PDF BibTeX XML Cite