Questions tagged [matching]
For questions on matchings, i.e. sets of disjoint edges of an undirected graph.
16
questions
3
votes
2
answers
133
views
Effective methods for solving the assignment and packing problem
There are $m$ items to be allocated into $n$ bins. The profit generated by placing the $i$-th item into the $j$-th bin is $c_{ij}$, and the service level is $s_{ij}$. A allocation scheme is required ...
- 95
1
vote
1
answer
131
views
Exact algorithms for a bin packing problem
There is a one-dimensional bin-packing problem.
There is a collection of items that need to be divided into several groups, with a maximum of M items per group.
Each item includes several characters, ...
- 95
1
vote
2
answers
115
views
Matching algorithm in an order batching problem
There is an order batching problem.
Given a set of orders, they need to be split into several batches, with a maximum order number of M per batch.
Each order needs to be picked from multiple storage ...
- 95
1
vote
1
answer
62
views
What are the most popular papers on Uber-type spatial matching?
This is probably one of those "just google it" kinds of questions, but is there a commonly-accepted "definitive" model in the literature for capturing the kind of matching problem ...
2
votes
1
answer
103
views
How do you recover dual variables for a minimum weight bipartite perfect matching problem?
I feel like I must be missing something obvious but this is confusing me. Let's say I have an optimal solution $x^*$ to a minimum-weight perfect bipartite matching problem on $2n$ nodes, $$\min\sum_i\...
- 163
2
votes
2
answers
99
views
Adjust result to equal mode values
The code below is generating the mode value considering the columns Method1, Method2, Method3...
- 319
1
vote
1
answer
111
views
Graph Theory problem
I just got sent a problem that I haven't found any model for thus I do not know how to proceed in solving it, if anybody can show me a similar problem so I can use it as a starting point or if they ...
4
votes
2
answers
99
views
How to bundle pairs of trips?
I have a database of real-time optional trip demands. Each with a load that needs to be delivered from a departure point to a destination:
...
- 141
1
vote
0
answers
82
views
Bipartite matching
If I have two matrix
$$A = \begin{bmatrix}
1 & 2 \\
2 & 3
\end{bmatrix} $$ and $$B = \begin{bmatrix}
3 & 4 \\
5 & 3
\end{bmatrix} $$
We have to make a matching between $A$ and $B$ ...
- 139
2
votes
1
answer
71
views
Maximal Matching in a constrained, unweighted Bipartite Graph
Suppose a set of partially connected nodes:
All nodes are in set A xor in Set B (i.e. Bipartite Graph)
All nodes have a datetime property.
Connections in the ...
- 171
7
votes
2
answers
610
views
Can a generic ILP solver find graph matchings as fast as a specialized algorithm?
Finding a maximum matching, or a maximum-weight matching, is a well-known problem, which has polynomial-time combinatorial algorithms.
It can also be formulated as an integer linear program.
In ...
4
votes
1
answer
73
views
Finding an augmenting path or cycle in weighted graph
Suppose we are given a (simple) graph with non-negative edge weights, along with a matching $M$, which may or may not be max weight. I know that $M$ will be max weight if and only if the graph does ...
- 201
5
votes
2
answers
367
views
Counting the number of matchings in a complete bipartite graph
I am trying to count the number of matchings in a complete bipartite graph (perfect as well as imperfect). It's relatively easy for me to convince myself that there is $n!$ perfect matchings in the ...
- 1,133
2
votes
0
answers
89
views
Problem classification: optimal weights for Weighted Arithmetic Mean
I want to write an optimization problem then solve it, to get optimized weights to compute a final score using a weighted arithmetic mean.
The problem is as follows. I have an entity (an input vector $...
- 534
23
votes
1
answer
344
views
Polynomially solvable problems with exponential extension complexity
The maximum matching problem is solvable in polynomial time using Edmonds' blossom algorithm. However, unlike for example the spanning tree polytope, it has been proven fairly recently that the ...
- 2,305
10
votes
1
answer
206
views
Relationship between the Assignment Problem and the Stable Marriage Problem
Suppose I'm solving a minimum-weight matching problem in a bipartite graph with sets $\mathcal{I}$ and $\mathcal{J}$, where $w_{ij}$ denotes the weight of matching item $i$ to $j$. I can model the ...
- 101