Jünger, Michael and Reinelt, Gerhard and Thienel, Stefan (1995) Practical Problem Solving with Cutting Plane Algorithms in Combinatorial Optimization.
Published in: Combinatorial optimization : papers from the DIMACS special year ; [contains refereed papers from workshops held at DIMACS during the period of September 1992 through August 1993]., DIMACS series in discrete mathematics and theoretical computer science. 20 American Math. Soc 1995, pp. 111-152.

Abstract

Cutting plane algorithms have turned out to be practically successful computational tools in combinatorial optimization, in particular, when they are embedded in a branch-and-bound framework. Implementations of such ''branch-and-cut'' algorithms are rather complicated in comparison to many purely combinatorial algorithms. The purpose of this article is to give an introduction to cutting plane algorithms from an implementor's point of view. Special emphasis is given to control and data structures used in practically successful implementations of branch-and-cut algorithms. We also address the issue of parallelization. Finally, we point out that in important applications branch-and-cut algorithms are not only able to produce optimal solutions but also approximations to the optimum with certified good quality in moderate computation times. We close with an overview of successful practical applications in the literature.

Actions:

Download:	Postscript Download (530Kb) | Preview
Export as:	HTML CitationASCII CitationOpenURL ContextObjectEndNoteBibTeXMPEG-21 DIDLEP3 XMLJSONAtomReference ManagerSimple MetadataRefer
Editorial actions:	View Item (Login required)