point(node)And road candidates(Edge)In a graph consisting of
Consider setting up a road on the edge.
I want to be able to move between several nodes.
The set of sets of nodes you want to move is called demand.
Convenience is the total distance traveled to meet demand.
Optimize installation costs and convenience.
Combinatorial optimization (http://qiita.com/SaitoTsutomu/items/bfbf4c185ed7004b5721) can also be used to solve such problems.
For installation costs only, the Minimum Spanning Tree in the Typical Problem 85% A8% E5% 9F% 9F% E6% 9C% A8) Problem or [Steiner Tree](https://en.wikipedia.org/wiki/%E3%82%B7%E3%83%A5%E3% 82% BF% E3% 82% A4% E3% 83% 8A% E3% 83% BC% E6% 9C% A8) This is a problem. For convenience alone, it is a multi-product minimum cost flow problem, which is a variant of the typical problem minimum cost flow problem.
Lowering the installation cost will reduce the convenience, and increasing the convenience will reduce the installation cost. An optimization problem with multiple evaluation scales in this way is called a multipurpose optimization problem.
Here, let's find a trade-off between installation cost and convenience. To do this, we will solve mathematical problems based on the high-mix minimum-cost flow problem many times, while capping the installation cost.
$ \ mbox {objective} $ td> | $ \ sum_i {\ sum_j {\ sum_k {x_ {ijk}}}} $ td> | Convenience td > tr> |
$ \ mbox {variables} $ td> | $ x_ {ijk} \ ge 0 ~ \ forall i, j, k $ td> | Demand Flow rate from node j to node j with respect to i td> tr> |
$ y_ {jk} \ in \ {0, 1 \} ~ \ forall j, k $ td> | Whether to install a road between node j and node k td > tr> | |
$ \ mbox {subject to} $ td> | $ \ sum_ {j, k} {y_ {jk}} \ le Upper limit $ td> | Maximum installation cost td> tr> |
$ x_ {ijk} \ le y_ {jk} ~ \ forall i, j, k $ td> | x constraints td> tr> | |
$ \ sum_k {x_ {ijk}} = \ sum_k {x_ {ikj}} + Demand ~ \ forall i, j $ td> | Flow storage td> tr> |
Prepare what you need.
python
import random, numpy as np, pandas as pd, networkx as nx, matplotlib.pyplot as plt
from itertools import chain, combinations
from pulp import *
def draw(g):
"""drawing"""
nx.draw_networkx_labels(g, pos=pos)
nx.draw_networkx_nodes(g, node_color='w', pos=pos)
nx.draw_networkx_edges(g, pos=pos)
plt.show()
def addvar(cnt=[0], *args, **kwargs):
"""Variable creation"""
cnt[0] += 1
return LpVariable('v%d'%cnt[0], lowBound=0, *args, **kwargs)
Let's create a problem at random. Demand was set only between some nodes.
python
n = 16 #Number of nodes
g = nx.random_graphs.fast_gnp_random_graph(n, 0.26, 8) #Graph
rn = g.nodes() #Node list
pos = nx.spring_layout(g, pos={i:(i/4, i%4) for i in rn}) #Node position
for i, j in g.edges():
v = pos[i] - pos[j]
g[i][j]['dist'] = np.sqrt(v.dot(v)) #distance
dems = random.sample(list(combinations(rn, 2)), 10) #demand
draw(g)
I will try to find the minimum spanning tree.
python
h = nx.minimum_spanning_tree(g, 'dist')
draw(h)
I will try to solve it.
python
rved = [(j, i) for i, j in g.edges()] #Reverse side
#Flow rate per demand
a = pd.DataFrame([(df, dt, ef, et, g.edge[ef][et]['dist'], addvar())
for df, dt in dems for ef, et in chain(g.edges(), rved)],
columns=['DeFr', 'DeTo', 'EdFr', 'EdTo', 'Dist', 'Var'])
#Whether to install the side
b = pd.DataFrame([(fr, to, g.edge[fr][to]['dist'], addvar(cat=LpBinary))
for fr, to in g.edges()], columns=['Fr', 'To', 'Dist', 'Var'])
res = [] #Solution(setup cost,Convenience,Graph)
mxcst = 999 #Installation cost upper limit
while True:
m = LpProblem() #Mathematical model
m += lpDot(a.Dist, a.Var) + lpDot(b.Dist, b.Var)*1e-6 #Objective function(Convenience)
m += lpDot(b.Dist, b.Var) <= mxcst #Installation cost upper limit
for _, r in a.iterrows():
i, j = r.EdFr, r.EdTo
if i > j: i, j = j, i
#Install when flowing the flow rate
m += r.Var <= lpSum(b.query('Fr==%s & To==%s'%(i,j)).Var)
for (df, dt), c in a.groupby(('DeFr', 'DeTo')):
for nd in rn:
z = 1 if nd == df else -1 if nd == dt else 0
#Flow rate storage
m += lpSum(c.query('EdFr == %s'%nd).Var) == \
lpSum(c.query('EdTo == %s'%nd).Var) + z
m.solve() #Solution
if m.status != 1: break
a['Val'] = a.Var.apply(lambda v: value(v)) #result(Flow rate)
b['Val'] = b.Var.apply(lambda v: value(v)) #result(Whether to install)
cst = value(lpDot(b.Dist, b.Var)) #setup cost
val = value(m.objective) #Convenience
mxcst = cst - 1e-3 #Next installation cost upper limit
h = nx.Graph()
h.add_edges_from([(r.Fr, r.To) for _, r in b[b.Val == 1].iterrows()])
res.append((cst, val, h))
Let's see the result. The higher the installation cost, the better the convenience.
python
plt.rcParams['font.family'] = 'IPAexGothic'
plt.plot([r[0] for r in res], [r[1] for r in res])
plt.xlabel('setup cost')
plt.ylabel('Convenience')
It is a graph when the convenience is the best.
python
draw(res[0][2])
I tried to make a GIF animation of the transition of installation cost.
that's all
Recommended Posts