Jünger, Michael, Reinelt, Gerhard and Thienel, Stefan
(1995).
Practical Problem Solving with Cutting Plane Algorithms in Combinatorial Optimization.
American Math. Soc.
["eprint_fieldopt_monograph_type_preprint" not defined].
|
PDF
zpr94-156.pdf Download (424kB) | Preview |
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.
| Item Type: | Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined]) | ||||||||||||||||
| Creators: |
|
||||||||||||||||
| URN: | urn:nbn:de:hbz:38-546855 | ||||||||||||||||
| Series Name: | DIMACS series in discrete mathematics and theoretical computer science | ||||||||||||||||
| Volume: | 20 | ||||||||||||||||
| Number: | 20 | ||||||||||||||||
| Page Range: | pp. 111-152 | ||||||||||||||||
| Date: | 1995 | ||||||||||||||||
| Publisher: | American Math. Soc | ||||||||||||||||
| Language: | English | ||||||||||||||||
| Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||||||||||
| Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||||||||||
| Subjects: | Data processing Computer science | ||||||||||||||||
| Refereed: | No | ||||||||||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/54685 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |