python-3.x - OR-Tools：向最小成本流类添加约束？

Question

我正在尝试使用 or-tools 解决供应链网络流量问题。我有对弧的容量和需求的需求和供应节点。我已经设法使用 SolveMaxFlowWithMinCost() 获得了最佳结果。

但我正在尝试找到一个解决方案，其中每个需求节点只能由 1 个供应节点提供服务。无论如何我可以将此约束添加到模型中吗？

标签： python-3.xor-tools

Answer 1

直觉反应是，您不能对最小成本流添加任何约束，也不能期望任何属性，如公平。一旦你这样做了，你就将复杂性从多项式（最小成本流）更改为 NP 完全。

您可以尝试使用整数求解器（MPSOlver、CP-SAT），但性能会差很多。

您还可以尝试对最小成本流的输出进行后处理以修复分配。

最后一个想法，您可以使用最小成本流分配来限制 NP 求解器的模型（例如，仅保留出现在最小成本流中的弧线）。