3
$\begingroup$

Here is the problem:
enter image description here

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?

$\endgroup$
2
$\begingroup$
  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.

$\endgroup$

Your Answer

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