# Tag Info

### 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$...
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/...

### 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 ...

### 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 ...

### 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 ...

### 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 ...
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 ...
Accepted

Accepted

### Graph Theory problem

The problem formulation is as follows: Here is the Pyomo code ...

### 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 ...
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 ...
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$ ...
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 ...
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 ...
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 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 ...

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