典型問題と実行方法

最小費用流問題

有向グラフ$G=(V,E)$において、各辺の容量と重みさらに節点の需要量が与えられたとき、各辺の容量を超過せずに各辺の流量に対する重みの総和が最小となるフローを求めよ。

各節点において、「流入量 - 流出量」は、需要量と等しい。
需要量が負の場合、供給量を表す。
全ての節点の需要量の和は0でなければいけない。

実行方法

usage

Signature: nx.min_cost_flow(G, demand='demand', capacity='capacity', weight='weight')
Docstring:
Return a minimum cost flow satisfying all demands in digraph G.

G is a digraph with edge costs and capacities and in which nodes
have demand, i.e., they want to send or receive some amount of
flow. A negative demand means that the node wants to send flow, a
positive demand means that the node want to receive flow. A flow on
the digraph G satisfies all demand if the net flow into each node
is equal to the demand of that node.

python

# CSVデータ
import pandas as pd, networkx as nx
from ortoolpy import graph_from_table, networkx_draw
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe, directed=True)[0]
result = nx.min_cost_flow(g)
for i, d in result.items():
    for j, f in d.items():
        if f: print((i, j), f)

結果

(0, 1) 1
(0, 3) 1
(0, 4) 2
(4, 5) 1

python

# pandas.DataFrame
from ortoolpy.optimization import MinCostFlow
MinCostFlow('data/node0.csv','data/edge0.csv')

	node1	node2	capacity	weight	flow
0	0	1	2	1	1
1	0	3	2	2	1
2	0	4	2	2	2
3	4	5	2	1	1

python

# 乱数データ
import networkx as nx
g = nx.fast_gnp_random_graph(8, 0.2, 1, True)
g.nodes[1]['demand'] = -2 # 供給
g.nodes[7]['demand'] = 2 # 需要
g.adj[2][7]['capacity'] = 1 # 容量
result = nx.min_cost_flow(g)
for i, d in result.items():
    for j, f in d.items():
        if f: print((i, j), f)

結果

(1, 2) 2
(2, 3) 1
(2, 7) 1
(3, 7) 1

データ