Resource allocation- Matching

2
votes

I've got a problem which I'm not sure can be solved by Linear Programming. Essentially there are 2 groups of people who are list their preference for one another and will be subsequently matchd. I'm writing an algorithm for this. Group A has upto 4 choices from Group B and vice versa.

In formulating a solution, I am currently assigning a cost to each combination of pairs. For example if Person 1 from Group A ranks Person 3 from Group B as his/her number 1 choice and vice versa, then the cost is minimal (Pair 1-3 cost: 0.01). Similarly, I would allot a cost to other pairs, devising an objective function which seeks to have pairings which minimize overall cost.

However, I do not see this being feasible because I don't know how to define my constraints and overall objective function. Reading online and from textbooks, I find resource allocation problems to be different from what I am trying to do.

Can I seek your advise on how to proceed?

1
algorithmlinear-programming
This looks more like maximum weight matching in bipartite graph than like linear programming or any of its variants. I won't go so far as to say you can't solve the problem with linear programming, but the other approach might be easier to start with. - High Performance Mark
Smells like Stable Marriage Problem. - Terry Li
Yes, there are similarities to Stable marriage problem (SMP), but this problem is more general than that. The SMP solution displays a certain property (no mutual higher preferred matches for a pair) but the OP's problem is more generalized with minimum total cost desired. - Ram Narasimhan
I find the stable marriage problem good because of the definition of a stable pair. Also, implementing it avoids the hassle of developing costs for pairings outlined in the LP solution below (I've explained why in the comment section). Thanks! - Roy

1 Answers

0
votes

Your problem can be formulated as an "Assignment Problem." As a canonical case, assignment problems are for assigning "jobs" to "machines." They can just as easily be used for Matching two sets.

Here's the formulation: Two sets of people A and B

Decision Variable Xij

Let Xij be 1 if person i (ith person in set A) is matched with jth person in set B; 0 otherwise

Parameters: Let Cij be the cost of pairing person i with person j

Objective Function: Minimize (Sum over i) (sum over j) Cij * Xij

Constraints:

Every Person i gets paired exactly once

Sum over j Xij = 1 (for each i)

Every Person j gets paired exactly once

Sum over i Xij = 1 (for each j)

Xij are Binary variables

Xij = (0,1)

The neat thing about Assignment problems is that the optimal pairings can be found using the fairly easy to understand 'Hungarian Method.' You can also use an LP/IP solver you have at your disposal.

Hope that helps.