matching algorithm

Question

I'm writing an application which divides a population of users into pairs for the purpose of performing a task together. Each user can specify various preferences about their partner, e.g.

• gender
• language
• age
• location (typically, within X miles/kilometers from where the user lives)

Ideally, I would like the user to be able to specify whether each of these preferences is a "nice to have" or a "must have", e.g. "I would prefer to be matched with a native English speaker, but I must not be matched with a female".

My objective is to maximise the overall average quality of the matches. For example, assume there are 4 users in the system, A, B, C, D. These users can be matched in 3 ways:

Option 1     Match Score
A-B           5
C-D           4
---
Average       4.5

Option 2     Match Score
A-C           2
B-D           3
---
Average       2.5

Option 3     Match Score
A-D           1
B-C           9
---
Average       5

So in this contrived example, the 3rd option would be chosen because it has the highest overall match quality, even though A and D are not very well matched at all.

Is there an algorithm that can help me to:

• calculate the "match scores" shown above
• choose the pairings that will maximise the average match score (while respecting each user's absolute constraints)

It is not absolutely necessary that each user is matched, so given a choice between significantly lowering the overall quality of the matches, and leaving a few users without a match, I would choose the latter.

Obviously, I would like the algorithm that calculates the matches to complete as quickly as possible, because the number of users in the system could be quite large.

Finally, this system of computing match scores and maximising the overall average is just a heurisitic I've come up with myself. If there's a much better way to calculate the pairings, please let me know.

Update

The problem I've described seems to be a similar to the stable marriage problem for which there is a well-known solution. However, in this problem I do not require the chosen pairs to be stable. My goal is to choose the pairs so that the average "match score" is maximized

Answer 1

What maximum match algorithms have you been looking at? I read your question too hastily at first: it seems you don't necessarily restrict yourself to a bipartite graph. This seems trickier.

Answer 2

I believe this problem could be represented as a linear programming problem. And then you can use Simplex method to solve it.