Computing minimum-weight perfect matching by linear programming.

Start by modeling the LP problem as in the bipartite case and solving it.

- If the subgraph induced by the found solution has odd cycles, it's necessary to add the corresponding "blossom inequality constraints" to the LP model in order "to break" the odd cycles.
-Then you solve again the augmented LP model.

By repeating this steps, eventually, a solution corresponding to a matching arises.

[alikellaway]

Is the source code for this available? Also, perhaps you might be able to advise me on a java imlementation of a solution to this problem?