Assignament Optimization Problem - a performance evaluation in problem size (Part. I. ILP)

Allocation problem: find the best HW-resource/node to allocate a service

$$ s_i \in Services \\ n_i \in Resources \\ Min. Coste(n_i,s_i) * Allocation(n_i,s_i) $$

import pulp
import time

# https://coin-or.github.io/pulp/guides/how_to_configure_solvers.html
print(pulp.listSolvers())

['GLPK_CMD', 'PYGLPK', 'CPLEX_CMD', 'CPLEX_PY', 'GUROBI', 'GUROBI_CMD', 'MOSEK', 'XPRESS', 'PULP_CBC_CMD', 'COIN_CMD', 'COINMP_DLL', 'CHOCO_CMD', 'MIPCL_CMD', 'SCIP_CMD']

One criterion: Cost optimization

nodes = list("ABC")
services = list("XYZHJ")
cunist = [10,30,5,90,40]
cost = {p:cunist[e] for e,p in enumerate(services)}

cost

{'X': 10, 'Y': 30, 'Z': 5, 'H': 90, 'J': 40}

allocs = pulp.LpVariable.dicts("allocation",[(node, service) for node in nodes for service in services], cat=pulp.LpBinary)  

prob = pulp.LpProblem("ilp", pulp.LpMinimize)
prob

ilp:
MINIMIZE
None
VARIABLES

#Default contraints: all allocations have a cost
prob += pulp.lpSum(cost[service] * sum(allocs[(node, service)] for node in nodes) for service in services)

for service in services:
    print(list(allocs[(node, service)] for node in nodes))

[allocation_('A',_'X'), allocation_('B',_'X'), allocation_('C',_'X')]
[allocation_('A',_'Y'), allocation_('B',_'Y'), allocation_('C',_'Y')]
[allocation_('A',_'Z'), allocation_('B',_'Z'), allocation_('C',_'Z')]
[allocation_('A',_'H'), allocation_('B',_'H'), allocation_('C',_'H')]
[allocation_('A',_'J'), allocation_('B',_'J'), allocation_('C',_'J')]

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

print(cost)
for node in nodes:
    print(sum(allocs[(node, service)]*cost[service] for service in services))

{'X': 10, 'Y': 30, 'Z': 5, 'H': 90, 'J': 40}
90*allocation_('A',_'H') + 40*allocation_('A',_'J') + 10*allocation_('A',_'X') + 30*allocation_('A',_'Y') + 5*allocation_('A',_'Z')
90*allocation_('B',_'H') + 40*allocation_('B',_'J') + 10*allocation_('B',_'X') + 30*allocation_('B',_'Y') + 5*allocation_('B',_'Z')
90*allocation_('C',_'H') + 40*allocation_('C',_'J') + 10*allocation_('C',_'X') + 30*allocation_('C',_'Y') + 5*allocation_('C',_'Z')

#More constraints
for e,node in enumerate(nodes):
    prob += pulp.lpSum(sum(allocs[(node, service)]*cost[service] for service in services)) <= 100.0, "CosteAsumible_%s"%(nodes[e])

prob

ilp:
MINIMIZE
90*allocation_('A',_'H') + 40*allocation_('A',_'J') + 10*allocation_('A',_'X') + 30*allocation_('A',_'Y') + 5*allocation_('A',_'Z') + 90*allocation_('B',_'H') + 40*allocation_('B',_'J') + 10*allocation_('B',_'X') + 30*allocation_('B',_'Y') + 5*allocation_('B',_'Z') + 90*allocation_('C',_'H') + 40*allocation_('C',_'J') + 10*allocation_('C',_'X') + 30*allocation_('C',_'Y') + 5*allocation_('C',_'Z') + 0
SUBJECT TO
_C1: allocation_('A',_'X') + allocation_('B',_'X') + allocation_('C',_'X') = 1

_C2: allocation_('A',_'Y') + allocation_('B',_'Y') + allocation_('C',_'Y') = 1

_C3: allocation_('A',_'Z') + allocation_('B',_'Z') + allocation_('C',_'Z') = 1

_C4: allocation_('A',_'H') + allocation_('B',_'H') + allocation_('C',_'H') = 1

_C5: allocation_('A',_'J') + allocation_('B',_'J') + allocation_('C',_'J') = 1

