Practical Problem Solving with Cutting Plane Algorithms in Combinatorial Optimization

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.


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.

Download: [img] Postscript
Download (543kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Collection Item
Citations: 97 (Google Scholar) |
Uncontrolled Keywords: branch-and-cut cutting plane algorithms parallelization
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
Related URLs:
Deposit Information:
ZAIK Number: zpr94-156
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 27 Jun 2003 00:00
Last Modified: 19 Jan 2012 11:03