2
$\begingroup$

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:

enter image description here

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Beautiful solution. $\endgroup$ – D.W. Oct 18 '17 at 22:33
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for the answer. There's something I don't understand. In the circulation problem, you set a minimum for the flow on certain edges. How can you express $N_1\geq t$ as such? $\endgroup$ – Benoit Sanchez Oct 17 '17 at 16:46
  • $\begingroup$ @BenoitSanchez, see edited answer. I added the part below the horizontal line to explain that part. $\endgroup$ – D.W. Oct 18 '17 at 22:31
  • $\begingroup$ Thanks a lot. This definitely works (actually, I found my own solution while working on your idea). $\endgroup$ – Benoit Sanchez Oct 19 '17 at 8:32
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 1. The preference is on the objects instead of the pairs. 2. OP's problem is to maximize $(N_1,N_2)$ lexicographically, instead of to maximize $2N_1+N_2$ (which is the same as the problem you are considering to minimize $N_1+2N_2$). $\endgroup$ – Willard Zhan Oct 16 '17 at 17:45
  • $\begingroup$ I have edited my answer in order to consider the priorities in the objects. It is still not clear what the lexicographic order is used for. Is it just a way to state that the priorities are in increasing order? $\endgroup$ – klaus Oct 17 '17 at 3:43
  • $\begingroup$ The lexicographic order means you first maximize $N_1$, then maximize $N_2$. So the resulted flow might even not be a max flow (or maybe, but you have to prove it). $\endgroup$ – Willard Zhan Oct 17 '17 at 4:19
  • $\begingroup$ Minimizing $N_1+2N_2$ is not ok for lexicographical order. But if you replace 1 by 0 and 2 by 1, this seems to work. You maximize $N_1+N_2$ (flow) and then you minimize $N_2$ (cost) for this flow. Am I right? $\endgroup$ – Benoit Sanchez Oct 17 '17 at 10:17
  • $\begingroup$ @Willard: whether the solution is a max flow is a good question. I tend to think it's true (not sure), but indeed it requires a proof. $\endgroup$ – Benoit Sanchez Oct 17 '17 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.