Distribute labelled balls among labelled boxes as evenly as possible

Question

Please help in solving the following problem:

"Given a collection of labelled balls and labelled boxes, each ball must be placed in one of the boxes. However balls are restricted to which boxes they can be placed in, and the objective is to distribute the balls among the boxes as evenly as possible."

For example we have 3 boxes and 12 balls.

Rules are the following:

ball1 can only be placed in subset of boxes [box1, box2, box3]
ball2 can only be placed in [box1]
ball3 can only be placed in [box1]
ball4 can only be placed in subset of boxes [box1, box2]
ball5 can only be placed in subset of boxes [box1, box2]
ball6 can only be placed in subset of boxes [box1, box3]
ball7 can only be placed in [box2]
ball8 can only be placed in [box2]
ball9 can only be placed in subset of boxes [box2, box3]
ball10 can only be placed in [box3]
ball11 can only be placed in [box3]
ball12 can only be placed in [box1]

A given ball is of count 1 and can be put only in 1 box (it cannot be placed in 2 or more boxes at the same time).

So that balls can be natively spread between boxes in the following way:

box1 {ball2, ball3, ball5, ball12}
box2 {ball4, ball7, ball8, ball9}
box3 {ball1, ball6, ball10, ball11}

Could you please point me to possible approaches that could help in solving such type of a problem?

I checked the similar questions and in most cases number of possible distributions has to be discovered. But for this particular problem the task is to minimize the difference of the number of balls among the boxes. For now that I found is this paper that is close to the problem: https://qspace.qu.edu.qa/bitstream/handle/10576/8020/06-02-15-0012-fulltext.pdf?sequence=8 Still having some difficulties in implementing fair distribution according to proposed formulas.

Thanks.

Answer 1

You can solve the problem via integer linear programming as follows. For ball $i$, let $J_i$ be the set of allowed boxes. Let binary decision variable $x_{i,j}$ indicate whether ball $i$ is assigned to box $j$. Let $y_\min$ and $y_\max$ be the smallest and largest number of balls in a box, respectively. The problem is to minimize $y_\max-y_\min$ subject to

\begin{align} \sum_{j\in J_i} x_{i,j} &= 1 &&\text{for all $i$} \tag1 \\ \sum_{i:j\in J_i} x_{i,j} &\ge y_\min &&\text{for all $j$} \tag2 \\ \sum_{i:j\in J_i} x_{i,j} &\le y_\max &&\text{for all $j$} \tag3 \end{align} Constraint $(1)$ assigns each ball to exactly one box. Constraints $(2)$ and $(3)$, together with the objective, enforce the definitions of $y_\min$ and $y_\max$.

For your example, an optimal solution $x_{i,j}$ is as follows, with $y_\min=y_\max=4$ balls in each box:

   1 2 3 
 1 0 0 1 
 2 1 0 0 
 3 1 0 0 
 4 1 0 0 
 5 0 1 0 
 6 0 0 1 
 7 0 1 0 
 8 0 1 0 
 9 0 1 0 
10 0 0 1 
11 0 0 1 
12 1 0 0 

Answer 2

I'll draw your attention to a way of formulating the problem as a maximum bipartite matching. That is, take the labelled balls as one set of vertices (we will define another set of boxes to be the other "part" of the bipartite graph).

Now the number of boxes is typically less than the number of balls (as your example illustrates). Since your goal is to make the counts of balls in those boxes as equal as possible, let's create copies of the boxes to hold one ball apiece, according to how many times the initial number of boxes, say $k$, goes into the total number of balls, say $n$. If we can assign all the balls after we make $\lceil n/k \rceil$ copies of each, then that would give the most equal assignment possible. If we cannot, then we can increase the number of copies for boxes one at a time, until eventually we arrive at an assignment that is the most equal possible.

Let's illustrate the idea with your example. The number of boxes $3$ goes into the number of balls $12$ exactly four times, so we create four copies of each box. These copies obey the same restrictions as their initial counterparts.

Figure 1: Balls mapped to copies of boxes

Now apply a standard algorithm to get a maximum matching between the balls and the copies-of-boxes. If it succeeds in assigning every ball to a box, we are done (equally as possible distributed, once all the copies of a box are recombined). If it fails, proceed to increase the number of copies of boxes by one (thereby allowing more slack in the unequal number of balls per box).