CosteAsumible_A: 90 allocation_('A',_'H') + 40 allocation_('A',_'J')
 + 10 allocation_('A',_'X') + 30 allocation_('A',_'Y')
 + 5 allocation_('A',_'Z') <= 100

CosteAsumible_B: 90 allocation_('B',_'H') + 40 allocation_('B',_'J')
 + 10 allocation_('B',_'X') + 30 allocation_('B',_'Y')
 + 5 allocation_('B',_'Z') <= 100

CosteAsumible_C: 90 allocation_('C',_'H') + 40 allocation_('C',_'J')
 + 10 allocation_('C',_'X') + 30 allocation_('C',_'Y')
 + 5 allocation_('C',_'Z') <= 100

VARIABLES
0 <= allocation_('A',_'H') <= 1 Integer
0 <= allocation_('A',_'J') <= 1 Integer
0 <= allocation_('A',_'X') <= 1 Integer
0 <= allocation_('A',_'Y') <= 1 Integer
0 <= allocation_('A',_'Z') <= 1 Integer
0 <= allocation_('B',_'H') <= 1 Integer
0 <= allocation_('B',_'J') <= 1 Integer
0 <= allocation_('B',_'X') <= 1 Integer
0 <= allocation_('B',_'Y') <= 1 Integer
0 <= allocation_('B',_'Z') <= 1 Integer
0 <= allocation_('C',_'H') <= 1 Integer
0 <= allocation_('C',_'J') <= 1 Integer
0 <= allocation_('C',_'X') <= 1 Integer
0 <= allocation_('C',_'Y') <= 1 Integer
0 <= allocation_('C',_'Z') <= 1 Integer

start = time.perf_counter()
prob.solve(pulp.PULP_CBC_CMD(msg=0))
total = time.perf_counter() - start
print(total)

0.02838451900004202

print(cost)
for v in prob.variables():
    print(v.name, "=", v.varValue)

{'X': 10, 'Y': 30, 'Z': 5, 'H': 90, 'J': 40}
allocation_('A',_'H') = 0.0
allocation_('A',_'J') = 1.0
allocation_('A',_'X') = 1.0
allocation_('A',_'Y') = 1.0
allocation_('A',_'Z') = 1.0
allocation_('B',_'H') = 1.0
allocation_('B',_'J') = 0.0
allocation_('B',_'X') = 0.0
allocation_('B',_'Y') = 0.0
allocation_('B',_'Z') = 0.0
allocation_('C',_'H') = 0.0
allocation_('C',_'J') = 0.0
allocation_('C',_'X') = 0.0
allocation_('C',_'Y') = 0.0
allocation_('C',_'Z') = 0.0

#In the LpVariables the varValue is updated
allocs["A","H"].varValue

0.0

for node in nodes:
    print("Cost in node %s: %f"%(node,sum(allocs[node,service].varValue*cost[service] for service in services)))

Cost in node A: 85.000000
Cost in node B: 90.000000
Cost in node C: 0.000000

Two criteria:

Cost and Latency optimization

nodes = list("ABC")
services = list("XYZHJ")
cunist = [10,30,5,90,40]
latencies = [20,10,10]
service_sla = [10,30,15,10,20]
cost = {p:cunist[e] for e,p in enumerate(services)}
service_lat = {p:service_sla[e] for e,p in enumerate(services)}
node_lat = {p:latencies[e] for e,p in enumerate(nodes)}

print(cost)
print(service_lat)
print(node_lat)

{'X': 10, 'Y': 30, 'Z': 5, 'H': 90, 'J': 40}
{'X': 10, 'Y': 30, 'Z': 15, 'H': 10, 'J': 20}
{'A': 20, 'B': 10, 'C': 10}

allocs = pulp.LpVariable.dicts("allocation",[(node, service) for node in nodes for service in services], cat=pulp.LpBinary) 
prob = pulp.LpProblem("ilp", pulp.LpMinimize)

#Default contraints: all allocations have a cost
prob += pulp.lpSum(cost[service] * sum(allocs[(node, service)] for node in nodes) for service in services)

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

#More constraints
for e,node in enumerate(nodes):
    prob += pulp.lpSum(sum(allocs[(node, service)]*cost[service] for service in services)) <= 100.0, "CosteAsumible_%s"%(nodes[e])

for node in nodes:
    for service in services:
        prob += pulp.lpSum(allocs[(node, service)]*node_lat[node]) <= service_lat[service], "Constr_Lat_S%s_N%s"%(service,node) 

