Max flow with priorities

Question

I'm studying a simple max flow problem:

Each type of object $a_1, a_2...$ can be stored in some of several stores $b_1,b_2...$. This is described by this graph:

There are $|a_i|$ objects of the type $a_i$. Store $b_j$ can contain at most $|b_j|$ objects. This shows as capacity constraints on the graph. The other edges have no capacity constraint and just mean "this type of object can be stored in this store". We want to maximize the total number $N$ of objects being stored. Max flow on this graph answers to this question.

Now we add a priority idea. Each type of object $a_i$ has an integer priority $p(a_i)$ say from $1$ to $2$ for simplicity. Instead of maximizing the total number of objects, we want to maximize $(N_1,N_2)$ in lexicographical order where $N_p$ stands for the number of objects with priority $p$ being stored.

Do you see a way to formalize this problem as a flow problem (possibly with a broader meaning than just simple max flow)? Or a way to use max flow algorithms to solve it?

Answer 1

First, build an algorithm to solve the following problem:

Given a threshold $t$ and a flow graph $G$, find the solution that maximizes $N_2$, subject to the requirement that $N_1 \ge t$.

That problem can be solved using algorithms for minimum cost circulation, which is a generalization of max flow where we can also have lower bounds on certain edges. (You'll set the cost of all edges out of the source to 1 and the cost of all other edges to 0, as you don't need different costs.)

Then, do binary search on $t$ to find the largest $t$ for which a solution exists.

---

How do you solve the problem above? We need to modify the graph. Instead of adding a single source vertex $s$, we'll add three vertices $s,s_1,s_2$. Add an edge $s \to s_1$ with lower bound on capacity of $t$. Add an edge $s \to s_2$ with lower bound 0. Add edges $s_1 \to a_i$ for each $i$ where $p(a_i)=1$, and $s_2 \to a_i$ for each $i$ where $p(a_i)=2$. All edges other than the $s \to s_1$ edge have lower bound on capacity of 0. Now any valid flow for this problem that respects the lower bounds will satisfy $N_1 \ge t$.

Answer 2

Thanks to klaus and D.W. answers that helped a lot to find a full solution. Actually, this is a solution without min cost or circulation methods (even though they are possible solutions).

My solution is the following:

• find $N_1$ as the max flow on the graph with nodes corresponding to objects of priority 2 (lowest) removed. The fact it is the $N_1$ we want is straightforward to prove.
• find $N$ the global max flow for the full graph (without priority constraints)
• define $N_2=N-N_1$ (*)
• construct a new graph with 2 additional nodes $s_1$ and $s_2$ between the source and the object nodes, each of them connected to the objects nodes of corresponding priority. Define maximal capacity of $s \rightarrow s_p$ as $N_p$. Solve the max flow. This provides a solution to the problem. (note that only the capacity on $s \rightarrow s_2$ is important)

As raised by Willard Zhan, point (*) requires a proof: $N=N_1+N_2$.

Proof: Consider a maximal solution $(N_1,N_2)$ for the priority problem. Assume it's not a global max flow: $N_1+N_2<N$. Then there is an augmenting path (without cycle) in the residual graph from $s$ to $t$. This path exits only once from the source, providing a way to increase either $N_1$ or $N_2$ and leave the other one unchanged. Both contradict the maximality of $(N_1,N_2)$ for the lexicographical order.

This proof relies on a nice fact about max flow: there is no need to ever decrease the flow on an edge from the source to find a better flow (when there is one).

This solution generalizes easily to any number of priorities. You need to solve as many max flow problems as priorities plus the last one.

Answer 3

I think you can simply put costs in the middle edges and solve a Min-Cost Max-Flow Problem. The idea is to find the maximum flow that has the minimum total cost.

In your problem, the higher the priority, the lower will be the cost. For example, if $a_1$ has priority 1 (highest) and $a_2$ has priority 2 (lowest), you can set all edges that leave an object with its priority:

$$ p(a_1 \rightarrow b_2) = 1$$ $$ p(a_1 \rightarrow b_1) = 1$$ $$ p(a_2 \rightarrow b_2) = 2$$ $$ p(a_2 \rightarrow b_3) = 2$$ $$ ... $$

The algorithm will try to take as much items $a_1$ as possible, because they are cheaper. Then it will try to take as much as possible from item $a_2$ and so on...

The problem here is that your priorities might not be that simple. Using the costs of the example above, you are saying that $a_1 $ is 'two times as preferable as' $ a_2$.