Tanzir5's blog

How to maximize flow while satisfying lower bounds on flow through individual edges ?

By Tanzir5, history, 8 years ago, In English

I was wondering if there is any way to solve the following problem:

" You are given a network graph. Every edge has two values associated with it: the upper bound of the amount of flow that CAN go through this edge and the lower bound of the amount of flow that MUST go through this edge. If there is no valid way to satisfy lower bound of all the edges, print "Unsolvable" . If there are multiple ways, maximize the amount of flow satisfying the lower bounds and upper bounds. You have to report the maximum amount and also the amount of flows through individual edges. "

I don't know of any online judge that has this problem. It's a random problem that came to my mind.

  • Vote: I like it
  • +25
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

This is known as Maximum Flow with edge demands. You can read about it here. Link

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. I actually wanted to know if it is possible to print the amount of flow that goes through individual edges in the best solution. I somehow missed that part. I've edited the post.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    That link doesn't work anymore but can be recovered with Wayback Machine. Link

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Tanzir5 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

actually it exists here on codeforces : problem B reactor cooling 2002-2003 Winter Petrozavodsk Camp, Andrew Stankevich Contest 1 (ASC 1)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks.

    But this problem doesn't ask to maximize the flow. It just wants any solution where we can meet the constraints given.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Since you can already solve lower bounds, you can just add a new super-source connected to the real source via a single edge, and use binary search to determine the maximum possible lower bound on that edge for which a feasible flow still exists.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        As far as I know, if lower bounds can be satisfied in any way, then the max flow satisfying that lower bound and the max flow that we get without satisfying any lower bound are both actually equal. That is, satisfying lower bounds does not change the amount of max flow.So there is no need for binary searching. But I had problems with printing the flow going through individual edges in such a solution.

        But your comment has given me an idea about printing the solution. We should at first check if lower bounds can be satisfied.Then we should run normal max flow algorithm on the input graph without any lower bound just to know the maximum flow. Then we should add a new super sink and add an edge from the sink to the super sink. The lower bound on that edge should be equal to the maximum flow. After doing this, if we run the algorithm for lower bound on the modified graph with all the lower bound constraints and then print the flow for individual edges, this should work I guess.

        Thanks. :D

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          If I understand your first paragraph correctly then I think you're mistaken, actually satisfying lower bounds of flow on edges can make the max flow less than without satisfying them.

          Here's an example (each row describe an edge and has four integers "from", "to", "lower bound", "upper bound"): compute max flow from vertex 1 to 4

          1 2 0 1
1 3 0 1
2 4 0 1
3 4 0 1
2 3 1 1

          max flow not satisfying lower bounds is 2 while max flow satisfying it is 1

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh. I was wrong then. So we do need to binary search on the maximum flow. Thanks.

            → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Another problem, which requires you to maximize the flow, is Captain America. This one is not as straightforward, though, so if you just want to test your implementation then you might want to take a look at the editorial.

      And here is my solution, in case it helps: 19731371

      → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

"No online judge has this problem" LOL, this is like an introductory network flow problem.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Edited the post.

    Can you give me a link of an online judge where I can find this problem ?

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Tanzir5 (previous revision, new revision, compare).

→ Reply