Tag Info

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 ?