Flot maximum

Oui le nombre maximum de chemins arcs disjoints entre la source et la destination est 3. Il ne pouvait pas être beaucoup plus grand d’ailleurs, car source et destination sont des carrefours à 4 branchements.

On trouve la solution avec un programme linéaire suivant.

param graphfile := "man.txt";
param source := 283492455;
param target := 283494345;

set V := { read graphfile as "<2n>" comment "a"};
set A := { read graphfile as "<2n,3n>" comment "v"};

var x[A] >=0 <=1;   # selected arcs

maximize flow:
     sum <source,u> in A: x[source,u];

subto no_flow_into_source:
    forall <v, source> in A: x[v, source] == 0;

subto flow_conservation:
    forall <v> in V - {source, target}:
        sum <u,v> in A: x[u,v] == sum <v,u> in A: x[v,u];

Présence de cycles

Mais qu’elle est donc cette solution trouvée par SCIP ?

Elle contient 3 chemins arcs disjoints de la source à la destination. Mais également plusieurs cycles disjoints. Ces cycles satisfont toutes les contraintes et n’interviennent pas dans la fonction objectif. Modifiez le programme linéaire pour obtenir une solution sans cycles.

suite