Linear programming: Optimize even distribution

integer programminglinear programming

I hope this is the right place to ask this question.
I'm solving a problem with linear programming, but there is a certain aspect for which I don't have an efficient idea.

I have a number of people p_1 to p_n and a set of other people o_1 to o_m that are assigned to the p's according to some constraints – this is working.

Now I have another constraint (or precisely, two) which I want to incorporate. However, I don't have a real idea for it.
The overall goal is that the o's are evenly distributed among the p's.

Let me give a small example: Let's assume we have p_1, p_2 and p_3 and 6 o's to assign – i.e. two to each p_x. According to the other constraints, assignments could be made so that assigning even all 6 people to e.g. p_2 wouldn't violate the optimality. Hence, I have to introduce new constraints now.

My problem is that I cannot formulate the required constraints.
The only thing I have currently is the list of binary variables p_x__o_y (1 iff o_y is assigned to p_x, 0 otherwise). So, basically, I'd need something like summing up these variables and penalize it when it deviates from the ideal value of two. I know how to solve the issue of working with absolute values, but for the summation, I don't have an idea.

Please note that the number of o's is not known in advance. I can assume a certain upper bound such as 20, but introducing binary variables for every p_x that are 1 iff the number of o's matches the corresponding number (e.g. b_p_1_1 is 1 if one o is assigned to p_1, b_p_3_19 is 1 if 19 o's are assigned to p_3 etc.) appears to be a lot of "overhead" to me as I would have to check all possible combinations of p_x__o_y that lead to said 1 or 3 or so assigments.

Is there a better solution?

Thanks and best!

Best Answer

Here are four common linearizable approaches to achieving balance/fairness/evenness:

  1. Maximize the minimum value.
  2. Minimize the maximum value.
  3. Minimize the range, that is, the difference between the maximum and minimum values.
  4. Minimize the sum of absolute deviations from some ideal value.

For #4, let binary decision variable $z_{p,o}$ indicate whether person $p$ is assigned person $o$. Introduce nonnegative surplus and slack variables $s_p$ and $t_p$, impose linear linear constraints $$\sum_o z_{p,o} - s_p + t_p = 2$$ for all $p$, and minimize $$\sum_p (s_p + t_p).$$ The values of $\sum_o z_{p,o}$ will all equal $2$ if and only the optimal objective value is $0$. If you don't know the value $2$ ahead of time, you can instead replace it with a single continuous variable $v$.

Related Question