Combinatorial optimization-typical problem-minimum cost flow problem

Typical problem and execution method

Minimum cost flow problem

In the directed graph $ G = (V, E) $, given the capacity and weight of each side and the demand for nodes, the sum of the weights for the flow rate of each side is minimized without exceeding the capacity of each side. Find the flow.

--At each node, "inflow --outflow" is equal to demand. --If the demand is negative, it represents the supply. --The sum of the demands of all nodes must be 0.

Execution method

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 data
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)

result


(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


#Random number data
import networkx as nx
g = nx.fast_gnp_random_graph(8, 0.2, 1, True)
g.nodes[1]['demand'] = -2 #Supply
g.nodes[7]['demand'] = 2 #demand
g.adj[2][7]['capacity'] = 1 #capacity
result = nx.min_cost_flow(g)
for i, d in result.items():
    for j, f in d.items():
        if f: print((i, j), f)

result


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

data

Recommended Posts

Combinatorial optimization-typical problem-minimum cost flow problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-Typical problem-Minimum spanning tree problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-Typical problem-Maximum stable set problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Combinatorial optimization-Typical problem-Facility placement problem with no capacity constraints
Combinatorial optimization-minimum cut problem