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:
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$.