In [7]:
import pulp
import time
import numpy
import string
import networkx as nx
In [2]:
tree = nx.random_tree(n=10, seed=0)
print(nx.forest_str(tree, sources=[0]))

╙── 0
    ├── 3
    └── 4
        ├── 6
        │   ├── 1
        │   ├── 2
        │   └── 7
        │       └── 8
        │           └── 5
        └── 9
In [3]:
users = [3,2,2,2,5,9]
level = [nx.shortest_path_length(tree,source=0,target=n) for n in tree.nodes()]
isLeaf = [(n==1) for (_,n) in tree.degree()]
cost = []
for n in tree.nodes():
    c = level[n]*2+10
    if isLeaf[n]:
        c = c*1.2
    cost.append(c) 

print(level)
print(isLeaf)
print(cost)

[0, 3, 3, 1, 1, 5, 2, 3, 4, 2]
[False, True, True, True, False, True, False, False, False, True]
[10, 19.2, 19.2, 14.399999999999999, 12, 24.0, 14, 16, 18, 16.8]
In [4]:
lat = {}
for (s,t) in tree.edges():
    lat[(s,t)]=level[t]*10
print(lat)

{(0, 3): 10, (0, 4): 10, (1, 6): 20, (2, 6): 20, (4, 6): 20, (4, 9): 20, (5, 8): 40, (6, 7): 30, (7, 8): 40}
In [5]:
nx.set_edge_attributes(tree,values=lat,name="Lat")

alllat = dict()
for n in tree.nodes():
    for m in tree.nodes():
        alllat[(n,m)]=nx.shortest_path_length(tree,source=n,target=m,weight="Lat")

print(alllat)    

{(0, 0): 0, (0, 1): 50, (0, 2): 50, (0, 3): 10, (0, 4): 10, (0, 5): 140, (0, 6): 30, (0, 7): 60, (0, 8): 100, (0, 9): 30, (1, 0): 50, (1, 1): 0, (1, 2): 40, (1, 3): 60, (1, 4): 40, (1, 5): 130, (1, 6): 20, (1, 7): 50, (1, 8): 90, (1, 9): 60, (2, 0): 50, (2, 1): 40, (2, 2): 0, (2, 3): 60, (2, 4): 40, (2, 5): 130, (2, 6): 20, (2, 7): 50, (2, 8): 90, (2, 9): 60, (3, 0): 10, (3, 1): 60, (3, 2): 60, (3, 3): 0, (3, 4): 20, (3, 5): 150, (3, 6): 40, (3, 7): 70, (3, 8): 110, (3, 9): 40, (4, 0): 10, (4, 1): 40, (4, 2): 40, (4, 3): 20, (4, 4): 0, (4, 5): 130, (4, 6): 20, (4, 7): 50, (4, 8): 90, (4, 9): 20, (5, 0): 140, (5, 1): 130, (5, 2): 130, (5, 3): 150, (5, 4): 130, (5, 5): 0, (5, 6): 110, (5, 7): 80, (5, 8): 40, (5, 9): 150, (6, 0): 30, (6, 1): 20, (6, 2): 20, (6, 3): 40, (6, 4): 20, (6, 5): 110, (6, 6): 0, (6, 7): 30, (6, 8): 70, (6, 9): 40, (7, 0): 60, (7, 1): 50, (7, 2): 50, (7, 3): 70, (7, 4): 50, (7, 5): 80, (7, 6): 30, (7, 7): 0, (7, 8): 40, (7, 9): 70, (8, 0): 100, (8, 1): 90, (8, 2): 90, (8, 3): 110, (8, 4): 90, (8, 5): 40, (8, 6): 70, (8, 7): 40, (8, 8): 0, (8, 9): 110, (9, 0): 30, (9, 1): 60, (9, 2): 60, (9, 3): 40, (9, 4): 20, (9, 5): 150, (9, 6): 40, (9, 7): 70, (9, 8): 110, (9, 9): 0}
In [8]:
nodes = tree.nodes()
services = list(string.ascii_lowercase[0:len(users)])
service_user = {services[i]:users[i] for i in range(len(users))}
print(service_user)
allocs = pulp.LpVariable.dicts("allocation",[(node, service) for node in nodes for service in services], cat=pulp.LpBinary)  

{'a': 3, 'b': 2, 'c': 2, 'd': 2, 'e': 5, 'f': 9}
In [9]:
prob = pulp.LpProblem("ilp", pulp.LpMinimize)
prob += pulp.lpSum((alllat[service_user[service],node] * allocs[(node, service)] for node in nodes) for service in services)

# All services have to be deployed
for service in services:
    prob += pulp.lpSum(allocs[(node, service)] for node in nodes) == 1

# One service in a node    
for node in nodes:
    prob += pulp.lpSum(allocs[(node, service)] for service in services) <= 1
In [10]:
start = time.perf_counter()
prob.solve(pulp.PULP_CBC_CMD(msg=0))
total = time.perf_counter() - start
print(total)

0.026218388000003756
In [11]:
for v in prob.variables():
    if v.varValue == 1:
        print(v.name, "=", v.varValue)

allocation_(2,_'c') = 1.0
allocation_(3,_'a') = 1.0
allocation_(4,_'b') = 1.0
allocation_(5,_'e') = 1.0
allocation_(6,_'d') = 1.0
allocation_(9,_'f') = 1.0
In [12]:
for service in services:
    for node in nodes:
        if allocs[node,service].varValue == 1.0:
            print("Latency of service %s at node %s to user %i :- %i" %(service,node,service_user[service],alllat[service_user[service],node]))

Latency of service a at node 3 to user 3 :- 0
Latency of service b at node 4 to user 2 :- 40
Latency of service c at node 2 to user 2 :- 0
Latency of service d at node 6 to user 2 :- 20
Latency of service e at node 5 to user 5 :- 0
Latency of service f at node 9 to user 9 :- 0
In [ ]: