arasmus's blog

Convert Linear Programming Problem to Network Flow problem.
By arasmus, history, 8 years ago, In English

Can someone explain (in detail) how can a Linear Programming Problem be converted to a Network Flow problem.
Essentially I wish know how to create the network flow graph given the LP constraints,what edges/vertices to add to the graph and why those edges/vertices are added

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

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

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

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

Also , it would be helpful if anyone can suggest such a practice problem.

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

Where can such a question arise? Not every LP problem can be transformed into a network flow problem (under some natural meaning), network flow LP representation is a very small and strict class.

A general LP problem can define an unbounded feasible set while a network flow LP always defines a bounded polyhedron.

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

    I was actually motivated by this discussion. http://mirror.codeforces.com/blog/entry/45412

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

    But can every network problem be solved by LP?

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

      i came across this comment so you might ask Swistakk

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

      You messed up direction of convertion. As Zlobober says not every LP can be represented as flow. But other way around is surely true. Look at any definition of flow. Variables are flows through every edge. Constraints are of form "influx=outflux" for every vertex and "0<=flow<=capacity" for every edge. Goal is to maximize outflux of source. Everything is perfectly linear, the very definition of flow is already an LP instance, no tweaking needed.

      → Reply