linear programming and flow network

Question

Here is the problem:

I have hard time understanding the problem , what does it mean by "conservation factors" and how to approach the problem using linear programming.

For what I understand, if a vertex have a total in_flow of 100, and the conservation factor is 50%-80%, then the total out_flow would be in between 50-80% of 100?

Answer 1

1. How to understand the conservation factors?

   It is clearly stated that a[u] * f_in[u] <= f_out[u] <= b[u] * f_in[u], where a[u] and b[u] are some non-negative numbers. I do not understand what is unclear here.

2. For what I understand, if a vertex have a total in_flow of 100, and the conservation factor is 50%-80%, then the total out_flow would be in between 50-80% of 100?

   Yes.

3. How to solve it using linear programming?

   Let's create a variable for each edge(which represents the amount of flow that goes through it). Let's call it x_i. Then we have constrains for each vertex based on its conservation factors(f_in is the sum of variables for in-going edges and f_out is the sum for of variables for the out-going edges). These constraints are expressed as two linear inequalities for each vertex(except the source and the sink). We need to maximize f_out[s], which is, again, a sum of x_i for some i(namely, for those edges that go out of this vertex). So we have reduced it to standard linear programming problem.