# Linear Optimization Problem - Assign Objects to People

Say you have a 100x5 matrix of integers between -10 and 10, including zero. Each row represents an object; each column represents a person's ranking of the objects. Of the possible ranking values [-10,10], the only value that may repeat for a given person (i.e., within a given column) is 0. All the other ranking values must be used exactly once in each column. Therefore, the sum of the data in every column is 0, because -10 cancels out 10, -9 cancels out 9, etc. Additionally, every column has 20 values which are nonzero and 80 values which are zero. Any number of duplicates across any given row are possible.

The goal is to determine, for each row, which person (i.e., which column) "wins" that object. The goal is to dole out the objects to the people such that the sum of that person's rankings for the objects they won is equal (or as close to equal as possible) for all five people.

As a trivial example, if we only had 5 rows instead of 100, and ranking values [-2,2]:

Person |  A  |  B  |  C  |  D  |  E
Obj1   | -2  | -1  | -1  |  0  |  1
Obj2   |  0  |  0  |  1  |  2  |  2
Obj3   | -1  | -2  |  2  |  1  | -1
Obj4   |  2  |  2  | -2  | -1  |  0
Obj5   |  1  |  1  |  0  | -2  | -2


Obviously there aren't enough rows here to allow for duplicates, but that's not important.

Additionally, as a constraint, each person must end up with the same number of objects. So in our example, each person would get one of the five objects, and the sum of the rankings assigned to each person would be as close to equal as possible. We can assume that the number of objects will be divisible evenly into the number of people, so with 5 people it'd be 5, 10, or 15 objects, and so on.

Just from "eyeballing" the solution to this problem, I would assign Obj1 to E, Obj2 to C, Obj3 to D, Obj4 to B, and Obj5 to A. This may not be the best solution, but it gives a score total of 1 to everyone except B, who gets a score of 2. In our case, there's no way to give a score of 1 to everyone, nor a score of 2 to everyone, because Obj1 doesn't have any 2s and Obj4 doesn't have any 1s. This is a possibility we have to anticipate.

Also, in my original formulation of the problem as a 100x5, there are going to be quite a few rows where the values are [0,0,0,0,0] -- zeroes all the way across. For these, assigning them randomly or arbitrarily to people is acceptable.

I think this is a linear programming problem, but I can't quite wrap my head around how to set it up so that I can solve it in e.g. GNU Octave's glpk plugin. How can I determine what my objective function is? How do I know my constraints? I'm pretty sure it's a maximization problem, but it's currently formulated in a way that I can't just enter the matrix as-is as constraints into an LP solver.

-
I think that the objective of making everyone's total score nearly equal is going to be a hard one to implement. To begin with, you'll have to come up with a precise definition of "as equal as possible". Is $2,2,2,2,-2$ more equal, or less equal, than $2,2,1,1,0$? And it's strange that you would prefer $-2,-2,-2,-2,-2$ to $2,2,2,2,1$ on the grounds that it's more equal, even though it gives everyone the object he/she wants least. – Gerry Myerson Aug 29 '12 at 1:53
A great comment because it points out a flaw in my constraints. I suppose it will have to be more complicated, then. I suppose the proper solution would be to create a sorted two-column list with column A being the sum of the point values of the assigned object-person pairs, and column B being the maximum delta between any two of the point-totals of the people. Then sort by Column A followed by Column B (column A gets precedence). This strategy would prefer 2,2,2,2,1 over -2,-2,-2,-2,-2 and would prefer (if it were a possible assignment, which it isn't in our example) 2,2,2,2,2 over 2,2,2,2,1. – allquixotic Aug 29 '12 at 13:40
I don't believe you'll get a linear program (LP) eventually anyways. But you might be better off trying with an integer linear program (ILP) first and see if it can be simplified to an LP afterwards. Regarding the ILP, try assigning a separate 0-1 variable $x_{ij}$ to each person $i$ and each object $j$ that takes the value $1$ if person $i$ receives object $j$ and zero otherwise. From there, all your constraints (whatever they end up to be) are easy to enforce. – Gabor Retvari Sep 15 '12 at 17:40