Practical Problem Solving with Cutting Plane Algorithms in Combinatorial Optimization
Jünger, Michael and Reinelt, Gerhard and Thienel, Stefan
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.
|Depositing User:||Prof. Dr. Michael Jünger|
|Date Deposited:||27 Jun 2003 00:00|
|Last Modified:||19 Jan 2012 11:03|