patternMinor
Max flow with priorities
Viewed 0 times
withprioritiesmaxflow
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#82553, answer score: 4
Revisions (0)
No revisions yet.