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.
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Crowder, H., Padberg, M. W.: Solving large-scale symmetric travelling salesman problems. Management Science26, 495–509 (1980).
Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards —B 69B, 125–130 (1965).
Edmonds, J., Johnson, E. L., Lockhart, S.: Blossom I, a code for matching. Internal IBM Report. Yorktown Heights: T. J. Watson Research Center 1969.
Glover, F., Klingman, D., Mote, J., Whitman, D.: A primal simplex variant for the maximum flow problem. Center for Cybernetics Studies. Preprint CCS 362, Austin, TX, 1979.
Gomory, R. E., Hu, T. C.: Multi terminal network flows. J. Sov. Industr. Applied Math.9, 551–571 (1961).
Grötschel, M.: Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme. Meisenheim: Hain 1977.
Grötschel, M.: Holland, O.: Solving matching problems with linear programming. Mathematical Programming33, 243–259 (1985).
Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica1, 169–197 (1981).
Lovász, L., Plummer, M. D.: Matching Theory. Budapest: Akadémiai Kiadó 1986.
Padberg, M. W., Rao, M. R.: Odd minimum cut-sets and b-matchings. Mathematics of Operations Research7, 67–80 (1982).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Grötschel, M., Holland, O. A cutting plane algorithm for minimum perfect 2-matchings. Computing 39, 327–344 (1987). https://doi.org/10.1007/BF02239975
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02239975