2
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ If you want to require that exactly two $o$'s are assigned to every $p$, well, that's a lot of constraints. I don't see how you can get around it. $\endgroup$ Commented Jul 17, 2021 at 16:32
  • $\begingroup$ Hmm, if there is no easy solution, it would explain why I could not find one ;) $\endgroup$ Commented Jul 17, 2021 at 20:08
  • $\begingroup$ To clarify, it's not about assigning exactly two, but distributing approximately evenly. So, if there are 8 o's and 3 p, a suitable assignment would be 3, 3, 2. $\endgroup$ Commented Jul 17, 2021 at 20:10

1 Answer 1

Reset to default
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I guess, what I head in mind is your point 4. But how to get these absolute deviations? How do I count the assigned o's for each p to calculate the deviation? $\endgroup$ Commented Jul 17, 2021 at 21:28
  • $\begingroup$ Thank you very much. Your answer was a great help and I could solve the problem as described. $\endgroup$ Commented Jul 19, 2021 at 14:10

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.