Max Flow Problem

given:

• given a network with N nodes and links among them
• the capacity of the i → j link is C_ij≥ 0 (i,j = 1, …, N)
• 2 distinguished nodes:

constraints:

• capacity constraint: The flow on each link cannot exceed the capacity of the link
• flow conservation: The total outgoing flow of a node minus the total incoming flow of the node must be equal to the source rate of the node. That is, the difference between the flow out and into the node is exactly what the node produces or sinks. For transshipment nodes (b_i = 0) the outgoing and incoming flow amounts are equal

objective:

• find the maximum amount of flow that can be sent through the network from the source to the destination, such that the link capacity is not exceeded on any link and the flow conservation constraint is satisfied at every intermediate (transshipment) node

Linear Programming Standard Formulation

• objective function:
  max Z = Σ_j[x_sj] - Σ_k[x_ks]
• linear constraints:
  xij ≤ C_ij
  Σ_j [x_ij] - Σ_k [x_ki] = 0 # (∀i ≠ s,d)
• non-negative variables:
  ∀_ij [x_ij ≥ 0]

Implementation

• Maximum Flow - Max Flow