10
votes
Relationship between the Assignment Problem and the Stable Marriage Problem
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$...
- 2,705
10
votes
Accepted
Can a generic ILP solver find graph matchings as fast as a specialized algorithm?
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/...
- 516
8
votes
Can a generic ILP solver find graph matchings as fast as a specialized algorithm?
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 ...
- 3,396
8
votes
Counting the number of matchings in a complete bipartite graph
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 ...
- 201
5
votes
Polynomially solvable problems with exponential extension complexity
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 ...
- 1,458
4
votes
Adjust result to equal mode values
You are looking for a transversal or system of distinct representatives. One approach is to construct a bipartite graph with a left node for each alternative $i$, a right node for each mode $j$, and ...
- 30.4k
4
votes
Accepted
Maximal Matching in a constrained, unweighted Bipartite Graph
Let $I, J$ be the two sets of nodes and let both be sorted by their datetime.
Let $E$ be the set of valid edges.
For each $i\in I$ let $D_i$ be the neighbours of $i$.
Your proposed greedy algorithm ...
- 701
3
votes
Accepted
Counting the number of matchings in a complete bipartite graph
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^...
- 12.9k
3
votes
How to bundle pairs of trips?
If you care only about pairing and not routing, you have a maximum-weight matching problem. For each compatible pair $\{i,j\}$ of loads, let binary decision variable $x_{ij}$ indicate whether these ...
- 30.4k
3
votes
Accepted
Adjust result to equal mode values
There is no guarantee you can avoid ties using mode (or anything else, if it is possible for two alternatives to have identical scores and thus be indistinguishable). Rob's approach (which I endorse) ...
- 37.8k
2
votes
How do you recover dual variables for a minimum weight bipartite perfect matching problem?
If we assume that $y$ corresponds to the constraints $\sum_i x_{ij}=1$ and $z$ corresponds to the other set of constraints, then you have a $(2n)\times (2n-1)$ system of equations $$y_j + z_i = c_{ij}$...
- 37.8k
2
votes
Accepted
2
votes
How to bundle pairs of trips?
Since delivery must be done directly after pick up, it looks more like an Asymmetric Orienteering problem to me, where a visit corresponds to a pick up and its delivery. The subtlety in this case ...
- 2,495
2
votes
Accepted
Effective methods for solving the assignment and packing problem
I don't think the following heuristic can be said to "guarantee near-optimal solutions", but it is quite straightforward to code and can make efficient use of parallel threading/multiple ...
- 37.8k
1
vote
Accepted
Exact algorithms for a bin packing problem
MIP is already exact. Let there be
$l = 26$ letters;
$m = 5$ maximum group items;
$n = 7$ as an example item count, also equal to the maximum number of groups;
$G_{i,j} \in \lbrace 0,1 \rbrace$ ...
- 361
1
vote
Matching algorithm in an order batching problem
It seems the problem you are facing is very similar to the storage location optimization and is categorized into the warehouse optimization field and the following heuristic approach is highly ...
- 8,390
1
vote
Matching algorithm in an order batching problem
It seems to be a maximal clique problem. The larger the clique (subset of vertices- orders with a common storage area as edge) smaller will be number of storage areas covered.
Seems there's no ...
- 3,343
1
vote
What are the most popular papers on Uber-type spatial matching?
I advise you to look at the following paper. The authors look at pure online strategies where a decision is made instantly but also look at re-optimization strategies.
Bertsimas, D., Jaillet, P., &...
- 1,461
1
vote
Finding an augmenting path or cycle in weighted graph
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 ...
- 2,925
Only top scored, non community-wiki answers of a minimum length are eligible