Best way to improve max-flow on a DAG

Question

I am considering a problem related to max-flow on a weighted DAG and I saw a number of posts with related questions but nothing that really helps me.

I have a weighted DAG D = (V, A, W), a source S, a target T, and a budget B of weight that I can add to the arcs to increase the flow between S and T. The goal is to maximize the flow between S and T using the budget in the best way possible. Now, a simple solution would be to compute the min-cut, pick $a$ random arc a from the set of arcs identified in this way, add weight of B/alpha to $a$, and restart the procedure alpha times.

I have a few problems with this solutions:

1. since the weights are real, setting alpha is not that easy (but I guess that a large enough alpha will work well in practice)
2. this method is terribly slow
3. I don't have any kind of theoretical guarantee (which I guess can be found but I don't have it yet)

Are you aware of any previous work in this area providing principled and efficient algorithms for this problem?

Answer 1

You can solve the problem via linear programming as follows. Let $x_{i,j} \ge 0$ be the flow across arc $(i,j)$, and let $y_{i,j} \ge 0$ be the weight added to arc $(i,j)$. The problem is to maximize $\sum_{(S,j)\in A} x_{S,j}$ subject to \begin{align} \sum_{(i,j)\in A} x_{i,j} - \sum_{(j,i)\in A} x_{j,i} &= 0 &&\text{for $i\in N \setminus\{S,T\}$} \\ x_{i,j} &\le c_{i,j} + y_{i,j} &&\text{for $(i,j)\in A$} \\ \sum_{(i,j)\in A} y_{i,j} &\le B \end{align}