ISSN:
1436-5057
Keywords:
05-04
;
05C45
;
90C10
;
Matching
;
cutting plane algorithm
;
polyhedral combinatorics
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Wir beschreiben die Implementierung eines Schnittebenenverfahrens zur Bestimmung minimaler gewichteter perfekter 2-Matchings. Der Algorithmus baut auf der vollständigen Beschreibung des perfekten 2-Matching-Polytops, die Edmonds angegeben hat, auf und verwendet die Simplexmethode zur Lösung der im Verfahren auftretenden LP-Relaxierungen. Schnittebenen werden entweder mit schnellen Heuristiken bestimmt, oder, falls diese nicht erfolgreich sind, mit einer effizienten und auf 2-matching-Ungleichungen abgestimmten Implementierung des Padberg-Rao-Verfahrens. Mit diesem Algorithmus konnten 2-Matching-Probleme in vollständigen Graphen mit bis zu 1000 Knoten, d. h. mit bis zu 499.500 Variablen, in weniger als einer Stunde CPU-Zeit auf einem Rechner mittlerer Leistung gelöst werden.
Notes:
Abstract We describe an implementation of a cutting plane algorithm for the minimum weight perfect 2-matching problem. This algorithm is based on Edmonds' complete description of the perfect 2-matching polytope and uses the simplex algorithm for solving the LP-relaxations coming up. Cutting planes are determined by fast heuristics, or, if these fail, by an efficient implementation of the Padberg-Rao procedure, specialized for 2-matching constraints. With this algorithm 2-matching problems on complete graphs with up to 1000 nodes (i.e., 499,500 variables) have been solved in less than 1 hour CPU time on a medium speed computer.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02239975
Permalink