prob

ilp:
MINIMIZE
90*allocation_('A',_'H') + 40*allocation_('A',_'J') + 10*allocation_('A',_'X') + 30*allocation_('A',_'Y') + 5*allocation_('A',_'Z') + 90*allocation_('B',_'H') + 40*allocation_('B',_'J') + 10*allocation_('B',_'X') + 30*allocation_('B',_'Y') + 5*allocation_('B',_'Z') + 90*allocation_('C',_'H') + 40*allocation_('C',_'J') + 10*allocation_('C',_'X') + 30*allocation_('C',_'Y') + 5*allocation_('C',_'Z') + 0
SUBJECT TO
_C1: allocation_('A',_'X') + allocation_('B',_'X') + allocation_('C',_'X') = 1

_C2: allocation_('A',_'Y') + allocation_('B',_'Y') + allocation_('C',_'Y') = 1

_C3: allocation_('A',_'Z') + allocation_('B',_'Z') + allocation_('C',_'Z') = 1

_C4: allocation_('A',_'H') + allocation_('B',_'H') + allocation_('C',_'H') = 1

_C5: allocation_('A',_'J') + allocation_('B',_'J') + allocation_('C',_'J') = 1

CosteAsumible_A: 90 allocation_('A',_'H') + 40 allocation_('A',_'J')
 + 10 allocation_('A',_'X') + 30 allocation_('A',_'Y')
 + 5 allocation_('A',_'Z') <= 100

CosteAsumible_B: 90 allocation_('B',_'H') + 40 allocation_('B',_'J')
 + 10 allocation_('B',_'X') + 30 allocation_('B',_'Y')
 + 5 allocation_('B',_'Z') <= 100

CosteAsumible_C: 90 allocation_('C',_'H') + 40 allocation_('C',_'J')
 + 10 allocation_('C',_'X') + 30 allocation_('C',_'Y')
 + 5 allocation_('C',_'Z') <= 100

Constr_Lat_SX_NA: 20 allocation_('A',_'X') <= 10

Constr_Lat_SY_NA: 20 allocation_('A',_'Y') <= 30

Constr_Lat_SZ_NA: 20 allocation_('A',_'Z') <= 15

Constr_Lat_SH_NA: 20 allocation_('A',_'H') <= 10

Constr_Lat_SJ_NA: 20 allocation_('A',_'J') <= 20

Constr_Lat_SX_NB: 10 allocation_('B',_'X') <= 10

Constr_Lat_SY_NB: 10 allocation_('B',_'Y') <= 30

Constr_Lat_SZ_NB: 10 allocation_('B',_'Z') <= 15

Constr_Lat_SH_NB: 10 allocation_('B',_'H') <= 10

Constr_Lat_SJ_NB: 10 allocation_('B',_'J') <= 20

Constr_Lat_SX_NC: 10 allocation_('C',_'X') <= 10

Constr_Lat_SY_NC: 10 allocation_('C',_'Y') <= 30

Constr_Lat_SZ_NC: 10 allocation_('C',_'Z') <= 15

Constr_Lat_SH_NC: 10 allocation_('C',_'H') <= 10

Constr_Lat_SJ_NC: 10 allocation_('C',_'J') <= 20

VARIABLES
0 <= allocation_('A',_'H') <= 1 Integer
0 <= allocation_('A',_'J') <= 1 Integer
0 <= allocation_('A',_'X') <= 1 Integer
0 <= allocation_('A',_'Y') <= 1 Integer
0 <= allocation_('A',_'Z') <= 1 Integer
0 <= allocation_('B',_'H') <= 1 Integer
0 <= allocation_('B',_'J') <= 1 Integer
0 <= allocation_('B',_'X') <= 1 Integer
0 <= allocation_('B',_'Y') <= 1 Integer
0 <= allocation_('B',_'Z') <= 1 Integer
0 <= allocation_('C',_'H') <= 1 Integer
0 <= allocation_('C',_'J') <= 1 Integer
0 <= allocation_('C',_'X') <= 1 Integer
0 <= allocation_('C',_'Y') <= 1 Integer
0 <= allocation_('C',_'Z') <= 1 Integer

start = time.perf_counter()
status = prob.solve(pulp.PULP_CBC_CMD(msg=0,timeLimit=10))
total = time.perf_counter() - start
if status == pulp.LpStatusOptimal:
    print("nice")
