This is an example implementation, in Python 3, of the minimum-cost perfect matching algorithm described in Chen, Cheung, Kielstra, and Winn's paper Revisiting a Cutting Plane Method for Perfect Matchings. It currently uses SciPy to solve linear programs, but will work with any black-box LP solver with only minor alterations. This is academic example code, not suitable for use in a production environment. Requirements SciPy NumPy igraph Usage import cpmatching import cpmatching.io as io from igraph import Graph G = Graph() G.add_vertices(16) G.add_edges([[13, 15], [11, 14], [10, 11], [10, 14], [9, 11], [8, 11], \ [7, 12], [5, 15], [5, 13], [4, 11], [4, 13], [3, 7], [2, 6], [2, 13], \ [1, 5], [0, 1], [0, 3], [0, 12], [8, 9], [4, 12]]) G.es["weight"] = 1 x = cpmatching.find_matching(G) io.pretty_print_solution(G, x) Further details are available in README.md.