Skip to main content
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$...
Marcus Ritt's user avatar
  • 2,725
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/...
Matthew Galati's user avatar
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 ...
Joris Kinable's user avatar
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 ...
Lars H's user avatar
  • 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 ...
batwing's user avatar
  • 1,508
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 ...
RobPratt's user avatar
  • 32.3k
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 ...
SimonT's user avatar
  • 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^...
Kuifje's user avatar
  • 13.5k
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 ...
RobPratt's user avatar
  • 32.3k
3 votes
Accepted

Graph Theory problem

The problem formulation is as follows: Here is the Pyomo code ...
Optimization team's user avatar
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) ...
prubin's user avatar
  • 39.3k
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}$...
prubin's user avatar
  • 39.3k
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 ...
fontanf's user avatar
  • 2,623
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 ...
prubin's user avatar
  • 39.3k
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$ ...
Reinderien's user avatar
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 ...
A.Omidi's user avatar
  • 8,950
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 ...
Sutanu Majumdar's user avatar
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., &...
PeterD's user avatar
  • 1,636
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 ...
Hexaly's user avatar
  • 2,976

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