Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0579.90069
Grötschel, M.; Holland, O.
Solving matching problems with linear programming. (English)
[J] Math. Program. 33, 243-259 (1985). ISSN 0025-5610; ISSN 1436-4646/e

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\sb 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. \par 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.

MSC 2000:: *90C10 Integer programming
90C05 Linear programming
68Q25 Analysis of algorithms and problem complexity
65K05 Mathematical programming (numerical methods)

Keywords: implementation; cutting plane algorithm; perfect matching problem; simplex method; sparse subgraphs; computational study

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]