Questions tagged [matching]

For questions on matchings, i.e. sets of disjoint edges of an undirected graph.

Filter by
Sorted by
Tagged with
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 ...
Ying's user avatar
  • 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, ...
Ying's user avatar
  • 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 ...
Ying's user avatar
  • 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 ...
Rebecca Donnelly's user avatar
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\...
Kathryn Twomey's user avatar
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...
Antonio's user avatar
  • 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 ...
lifeispaingulag's user avatar
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: ...
italo's user avatar
  • 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$ ...
Ishaan's user avatar
  • 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 ...
Brondahl's user avatar
  • 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 ...
Erel Segal-Halevi's user avatar
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 ...
t42d's user avatar
  • 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 ...
Djames's user avatar
  • 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 $...
Betty's user avatar
  • 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 ...
Rolf van Lieshout's user avatar
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 ...
tuba's user avatar
  • 101