optimization - 具有边缘投资成本的最小成本流

Question

我想使用 python Min-Cost Flow 求解器来构建新的网络。这意味着我有一个初始完整图，顶点是供应商或有需求。使用该算法应该告诉我，根据他们的成本，将使用哪些边来解决所有需求。与现有问题不同的是，一条边在使用时的成本不仅用单位成本来描述，而且还有与流量无关的这条边的投资。我一直在研究 networkx 和 or-tools 的源代码，但无法弄清楚如何调整它们以实现边缘的投资成本。有人有更好的主意或可以帮助我调整代码吗？

最好的问候贾斯图斯

标签： optimizationgraphnetworkxor-toolscost-based-optimizer

Answer 1

您无法使用标准图形算法（例如：MinCostFlow）解决此问题。相反，您需要将其制定为混合整数程序。你可以从这个例子开始：

https://developers.google.com/optimization/assignment/assignment_mip

但是你需要稍微调整一下：你需要两类决策变量：（invest_var二元）和flow_var（连续）。目标将如下所示：

min: sum(flow_cost[i,j]*flow_var[i,j]) + sum(invest_cost[i,j]*invest_var[i,j])
And you need to add an additional constraint for each link:
flow_var[i,j] <= BIG_INT * invest_var[i,j]

这些限制flow_var为0if的目的invest_var是0。需求和供应约束将与示例中的类似。 BIG_INT是一个常数。您可以将其设置为：

BIG_INT=max(flow_upper_bound[i,j])

其中 flow_upper_bound 是 flow_var 变量的上限。

请注意，问题现在变成了一个混合整数线性程序，而不仅仅是一个线性程序。