Revisiting a Cutting-Plane Method for Perfect Matchings
Open Journal of Mathematical Optimization, Volume 1 (2020) , article no. 2, 15 p.

In 2016, Chandrasekaran, Végh, and Vempala (Mathematics of Operations Research, 41(1):23–48) published a method to solve the minimum-cost perfect matching problem on an arbitrary graph by solving a strictly polynomial number of linear programs. However, their method requires a strong uniqueness condition, which they imposed by using perturbations of the form c(i)=c 0 (i)+2 -i . On large graphs (roughly m>100), these perturbations lead to cost values that exceed the precision of floating-point formats used by typical linear programming solvers for numerical calculations. We demonstrate, by a sequence of counterexamples, that perturbations are required for the algorithm to work, motivating our formulation of a general method that arrives at the same solution to the problem as Chandrasekaran et al. but overcomes the limitations described above by solving multiple linear programs without using perturbations. The key ingredient of our method is an adaptation of an algorithm for lexicographic linear goal programming due to Ignizio (Journal of the Operational Research Society, 36(6):507–515, 1985). We then give an explicit algorithm that exploits our method, and show that this new algorithm still runs in strongly polynomial time.

Received:
Revised:
Accepted:
Published online:
DOI: https://doi.org/10.5802/ojmo.2
Keywords: perfect matching, uniqueness, perturbation, lexicographic linear goal programming, cutting-plane
@article{OJMO_2020__1__A2_0,
     author = {Amber Q. Chen and Kevin K. H. Cheung and P. Michael Kielstra and Avery D. Winn},
     title = {Revisiting a Cutting-Plane Method for Perfect Matchings},
     journal = {Open Journal of Mathematical Optimization},
     eid = {2},
     publisher = {Universit\'e de Montpellier},
     volume = {1},
     year = {2020},
     doi = {10.5802/ojmo.2},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/item/OJMO_2020__1__A2_0/}
}
Amber Q. Chen; Kevin K. H. Cheung; P. Michael Kielstra; Avery D. Winn. Revisiting a Cutting-Plane Method for Perfect Matchings. Open Journal of Mathematical Optimization, Volume 1 (2020) , article  no. 2, 15 p. doi : 10.5802/ojmo.2. https://ojmo.centre-mersenne.org/item/OJMO_2020__1__A2_0/

[1] David L. Applegate; William Cook; Sanjeeb Dash; Daniel G. Espinoza Exact solutions to linear programming problems, Operations Research Letters, Volume 35 (2007) no. 6, pp. 693-699 | Article | MR 2361036 | Zbl 1177.90282

[2] Karthekeyan Chandrasekaran; László A. Végh; Santosh S. Vempala The cutting plane method is polynomial for perfect matchings, Mathematics of Operations Research, Volume 41 (2016) no. 1, pp. 23-48 http://pubsonline.informs.org/doi/10.1287/moor.2015.0714 | Article | MR 3465740 | Zbl 1334.90077

[3] A. Charnes Optimality and degeneracy in linear programming, Econometrica, Volume 20 (1952) no. 2, pp. 160-170 | Article | MR 56264 | Zbl 0049.37903

[4] William Cook; Rohe André Computing minimum-weight perfect matchings, INFORMS Journal on Computing, Volume 11 (1999) no. 2, pp. 138-148 https://pubsonline.informs.org/doi/pdf/10.1287/ijoc.11.2.138 | Article | MR 1696029 | Zbl 1040.90539

[5] William Cook; William Cunningham; William Pulleyblank; Alexander Schrijver Combinatorial optimization, Wiley-Interscience series in discrete mathematics and optimization, Wiley, New York, 1998 | Zbl 0909.90227

[6] William Cook; Thorsten Koch; Daniel E. Steffy; Kati Wolter An exact rational mixed-integer programming solver, Integer programming and combinatoral optimization (Oktay Günlük; Gerhard J. Woeginger, eds.), Volume 6655, Springer Berlin Heidelberg, Berlin, Heidelberg, 2011, pp. 104-116 http://link.springer.com/10.1007/978-3-642-20807-2_9 | Article | MR 2820901 | Zbl 1339.90244

[7] Jack Edmonds Maximum Matching and a Polyhedron with 0,1 Vertices, J. of Res. the Nat. Bureau of Standards, Volume 69 B (1965), pp. 125-130 | Article | MR 183532 | Zbl 0141.21802

[8] Jack Edmonds Paths, trees, and flowers, Canad. J. Math., Volume 17 (1965), pp. 449-467 | Article | MR 177907 | Zbl 0132.20903

[9] Ambros M. Gleixner; Daniel E. Steffy; Kati Wolter Iterative Refinement for Linear Programming, INFORMS Journal on Computing, Volume 28 (2016) no. 3, pp. 449-464 | Article | MR 3505581 | Zbl 1348.90460

[10] Martin Grötschel; László Lovász; Alexander Schrijver Geometric algorithms and combinatorial optimization, Springer, 1988 http://eudml.org/doc/204222 | Article | Zbl 0634.05001

[11] James Ignizio Introduction to linear goal programming, Sage University Paper Series on Quantitative Applications in the Social Sciences, Volume 56, Sage Publications, Beverly Hills, CA, 1985 | Article | MR 843074 | Zbl 0662.90075

[12] James P. Ignizio An Algorithm for Solving the Linear Goal Programming Problem by Solving its Dual, Journal of the Operational Research Society, Volume 36 (1985) no. 6, pp. 507-515 | Article | Zbl 0565.90071

[13] Paul Michael Kielstra Code for revisiting a cutting plane method for perfect matchings, 2019 | Article

[14] Vladimir Kolmogorov Blossom V: A New Implementation of a Minimum Cost Perfect Matching Algorithm, Mathematical Programming Computation, Volume 1 (2009) no. 1, pp. 43-67 http://link.springer.com/10.1007/s12532-009-0002-8 | Article | MR 2520443 | Zbl 1171.05429

[15] Manfred W. Padberg; M. R. Rao Odd Minimum Cut-Sets and b-Matchings, Math. Oper. Res., Volume 7 (1982) no. 1, pp. 67-80 | Article | MR 665219 | Zbl 0499.90056

[16] Alexander Schrijver Theory of Linear and Integer Programming, Wiley-Interscience series in discrete mathematics and optimization, Wiley, Chichester, 2000 (OCLC: 247967491)