zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Solving matching problems with linear programming. (English) Zbl 0579.90069

Summary: We describe an implementation of a cutting plane algorithm for the perfect matching problem which is based on the simplex method. The algorithm has the following features: 1. It works on very sparse subgraphs of K n which are determined heuristically, global optimality is checked using the reduced cost criterion. 2. Cutting plane recognition is usually accomplished by heuristics. Only if these fail, the Padberg-Rao procedure is invoked to guarantee finite convergence.

Our computational study shows that - on the average - very few variables and very few cutting planes suffice to find a globally optimal solution. We could solve this way matching problems on complete graphs with up to 1000 nodes. Moreover, it turned out that our cutting plane algorithm is competitive with the fast combinatorial matching algorithms known to date.

90C10Integer programming
90C05Linear programming
68Q25Analysis of algorithms and problem complexity
65K05Mathematical programming (numerical methods)
[1]M. Ball and U. Derigs, ”An analysis of alternate strategies for implementing matching algorithms”,Networks 13 (1983) 517–549. · Zbl 0519.68055 · doi:10.1002/net.3230130406
[2]R.E. Burkard and U. Derigs,Assignment and Matching Problems: Solution Methods with Fortran-Programs (Springer Lecture Notes in Economics and Mathematical Systems, No. 184, Berlin, 1980).
[3]H. Crowder and M.W. Padberg, ”Solving large-scale symmetric travelling salesman problems”,Management Science 26 (1980) 495–509. · Zbl 0444.90068 · doi:10.1287/mnsc.26.5.495
[4]W. Cunningham and A. Marsh, ”A primal algorithm for optimum matching”,Mathematical Programming Study 8 (1978) 50–72.
[5]U. Derigs, ”Solving matching problems via shortest path techniques”, Report No. 83263-OR, Institut für Ökonometrie und Operations Research, Universität Bonn (Bonn, 1983).
[6]U. Derigs, ”Solving large scale matching problems efficiently–A new primal matching approach”, Report No. 84346-OR, Institut für Ökonometrie und Operations Research, Universität Bonn (Bonn, 1984).
[7]E.A. Dinic, ”Algorithm for solution of a problem of maximum flow in a network with power estimation”,Soviet Mathematics Doklady 11 (1970) 1277–1280.
[8]J. Edmonds, ”Paths, trees and flowers”,Canadian Journal of Mathematics 17 (1965) 449–467. · Zbl 0132.20903 · doi:10.4153/CJM-1965-045-4
[9]J. Edmonds, ”Maximum matching and a polyhedron with 0, 1 vertices”,Journal of Research National Bureau of Standards 69B (1965) 125–130.
[10]L.R. Ford and D.R. Fulkerson, ”A simple algorithm for finding maximal flows and an application to the Hitchcock problem”,Canadian Journal of Mathematics 9 (1957) 210–218. · Zbl 0088.12907 · doi:10.4153/CJM-1957-024-0
[11]F. Glover, D. Klingman, J. Mote and D. Whitman, ”A primal simplex variant for the maximum flow problem”, Center for Cybernetic Studies, CCS 362 (Austin, TX, 1979).
[12]M. Grötschel, M. Jünger and G. Reinelt, ”A cutting plane algorithm for the linear ordering problem”,Operations Research 32 (1984) 1195–1220. · Zbl 0554.90077 · doi:10.1287/opre.32.6.1195
[13]M. Grötschel, L. Lovász and A. Schrijver, ”The ellipsoid method and its consequences in combinatorial optimization”,Combinatorica 1 (1981) 169–197. · Zbl 0492.90056 · doi:10.1007/BF02579273
[14]M. Grötschel and W.R. Pulleyblank, ”Weakly bipartite graphs and the max-cut problem”,Operations Research Letters 1 (1981) 23–27. · Zbl 0494.90078 · doi:10.1016/0167-6377(81)90020-1
[15]A.V. Karzanov, ”Determining the maximal flow in a network by the method of preflows”,Soviet Mathematics Doklady 15 (1972) 434–437.
[16]E.L. Lawler,Combinatorial optimization: Networks and matroids (Holt, Rinehart and Winston, New York, 1976).
[17]V.M. Malhorta, M.P. Kumar and S.N. Maheshwari, ”An O(|V|3) algorithm for finding maximum flows in networks”,Information Processing Letters 7 (1978) 277–278. · Zbl 0391.90041 · doi:10.1016/0020-0190(78)90016-9
[18]M.W. Padberg and M.R. Rao, ”Odd minimum cut-sets andb-matchings”,Mathematics of Operations Research 7 (1982) 67–80. · Zbl 0499.90056 · doi:10.1287/moor.7.1.67
[19]M.W. Padberg and M.R. Rao, ”The Russian method for linear inequalities III: Bounded integer Programming”, Preprint, GBA New York University, New York, May 1981.