# Online set filling with redistributions

Edited: Suppose we have 4 sets $A, B, C, D$ which can can hold a maximum of two elements, each.

Now, elements ($E_i$) arrive serially with properties such as:

E1 : Should be placed in either B or C.
E2 : Should be placed in either A or B or C.
E3 : Should be placed in either A or B.


When an element arrives, we have to place the element in one of the 4 sets, immediately i.e. we cannot wait for all elements to arrive, and then decide.

When a new element arrives:

• If there exists space in one or more sets, satisfying the constraints, we place the element in the set with minimum cardinality. Ties are broken randomly.
• If there is no space satisfying the constraints, the existing elements may be redistributed to accommodate the new element.
• If even after redistribution, there is no space satisfying the constraints, discard the new element.

Objective Accommodate the newly arriving elements, while having less number of redistribution.

An illustrative example depicting the problem is attached.

What strategy should i choose to achieve the objective? I need an algorithm for the redistributions that is scalable to large number of sets and more than 2 entry for each set.

In the picture, randomly I have chosen 2 possibilities, one of which yields less number of redistribution than the other. So are there any approaches other than exhaustively checking all possible combinations?

• Please define "best utilization of space" in a precise and quantitative way. How do you plan to measure the utilization of space as a number? Also, you are asking for us to optimize two parameters simultaneously: both maximize utilization and minimize redistributions. However it is likely that you can't do both simultaneously: there's a trade-off. You haven't given us any basis for how you want to trade off one against the other. Do you want to achieve absolute maximum utilization of space, breaking ties by minimizing number of redistributions? Something else? (continued) – D.W. Feb 12 '18 at 19:16
• Please edit the question to make the question well-defined. As it stands I don't think this is answerable. – D.W. Feb 12 '18 at 19:16
• Also, you have an idea so far. So, does that meet your needs? Why have you rejected that idea? Have you tried evaluating that approach? Does it meet your requirements? If not, why not? Have you tried to prove that it meets all your requirements? Have you tried to find a counterexample? Help us help you by exhausting all reasonable avenues on your own, and showing us in the question the progress you've made so far. – D.W. Feb 12 '18 at 19:16
• I don't see a question here. – D.W. Feb 13 '18 at 17:35
• Sorry if i wasn't clear. I'm looking for an approach other than brute force to achieve the objective. I've updated the question to reflect this. – Niloy Saha Feb 13 '18 at 18:10

I can suggest two approaches:

# Brute-force search

First try to find if there is a way to place the element, without redistributing any previously placed elements.

If not, try to find a way to place it, by redistributing exactly one previously placed element. This can be done by enumerating all possibility for which element you redistribute and where you redistribute it to, to see if that leads to a valid placement.

If not, try to find a way to place it, by redistributing exactly two previously placed elements. This involves enumerating all combinations of two previously placed elements to redistribute.

In general, if $n$ elements have been previously placed and $r$ redistributions are needed, this will involve enumerating ${n \choose 0} + {n \choose 1} + {n \choose 2} + \dots + {n \choose r}$ possibilities, which is $O(n^r)$. This might scale OK if you expect $r$ to be very small but becomes slow once $r$ is large.

# SAT solver

To get a more scalable solution, I suggest you use a SAT solver.

There's a natural way to encode your problem as SAT. Introduce boolean variables $x_{i,j}$, meaning that element $i$ gets placed in set $j$ after redistribution. Each constraint is a clause (disjunction of some $x_{i,j}$'s). Also, we can represent the requirement that at most $r$ redistributions be used as the sum of $\neg x_{i,j}$ over all pairs $(i,j)$ that correspond to an element that is currently placed in set $j$ (before redistribution).

Thus, you can represent the problem of finding a solution using at most $r$ redistributions as an instance of SAT, and solve it using an off-the-shelf SAT solver. Use binary search over $r$ to find the minimal number of redistributions needed.

I expect that this will scale much better.

Suppose each set can contain at most $k$ entries.

Consider an arrangement as a flow in a directed graph where

• there is a source node $s$, a sink node $t$, a node $u_E$ for each element $E$, and a node $v_S$ for each set $S$,

• there is an edge with capacity $1$ from $s$ to each element node, an edge with capacity $k$ from each set node to $t$,

• there is an edge with capacity $1$ from $u_E$ to $v_S$ if $E$ can be placed in $S$, and

• a flow with value $1$ for each edge in the path $s\rightarrow u_E\rightarrow v_S\rightarrow t$ is sent to the graph if $E$ is placed in $S$.

In your example, the graph looks like the follows, where edges to $t$ have capacity $2$, and all other edges have capacity $1$.

The flow before redistribution is represented by bold edges in the following graph, where except the three edges indicated, values for other bold edges are all $1$.

Easy to see a redistribution corresponds to an augmenting path. For example, the red path in the following graph shows an augmenting path corresponding to your second possibility.

So the problem turns out to be finding the shortest augmenting path, which can be done by a breadth-first search from $s$. You can read Edmonds–Karp algorithm for more details, which is an algorithm to compute max-flow by repeatedly finding a shortest augmenting path.