10

You don't get a minimum-weight (perfect) matching by giving preference to smaller weights in the stable marriage problem. Consider $\mathcal{I}=\{a,b\}$ and $\mathcal{J}=\{1,2\}$ and weights $w_{a1}=2$, $w_{a2}=1$, $w_{b1}=100$, and $w_{b2}=2$. In this case matching $\{a2,b1\}$ of value $101$ is the only stable one but the minimum-weight matching is $\{a1,b2\...


9

This is where decomposition algorithms (specifically Dantzig-Wolfe can be quite useful). My thesis work and subsequent OSS in COIN provides APIs to do this kind of thing: https://projects.coin-or.org/Dip The basic idea is that the oracle is the graph implementation while the side constraints are modeled as the master constraints in the decomposition ...


8

A matching of size $m$ in $\mathrm{K}_{n,n}$ is uniquely identified by (i) the set of covered vertices in the left partition, for which there are $\binom{n}{m}$ choices, (ii) the set of covered vertices in the right position, ditto $\binom{n}{m}$ choices, and (iii) a bijection from the covered vertices on the left onto the covered vertices on the right, for ...


7

In general ILP solvers are not as efficient in solving the Maximum Matching problem. A comparison of efficient matching algorithm implementations, as well as an ILP formulation for the Maximum Cardinality Matching Problem and the Minimum Weight perfect matching problem can be found in Figures 5 and 6 of this paper: Dimitrios Michail, Joris Kinable, Barak ...


5

I think the spanning tree polytope also falls under this category. Computing the minimum spanning tree is easy. However, we would require all the sub-tour elimination constraints (which is exponential in number of vertices) to represent the spanning tree polytope in 0-1 variables as a LP. EDIT: From the comments below, one can find a reference for a ...


3

If the bipartite graph is $K_{n,n}$, then all $n$ vertices of the left hand size have exactly $n$ possible matches (each node of the right layer is a candidate). So the total number of matchings is $n^n$ indeed. Maybe you can try and detect if there are identical matchings among the $3174$ found by CPLEX ?


1

You might be interested in the paper published by Vladimir Kolmogorov in Mathematical Programming Computation (MPC), July 2009, 1(1), pp. 43-67: "Blossom V: A new implementation of a minimum cost perfect matching algorithm". You can find the paper here together with a C++ implementation by the author here.


Only top voted, non community-wiki answers of a minimum length are eligible