Plus court chemin

Bien.

Le programme linéaire

Mais comme vous êtes arrivés sur cette page, vous avez conçu le bon modèle.

Il faut une variable de décision par arc. Puis d’une part il faut des contraintes de conservation de flot, indiquant que pour chaque sommet v différent de la source ou de la destination, que le nombre d’arcs entrants sélectionnés est égal au nombre d’arcs sortant sélectionnés. D’autre part il faut aussi des contraintes pour forcer à ce qu’aucun arc sélectionné n’entre dans la source et exactement un arc sélectionné sorte de la source. Ces mêmes contraintes pourraient être imposées également à la destination, mais ce n’est pas nécessaire. Comprenez vous pourquoi ?

Comme il est montré plus bas, on peut se passer des contraintes d’intégralité sur les variables. Et même on peut se passer de la borne supérieure de 1 sur les variables.

param source = 283492455;
param target = 283494345;
param multiplicity = 3;

set V;                    # vertices
set A within {V cross V cross 0..multiplicity-1}; # arcs
param longitude{V};
param latitude{V};
param time{A};

cd /Users/durr/Documents/Enseignement/CentraleSupelecOPT/optim/data/man;

table ManV IN "man_v.tab": V <- [V], longitude, latitude;
read table ManV;

table ManA IN "man_a.tab": A <- [arc_src, arc_dst, id], time;
read table ManA;

var x{A}, >= 0;

minimize path_length: 
    sum{(u, v, i) in A} time[u ,v, i] * x[u, v, i];

subject to Start:  
    sum {(source, v, i) in A} x[source, v, i] - sum {(v, source, i) in A} x[v, source, i] == 1;

subject to Balance {v in V diff {source, target}}:
    sum {(u, v, i) in A} x[u, v, i] = sum {(v, u, i) in A} x[v, u, i];

Forme alternative

# sans la contrainte Start

subject to Balance {v in V}:
    sum {(u, v, i) in A} x[u, v, i] - sum {(v, u, i) in A} x[v, u, i] = 
        (if v == source then 1 
         else if v == target then -1 
         else 0);

Visualisation

Preuve de l’intégralité du programme linéaire

On rappelle: on veut minimiser \(\sum_{a} c_a x_a\) avec \(x\geq 0\) et les contraintes suivantes où s est la source et t la destination.

\[ ​ \forall v\in V: \sum_{u:uv\in A} x_{uv} - \sum_{u:vu\in A} x_{vu} = f_v \]

avec f(v) étant -1 pour v=s, +1 pour v=t et 0 sinon.

Considérons la méthode itérative suivante pour trouver une solution entière optimale au programme linéaire.

P = multi-ensemble vide
tant que l'ensemble des arcs A n'est pas vide:
    soit x une solution optimale au programme linéaire ci-haut.
    enlever tous les arcs a avec x_a=0
    s'il existe un arc a=uv avec x_a entier, alors
        ajouter x_a copies de a à P,
        enlever a du graphe,
        incrémenter f(u) de x_a,
        et décrémenter f(v) de x_a.
retourner P

On va montrer qu’à tout moment l’algorithme a une arête \(a\) avec \(x_a\) entier et peut ainsi progresser. L’optimalité suit simplement par induction.

Soit x une solution optimale point extrême avec \(x_a>0\) pour tout arc a. Pour une preuve par contradiction supposons qu’aucun arc n’ait une valeur entière.

D’abord nous montrons qu’il existe un chemin de s à t dans le graphe. Soit S une s-t-coupe, donc un ensemble de sommets contenant s mais pas t. En sommant toutes les contraintes associées aux sommets de S on trouve que la valeur des arcs entrants en S moins la valeur des arcs sortants de S est -1. Il existe donc au moins un arc sortant de S.

Ceci nous permet de montrer qu’il existe un chemin de s à t. Initialement S est le singleton {s}, et T est vide. Tant que S ne contient pas t, on fait l’opération suivante. Par l’observation suivante il existe un arc uv sortant de S. Alors on ajoute v à S et uv à T, et on recommence. Quand la procédure termine, T contient un chemin de s à t.

Soit n le nombre de sommets qui ne sont pas isolés, donc ont au moins 1 arc entrant ou sortant. Comme la partie droite des contraintes est entière, et qu’aucun arc n’a de valeur entière, la partie gauche des contraintes est composée d’au moins 2 arcs. Chaque arc contribuant à deux contraintes, on peut conclure qu’il existe au moins n arcs.

D’un autre côté, comme on est en présence de contraintes d’égalité, il faut les considérer toutes comme saturées. Quand on somme les parties gauche des contraintes sur tous les sommets on obtient 0, car chaque arc contribue exactement une fois positivement et une fois négativement dans la somme. Ce qui veut dire que le nombre de contraints saturées linéairement indépendants est au plus n-1. Ceci nous donne la contradiction avec le lemme du rang, qui permet de conclure la preuve de l’intégralité de x.

Maintenant on va montrer que P est un chemin de s à t. Comme P est décrit par une solution entière, les contraintes impliquent que P est constitué d’un chemin de s à t (même preuve itérative que ci-haut) et d’une collection de cycles. Par l’hypothèse que tous les cycles ont un poids positif, on peut utiliser l’optimalité de x pour conclure que P ne contient pas de cycle.

suite