A cutting plane algorithm for minimum perfect 2-matchings (Q1821798)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A cutting plane algorithm for minimum perfect 2-matchings |
scientific article |
Statements
A cutting plane algorithm for minimum perfect 2-matchings (English)
0 references
1987
0 references
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.
0 references
cutting plane algorithm
0 references
minimum weight perfect 2-matching problem
0 references
perfect 2-matching polytope
0 references
polyhedral combinatorics
0 references
