Revisiting a Cutting-Plane Method for Perfect Matchings

Chen, Amber Q.; Cheung, Kevin K. H.; Kielstra, P. Michael; Winn, Avery D.

Open Journal of Mathematical Optimization, Tome 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\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.

Mots clés : perfect matching, uniqueness, perturbation, lexicographic linear goal programming, cutting-plane

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

[2] Chandrasekaran, Karthekeyan; Végh, László A.; Vempala, Santosh S. 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 (Accessed 2019-08-14) | DOI | MR | Zbl

[3] Charnes, A. Optimality and degeneracy in linear programming, Econometrica, Volume 20 (1952) no. 2, pp. 160-170 (Accessed 2019-08-22) | DOI | MR | Zbl

[4] Cook, William; André, Rohe 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 | DOI | MR | Zbl

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

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

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

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

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

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

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

[12] Ignizio, James P. 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 | DOI | Zbl

[13] Kielstra, Paul Michael Code for revisiting a cutting plane method for perfect matchings, 2019 (Accessed 2019-08-22) | DOI

[14] Kolmogorov, Vladimir 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 (Accessed 2019-08-15) | DOI | MR | Zbl

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

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