From: israel@math.ubc.ca (Robert Israel)
Newsgroups: sci.math
Subject: Re: Help needed on problem. "Married couple"-variant?
Date: 22 Sep 1996 18:36:44 GMT

In article <01bba86b$a08bbca0$780464c3@Jocke.algonet.se>, "Joakim Spångberg" <joakimsp@algonet.se> writes:
|> I would need some help on this problem. I'm trying to build a software 
|> that should distribute x people into y groups (eg. Bridge tables or
|> discussion groups). Each person has made a preference list for all
|> other persons. This gives me a two dimensional matrix with values.
|> I want a routine that finds the distribution of people that gives the 
|> highest "score". 

If I understand you correctly, the problem is this: 
Let a[i,j] be person i's preference for person j.
You want to assign the people to the groups so each group has a specified 
number of people, each person is in one group, and the sum of the a[i,j] 
for i and j in the same group is maximized.

I'm pretty sure this is an NP-complete problem (it can be thought of as
a version of the Quadratic Assignment Problem).  Thus it will be very
hard to solve exactly if x is at all large.  You might try a simple
heuristic approach of assigning people one-by-one to the groups that seem
best, and then look for ways to interchange two people to improve the score.
If you want something more sophisticated than this, Simulated Annealing or 
Tabu Search is likely to give pretty good results.  

Robert Israel                            israel@math.ubc.ca
Department of Mathematics             (604) 822-3629
University of British Columbia            fax 822-6074
Vancouver, BC, Canada V6T 1Y4