Algorithme Out-of-Kilter

Cours basé sur le papier suivant : out-of-kilter.

Aussi appelé algorithme de Fulkerson-Ford (à ne pas confondre avec l’algorithme de flot maximum), l’algorithme out-of-kilter permet de calculer un flot maximal à cout minimal avec des bornes min et max sur les arêtes.

Nous dirons qu’une arête est In-Kilter si elle satisfait les écarts complémentaires, sinon nous dirons qu’elle est Out-of-Kilter (kilter signifie « en bon état »).

La suite des explications provient de : http://www-ist.massey.ac.nz/204302/ Il ne sera pas traduit pour des soucis de compréhension de la logique sous-jacente au sens de « kilter ».

_____________________

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

Ce qui donne le diagramme d’efficacité suivant :

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