cplex - 有人在 OPL 中使用过 Ford Fulkerson 算法吗？

Question

我有一个可以用图建模的问题，需要用 opl 实现它并用 Ford Fulkerson 算法应用最大化。我没有找到任何用opl制作的东西...

Answer 1

Ford Fulkerson 是一种解决最大流量的技术。

线性规划是解决最大流量的给定技术

https://gist.github.com/ZaydH/b1b09deb1873d8018fdd7cce139d0878中的 Python CPLEX 示例

可以用 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]);
}

这使

// 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