else:
    print("NO")
print(total) #seconds

nice
0.017707104000010077

print(cost)
for v in prob.variables():
    print(v.name, "=", v.varValue)

{'X': 10, 'Y': 30, 'Z': 5, 'H': 90, 'J': 40}
allocation_('A',_'H') = 0.0
allocation_('A',_'J') = 1.0
allocation_('A',_'X') = 0.0
allocation_('A',_'Y') = 1.0
allocation_('A',_'Z') = 0.0
allocation_('B',_'H') = 1.0
allocation_('B',_'J') = 0.0
allocation_('B',_'X') = 0.0
allocation_('B',_'Y') = 0.0
allocation_('B',_'Z') = 1.0
allocation_('C',_'H') = 0.0
allocation_('C',_'J') = 0.0
allocation_('C',_'X') = 1.0
allocation_('C',_'Y') = 0.0
allocation_('C',_'Z') = 0.0

#COSTS
for node in nodes:
    print("Cost in node %s: %f"%(node,sum(allocs[node,service].varValue*cost[service] for service in services)))

Cost in node A: 70.000000
Cost in node B: 95.000000
Cost in node C: 10.000000

#Latencies
for service in services:
    for node in nodes:
        if allocs[node,service].varValue == 1.0:
            print("Service %s at node %s :- %i>=%i"
                 %(service,node,service_lat[service],node_lat[node]))

Service X at node C :- 10>=10
Service Y at node A :- 30>=20
Service Z at node B :- 15>=10
Service H at node B :- 10>=10
Service J at node A :- 20>=20

other solvers

sudo apt-get install python-glpk
sudo apt-get install glpk-utils
`

prob.solve(pulp.GLPK(msg=0))
`

Analysing the scalability

%matplotlib inline
import string
import random
import pulp
import time
import matplotlib.pyplot as plt
random.seed(2022)

nodes = list(string.ascii_uppercase)
services = list(string.ascii_uppercase)
cost_units_service = [random.randint(5,100) for _ in range(len(services))]
latencies = [random.randint(10,30) for _ in range(len(nodes))]
service_sla = [random.randint(5,30) for _ in range(len(services))]

cost = {p:cost_units_service[e] for e,p in enumerate(services)}
service_lat = {p:service_sla[e] for e,p in enumerate(services)}
node_lat = {p:latencies[e] for e,p in enumerate(nodes)}

def solver_alloc(nodes,services,cost,service_lat,node_lat,timeLimit=10):
    allocs = pulp.LpVariable.dicts("allocation",[(node, service) for node in nodes for service in services], cat=pulp.LpBinary) 
    prob = pulp.LpProblem("ilp", pulp.LpMinimize)
    prob += pulp.lpSum(cost[service] * sum(allocs[(node, service)] for node in nodes) for service in services)
    #all products have to be allocated
    for service in services:
        prob+= pulp.lpSum(allocs[(node, service)] for node in nodes) == 1
        
    #More constraints
    for e,node in enumerate(nodes):
        prob += pulp.lpSum(sum(allocs[(node, service)]*cost[service] for service in services)) <= 100.0, "CosteAsumible_%s"%(nodes[e])    

    for node in nodes:
        for service in services:
            prob += pulp.lpSum(allocs[(node, service)]*node_lat[node]) <= service_lat[service], "Constr_Lat_S%s_N%s"%(service,node) 
    
    start = time.perf_counter()
    status = prob.solve(pulp.PULP_CBC_CMD(msg=0,timeLimit=timeLimit))
    return status, time.perf_counter()-start

    

solver_alloc(nodes,services,cost,service_lat,node_lat,timeLimit=10)

#scaling, step=10
node_test, time_test = [], []

for n in range(1,50,5):
    print("Step: ",n)
    nodes = ["N"+w+str(i) for w in list(string.ascii_uppercase) for i in range(n)]
