Revisiting a Cutting-Plane Method for Perfect Matchings

Amber Q. Chen ¹; Kevin K. H. Cheung ²; P. Michael Kielstra ³; Avery D. Winn ⁴

¹ University of Waterloo, 200 University Ave. W., Waterloo, ON N2L 3G1, Canada
² Carleton University, 1125 Colonel By Dr., Ottawa, ON K1S 5B6, Canada
³ Harvard University, 1 Oxford Street, Cambridge, MA 02138, USA
⁴ University of Michigan, 530 S State St., Ann Arbor, MI 48109, USA

Open Journal of Mathematical Optimization, Volume 1 (2020), article no. 2, 15 p.

Abstract

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: 2020-06-15
Revised: 2020-09-24
Accepted: 2020-11-30
Published online: 2020-12-09

DOI: 10.5802/ojmo.2

Keywords: perfect matching, uniqueness, perturbation, lexicographic linear goal programming, cutting-plane

Author's affiliations:

Amber Q. Chen ¹; Kevin K. H. Cheung ²; P. Michael Kielstra ³; Avery D. Winn ⁴

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@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},
     pages = {1--15},
     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/}
}

TY  - JOUR
AU  - Amber Q. Chen
AU  - Kevin K. H. Cheung
AU  - P. Michael Kielstra
AU  - Avery D. Winn
TI  - Revisiting a Cutting-Plane Method for Perfect Matchings
JO  - Open Journal of Mathematical Optimization
PY  - 2020
SP  - 1
EP  - 15
VL  - 1
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.2/
DO  - 10.5802/ojmo.2
LA  - en
ID  - OJMO_2020__1__A2_0
ER  -

%0 Journal Article
%A Amber Q. Chen
%A Kevin K. H. Cheung
%A P. Michael Kielstra
%A Avery D. Winn
%T Revisiting a Cutting-Plane Method for Perfect Matchings
%J Open Journal of Mathematical Optimization
%D 2020
%P 1-15
%V 1
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.2/
%R 10.5802/ojmo.2
%G en
%F 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/articles/10.5802/ojmo.2/

References
Cited by

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

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

[11] James Ignizio 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] 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 | DOI | Zbl

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

Cited by Sources: