如何求解MCMF问题？现有程序库中是否有已实现的MCMF算法？

求解方法 #

你描述的带供需约束的多源多汇MCMF，首先可以通过加虚拟点的方式转换为标准单源单汇MCMF问题，后续直接调用单源单汇的算法求解即可，转换步骤如下：

• 新增虚拟超级源点S，从S向每一个原有源点连边，边容量设置为该源点的最大供应容量，边费用设为0
• 新增虚拟超级汇点T，从每一个原有汇点向T连边，边容量设置为该汇点的需求上限，边费用设为0
• 原有图中所有带容量、费用的边完全保留不变

转换完成后对新图求解单源单汇最小费用最大流，得到的最大流就是当前条件下可以满足的最大供需规模，对应的总费用就是该流量下的最小成本。如果最大流等于所有汇点的总需求，说明所有需求都可以被满足。

常用的单源单汇MCMF算法可以按需选择：

• SPFA 连续最短路算法：实现门槛低，适合小规模图，只要图中不存在负费用环即可正常运行
• Dijkstra+势能优化（原始对偶算法）：基于Johnson算法思想消除负权边，运行效率远高于SPFA版本，是目前工业实现和竞赛的主流选择，适合中等及以上规模的图
• 消圈算法：仅适用于存在负权环的特殊场景，运行效率较低，常规场景很少使用

现有程序库实现 #

主流编程语言都有成熟的MCMF封装可以直接调用：

• C++
  • 竞赛场景可以直接用ACLib、KACTL等竞赛模板库中的MCMF实现，都是经过优化的原始对偶版本，运行效率很高
  • 工业生产场景可以使用图论专用库LEMON，内置成熟的MinCostFlow类，支持多种算法切换，稳定性有保障
• Python
  • 小规模验证可以直接调用networkx库的min_cost_flow系列函数，调用成本极低
  • 大规模场景可以用谷歌优化工具包ortools的最小费用流接口，效率远高于networkx；二部图场景的MCMF也可以用scipy的稀疏图匹配接口实现
• Java
  • 可以直接使用JGraphT库提供的MinCostFlow实现，支持自定义算法选择，能覆盖绝大多数使用场景

内容的提问来源于stack exchange，提问作者Rahul Kumar