#    services = ["S"+w+str(i) for w in list(string.ascii_uppercase) for i in range(n)]
#    services = ["SA0"]
    services = ["S"+w for w in list(string.ascii_uppercase)]
    print("total nodes:",len(nodes))
    node_test.append(len(nodes))
    
    cost_units_service = [random.randint(5,100) for _ in range(len(services))]
    latencies = [random.randint(10,30) for _ in range(len(nodes))]
    service_sla = [random.randint(5,30) for _ in range(len(services))]

    cost = {p:cost_units_service[e] for e,p in enumerate(services)}
    service_lat = {p:service_sla[e] for e,p in enumerate(services)}
    node_lat = {p:latencies[e] for e,p in enumerate(nodes)}

    found, response = solver_alloc(nodes,services,cost,service_lat,node_lat,timeLimit=100)
    print(bool(found), response)
    time_test.append(response)

fig = plt.figure()
ax = plt.axes()

ax.plot(node_test, time_test)

%matplotlib inline
import string
import random
import pulp
import time
import matplotlib.pyplot as plt
random.seed(2022)

nodes = list(string.ascii_uppercase)
services = list(string.ascii_uppercase)
cost_units_service = [random.randint(5,100) for _ in range(len(services))]
latencies = [random.randint(10,30) for _ in range(len(nodes))]
service_sla = [random.randint(5,30) for _ in range(len(services))]

cost = {p:cost_units_service[e] for e,p in enumerate(services)}
service_lat = {p:service_sla[e] for e,p in enumerate(services)}
node_lat = {p:latencies[e] for e,p in enumerate(nodes)}

def solver_alloc(nodes,services,cost,service_lat,node_lat,timeLimit=10):
    allocs = pulp.LpVariable.dicts("allocation",[(node, service) for node in nodes for service in services], cat=pulp.LpBinary) 
    prob = pulp.LpProblem("ilp", pulp.LpMinimize)
    prob += pulp.lpSum(cost[service] * sum(allocs[(node, service)] for node in nodes) for service in services)
    #all products have to be allocated
    for service in services:
        prob+= pulp.lpSum(allocs[(node, service)] for node in nodes) == 1
        
    #More constraints
    for e,node in enumerate(nodes):
        prob += pulp.lpSum(sum(allocs[(node, service)]*cost[service] for service in services)) <= 100.0, "CosteAsumible_%s"%(nodes[e])    

    for node in nodes:
        for service in services:
            prob += pulp.lpSum(allocs[(node, service)]*node_lat[node]) <= service_lat[service], "Constr_Lat_S%s_N%s"%(service,node) 
    
    start = time.perf_counter()
    status = prob.solve(pulp.PULP_CBC_CMD(msg=0,timeLimit=timeLimit))
    return status, time.perf_counter()-start

    

solver_alloc(nodes,services,cost,service_lat,node_lat,timeLimit=10)

(-1, 0.03782144199999493)

#scaling, step=10
node_test, time_test = [], []

for n in range(1,50,5):
    print("Step: ",n)
    nodes = ["N"+w+str(i) for w in list(string.ascii_uppercase) for i in range(n)]
#    services = ["S"+w+str(i) for w in list(string.ascii_uppercase) for i in range(n)]
#    services = ["SA0"]
    services = ["S"+w for w in list(string.ascii_uppercase)]
    print("total nodes:",len(nodes))
    node_test.append(len(nodes))
    
    cost_units_service = [random.randint(5,100) for _ in range(len(services))]
    latencies = [random.randint(10,30) for _ in range(len(nodes))]
    service_sla = [random.randint(5,30) for _ in range(len(services))]

    cost = {p:cost_units_service[e] for e,p in enumerate(services)}
    service_lat = {p:service_sla[e] for e,p in enumerate(services)}
    node_lat = {p:latencies[e] for e,p in enumerate(nodes)}

    found, response = solver_alloc(nodes,services,cost,service_lat,node_lat,timeLimit=100)
    print(bool(found), response)
    time_test.append(response)

Step:  1
total nodes: 26
True 0.03500134399973831
Step:  6
total nodes: 156
True 0.23172726700022395
Step:  11
total nodes: 286
True 0.34116768600006253
Step:  16
total nodes: 416
True 0.517777622000267
Step:  21
total nodes: 546
True 1.1037343630000578
Step:  26
total nodes: 676
True 1.3212750520001464
Step:  31
total nodes: 806
True 1.8405263620002188
Step:  36
total nodes: 936
True 1.2379455400000552
Step:  41
total nodes: 1066
True 3.4067374080000263
Step:  46
total nodes: 1196
True 3.588439693000055

fig = plt.figure()
ax = plt.axes()

ax.plot(node_test, time_test)

[<matplotlib.lines.Line2D at 0x111942b20>]