Flot maximum sans cycles
Méthode avec potentiel
Une solution consiste à ajouter des variables de potentiel aux sommets, et à demander que pot[u] + time[v] ≤ pot[v] soit satisfait pour tous les arcs (u,v) sélectionnés.
# constante assez grande
param M := sum{(u,v,i) in A} time[u,v,i];
var potentiel{V};
subject to no_cycle{(u,v,i) in A}:
potentiel[u] + time[u,v,i] <= potentiel[v] + (1 - x[u,v,i]) * M;
Cette solution est lente. Elle a aussi le problème grave de ne pas générer une solution entière. Avec l’ajout des variables et contraintes, le programme linéaire n’est plus totalement unimodulaire. Déjà par ce que certains coefficients des variables dans les contraintes sont -M, donc différent de +1,0 ou -1. Si on arrondi la solution fractionnaire produite en une solution entière, on obtient la solution suivante, où on peut observer encore quelques cycles.
Méthode avec raffinement de l’objectif
Une meilleure solution est de chercher parmi les solutions de flot maximum ceux qui minimisent le nombre d’arcs sélectionnés. Ceci va non seulement éliminer les cycles, mais aussi de trouver une solution courte.
# toute constant au moins le nombre d'arcs ferait l'affaire
param size := sum{(u,v,i) in A} 1;
maximize flow_value:
sum {(source, v, i) in A} x[source, v, i] * (1 + size) - sum{(u,v,i) in A} x[u,v,i] ;