I am solving a minimization problem in Python that allocates packet capacities over the edges of a graph in a way that the loss of packets throughout the network/graph is minimum. Packets are generated at nodes following a Poisson Distribution . The problem is scipy.optimize.minimize() cannot accept only integers as inputs to the objective function loss_obj(x). It operates over all float values satisfying the constraint. Method find_loss() finds the loss of edge e assuming k as its capacity. I am pasting only the optimization function below because the original code is over 300 lines.
#here we find loss of an edge e of the graph
def find_loss(e,lmd,q,k):
edge_pmf=find_final_dist(e,lmd,q)
l_e=sum(edge_pmf[k+1:])
return l_e
net_cap=12 #this is the net capacity to be allocated over the edges
#The minimization function
x0=[1]*a
for i in range(a):
x0[i]=net_cap/a
#x=[c1,c2,c3,...]
def loss_obj(x):
s=0
for i in range(len(x)):
l=find_loss(edge_enum[i],lamd,q,m.floor(x[i]))
s+=l
return s
print('Initial guess ',x0)
def constraint(x):
b=sum(x[0:])
return b-net_cap
con={'type':'eq','fun':constraint}
b=(0,net_cap)
bounds=[]
for i in range(a):
bounds.append(b)
cap_op=minimize(loss_obj,x0,method='SLSQP',constraints=con,bounds=bounds)
print('\n',cap_op.x)
This is the output shown:
Initial guess [0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5]
[0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5
0.5 0.5 0.5 0.5 0.5 0.5]
Although I have shown here a vector with only 24 elements just to demonstrate the issue, my network has 104 edges and hence it cannot be solved with scipy.optimize.brute() or itertools.combinations() because the system cannot handle too large arrays and gives a Memory Error. Linear Programming Problem is not what I am aiming at, so PuLP won't be a good solution. Can someone please figure out a way to minimize integer-input functions?
Since the loss function is clear, how about using Bayesian Optimization (BO)? It makes "smart guess" based on the former guesses suggested by the Bayes rule. The following is one popular implementation of BO in Python and its documents are clear.