Out-of-Kilter algorithm

The course based on the following paper: out-of-kilter.

Also known as the Fulkerson-Ford algorithm (not to be confused with the maximum flow algorithm), the out-of-kilter algorithm calculates a maximum min cost flow with min and max bounds on the edges.

We will say that an edge is In-Kilter if it satisfies the complementary gaps, otherwise we will say that it is Out-of-Kilter (kilter means « in good condition »).

The following text comes from: http://www-ist.massey.ac.nz/204302/

_____________________

Theorem: A feasible solution x* is an optimal solution of the MCF problem if and only if for some set of node potentials π, the reduced costs and flow values satisfy the following complementary slackness conditions for every edge (u,v) in the network:

kilter1

kilter2

kilter3.png

kilter4

kilter5

kilter6

Correctness:

  • Kilter numbers of the edges are non-increasing
    • Two operations in the algorithm affect the kilter numbers of arcs:
      • updating node potentials
      • augmenting flow along the cycle W
    • At each iteration the algorithm selects and edge (p,q)
      • Makes it in-kilter during potential update
      • decrease it by at least 1 by the flow augmentation

The algorithm terminate within O(mU) iterations, total runtime is : O(m^2 U+mUn log n)

Publicités