具有边缘投资成本的最小成本流
我想使用python最小成本流解算器来构建新的网络。这意味着我有一个初始的完整图，顶点要么是供应商，要么是有需求的。使用该算法应该告诉我，根据它们的成本，将使用哪些边来解决所有需求。与现有问题不同的是，一条边在使用时的成本不仅用单位成本来描述，而且还有一条边的投资，该投资与流量无关。我一直在研究networkx和/或工具的源代码，但不知道如何调整这些代码以实现Edge的投资成本。是否有人有更好的想法或可以帮助我调整代码？
向Justus致意
共有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]
如果invest_var是0，则这些约束的目的是将flow_var约束为0。需求和供应约束将与示例中类似。BIG_INT是一个常量。您可以将其设置为：
BIG_INT=max(flow_upper_bound[i,j])
其中flow\u upper\u bound是flow\u var变量的上限。
请注意，问题现在变成了混合整数线性程序，而不仅仅是线性程序。
-
这是最小成本路径动态规划问题的一个变体，让我难倒了。 我得到了一个成本矩阵MXN。成本矩阵有随机放置的正缓冲区和负成本。我从[1,1]开始，必须到[m,n]。我从一个初始缓冲区x开始。在我的遍历过程中，我的缓冲区x永远不应该<=0。如果它变成<=0，那么即使结束状态是一个正缓冲区，也是一个无效的路径（把它想象成一个玩家从一些初始健康开始，负成本扣除健康，而正缓冲区增加健康）。什么是最小的初始缓冲区
-
我有一个最小成本流网络，其中一些弧有固定费用，也就是说，如果弧有非零流量，那么成本是c\u k，与流量无关。0的流产生0的成本。这些圆弧没有容量限制。 我知道如何将其建模为一个混合整数程序（MIP）：添加一个0/1变量，成本为c\k。将arc上的容量设置为M*y\U k，其中M大于所有电源的总和。因此，当且仅当弧有流时，才会产生固定成本。 是否可以使用最小成本流公式来解决此问题，该公式比一般MIP
-
考虑元组（a0，b0），（a1，b1）。。。和2个箱子A和B。将元组放入箱子将花费您美元，放入箱子将花费您美元。将元件放入料仓A和元件放入料仓B的最低成本是多少 我提出了贪婪算法：对元组数组进行排序，将作为键，按降序排列。然而，我们能用动态规划来解决这个问题吗？如果有bin而不是两个呢。
-
我正在尝试使用MinCostFlow或工具解决一个工程问题。有一个带有管道和多个供应阀的机械分配系统。这些阀门需要连接到用户。起初，我试图用匈牙利算法来解决这个问题，但后来我意识到，这并不考虑通过路径的流。 节点0-4是消费者，节点4-7是供应阀，节点8和9是管道。我在每个消费者身上放了一个“供应”，以显示它期望的流量。我在最后放了一个水槽，以将供应从系统中取出。并非所有消费者都有相同的需求。我们
-
我遇到了这个问题： 你必须乘坐一辆汽车穿过城市的
-
Haskell库中是否存在这种数据结构？我做了一些搜索，但找不到任何有用的东西。我想使用现有的类型，而不是定义我自己的类型——它似乎应该存在。 这个想法是它与Data. Tree非常相似，但是边可以保存信息和节点。 如果你有一个通过树的路径（类型为[e]），你可以在O（log（n））中找到rootLabel（类型为n）。据我所知，你不能用Data做这件事。树，因为您必须扫描每个节点的子节点，以查找