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\left(i\right)={c}_{0}\left(i\right)+{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.

Revised:

Accepted:

Published online:

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/articles/10.5802/ojmo.2/} }

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/articles/10.5802/ojmo.2/

[1] Exact solutions to linear programming problems, Operations Research Letters, Volume 35 (2007) no. 6, pp. 693-699 | Article | MR 2361036 | Zbl 1177.90282

[2] 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] Optimality and degeneracy in linear programming, Econometrica, Volume 20 (1952) no. 2, pp. 160-170 | Article | MR 56264 | Zbl 0049.37903

[4] 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] Combinatorial optimization, Wiley-Interscience series in discrete mathematics and optimization, Wiley, New York, 1998 | Zbl 0909.90227

[6] 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] 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] Paths, trees, and flowers, Canad. J. Math., Volume 17 (1965), pp. 449-467 | Article | MR 177907 | Zbl 0132.20903

[9] Iterative Refinement for Linear Programming, INFORMS Journal on Computing, Volume 28 (2016) no. 3, pp. 449-464 | Article | MR 3505581 | Zbl 1348.90460

[10] Geometric algorithms and combinatorial optimization, Springer, 1988 http://eudml.org/doc/204222 | Article | Zbl 0634.05001

[11] 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] 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] Code for revisiting a cutting plane method for perfect matchings, 2019 | Article

[14] 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] 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] Theory of Linear and Integer Programming, Wiley-Interscience series in discrete mathematics and optimization, Wiley, Chichester, 2000 (OCLC: 247967491)