注意事项
TypeError: in method 'SimpleMinCostFlow_SetNodeSupply', argument 3 of type 'operations_research::FlowQuantity'
如上报错，是因为传入AddArcWithCapacityAndUnitCost 的参数中含了 numpy.int64 或 numpy数据类型，需要转成内置类型 int。
Maximum Flows
"""From Taha 'Introduction to Operations Research', example 6.4-2."""
from __future__ import print_function
from ortools.graph import pywrapgraph
def main():
"""MaxFlow simple interface example."""
# Define three parallel arrays: start_nodes, end_nodes, and the capacities
# between each pair. For instance, the arc from node 0 to node 1 has a
# capacity of 20.
start_nodes = [0, 0, 0, 1, 1, 2, 2, 3, 3]
end_nodes = [1, 2, 3, 2, 4, 3, 4, 2, 4]
capacities = [20, 30, 10, 40, 30, 10, 20, 5, 20]
# Instantiate a SimpleMaxFlow solver.
max_flow = pywrapgraph.SimpleMaxFlow()
# Add each arc.
for i in range(0, len(start_nodes)):
max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i])
# Find the maximum flow between node 0 and node 4.
if max_flow.Solve(0, 4) == max_flow.OPTIMAL:
print('Max flow:', max_flow.OptimalFlow())
print('')
print(' Arc Flow / Capacity')
for i in range(max_flow.NumArcs()):
print('%1s -> %1s %3s / %3s' % (
max_flow.Tail(i),
max_flow.Head(i),
max_flow.Flow(i),
max_flow.Capacity(i)))
print('Source side min-cut:', max_flow.GetSourceSideMinCut())
print('Sink side min-cut:', max_flow.GetSinkSideMinCut())
else:
print('There was an issue with the max flow input.')
if __name__ == '__main__':
main()
Minimum Cost Flows
task
欲构造data center的traffic变换仿真，输入为二维矩阵，根据论文中的算法给定一些限定条件，求解得到新的拓扑结构。
单纯算Minimum Cost Flows的Demo
与 maximum flows 问题比较，多了 unit_costs 和 supplies
- 若用强约束的 Solve() 求解，则supplies 流入总和等于流出总和，即 supplies 中元素和为0。并且要求 source 流出的supply不能大于其所有流出links上的capacities总和。
- 若用若约束的 SolveMaxFlowWithMinCost()求解，则没有上述两条限制。将以最小的成本计算最大流量。
SolveMaxFlowWithMinCost() Same as Solve(), but does not have the restriction that the supply must match the demand or that the graph has enough capacity to serve all the demand or use all the supply. This will compute a maximum-flow with minimum cost. The value of the maximum-flow will be given by MaximumFlow().
supply 中的负数元素即代表了 demand.
or-tools 中的 AddArcWithCapacityAndUnitCost 支持有向图，节点索引和容量(capacity)必须是非负的，花费 unit cost 可以是任意整数，支持自循环和重复弧。
Adds a directed arc from tail to head to the underlying graph with a given capacity and cost per unit of flow. * Node indices and the capacity must be non-negative (>= 0). * The unit cost can take any integer value (even negative). * Self-looping and duplicate arcs are supported. * After the method finishes, NumArcs() == the returned ArcIndex + 1.
# """From Bradley, Hax, and Magnanti, 'Applied Mathematical Programming', figure 8.1."""
from __future__ import print_function
from ortools.graph import pywrapgraph
def main():
"""MinCostFlow simple interface example."""
# Define four parallel arrays: start_nodes, end_nodes, capacities, and unit costs
# between each pair. For instance, the arc from node 0 to node 1 has a
# capacity of 15 and a unit cost of 4.
start_nodes = [ 0, 0, 1, 1, 1, 2, 2, 3, 4]
end_nodes = [ 1, 2, 2, 3, 4, 3, 4, 4, 2]
capacities = [15, 8, 20, 4, 10, 15, 4, 20, 5]
unit_costs = [ 4, 4, 2, 2, 6, 1, 3, 2, 3]
# Define an array of supplies at each node.
supplies = [20, 0, 0, -5, -15]
# Instantiate a SimpleMinCostFlow solver.
min_cost_flow = pywrapgraph.SimpleMinCostFlow()
# Add each arc.
for i in range(0, len(start_nodes)):
min_cost_flow.AddArcWithCapacityAndUnitCost(start_nodes[i], end_nodes[i],
capacities[i], unit_costs[i])
# Add node supplies.
for i in range(0, len(supplies)):
min_cost_flow.SetNodeSupply(i, supplies[i])
# Find the minimum cost flow between node 0 and node 4.
# if min_cost_flow.Solve() == min_cost_flow.OPTIMAL:
if min_cost_flow.SolveMaxFlowWithMinCost() == min_cost_flow.OPTIMAL:
print('Minimum cost:', min_cost_flow.OptimalCost())
print('')
print(' Arc Flow / Capacity Cost')
for i in range(min_cost_flow.NumArcs()):
cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i)
print('%1s -> %1s %3s / %3s %3s' % (
min_cost_flow.Tail(i),
min_cost_flow.Head(i),
min_cost_flow.Flow(i),
min_cost_flow.Capacity(i),
cost))
else:
print('There was an issue with the min cost flow input.')
if __name__ == '__main__':
main()