cplexoplford-fulkerson

Has anyone used Ford Fulkerson's algorithm in OPL?


I have a problem that can be modelise with a graph, need to implement it with opl and apply a maximization with Ford Fulkerson's algorithm. I didn't find anything made with opl...


Solution

  • Ford Fulkerson is a technique to solve max flow.

    Linear programming is a given technique to tackle max flow

    Python CPLEX example in https://gist.github.com/ZaydH/b1b09deb1873d8018fdd7cce139d0878

    can be rewritten in OPL CPLEX:

    {string} nodes={"s","a","b","c","e","t"};
    
    tuple edge
    {
      key string o;
      key string d;
      float capacity;
    }
    
    {edge} edges with o,d in nodes=
    {
      <"s","a",1>, 
      <"s","b",9>, 
      <"s","c",9.5>,
      <"a","e",2>, 
      <"b","e",5>, 
      <"b","t",4>, 
      <"c","b",2>, 
      <"c","t",3.5>, 
      <"e","t",3>
    };
    
    dvar float+ flow[e in edges] in 0..e.capacity;
    
    maximize sum(e in edges:e.o=="s") flow[e];
    
    subject to
    {
      // flow conservation
      forall(n in nodes diff {"s","t"}) 
        flowConservation:
          sum(e in edges:e.o==n) flow[e]==sum(e in edges:e.d==n) flow[e];
    }
    
    execute
    {
      for(var e in edges)
       writeln(e.o," -> ",e.d," : ",flow[e]);
    }
    

    which gives

    // solution (optimal) with objective 10.5
    s -> a : 0
    s -> b : 7
    s -> c : 3.5
    a -> e : 0
    b -> e : 3
    b -> t : 4
    c -> b : 0
    c -> t : 3.5
    e -> t : 3