Optimization Probelm not ADDINF CONSTRAINTS
AnsweredThe correlation constraint is not getting added to the solver, I tried everything possible but it doesnt seem to work!
import random
import gurobipy as gp
from gurobipy import GRB
import numpy as np
from scipy.stats import pearsonr
import sys
random.seed(100)
np.random.seed(100)
def randgenfil(target_average, num_values,zx):
values = []
for _ in range(num_values):
x = random.uniform(0, min(target_average, 100 - target_average))
k = target_average + x if random.randint(0, 1) else target_average - x
if k < 0:
k = 0
elif k > 100:
k = 100
values.append(k)
np.random.shuffle(values)
#if zx%2:
#values.sort()
#else:
#values.sort(reverse=True)
return values, np.mean(values)
tasks=8
items=[]
memory=[7.9,4.7,1.576,2.82,7.9,4.7,1.576,2.82]
runtime=[55,49,34,65,91,28,51,77]
utilization=[79.58,54.9577,69.203,28.79,79.58,54.95,69.2033,28.7931]
for x in range(tasks):
util=[]
util1,a=randgenfil(utilization[x],10,0)
for ii in util1:
util.append(ii)
if(x==0):
#print(x)
util=util+[0.0 for _ in range(tasks*5)]
#print(len(util))
elif(x>=1 and x <tasks-1):
#print(x)
util=[0.0 for _ in range(x*5)] + util
util=util+[0 for _ in range(tasks*5-x*5)]
#print(len(util))
if(x==tasks-1):
#print(x)
util=[0.0 for _ in range((x+1)*5)] + util
#print(len(util))
item = (str(x), memory[x], runtime[x],util)
items.append(item)
itemCount = len(items)
itemsa=items
itemsa = [(a, b, c, [x for x in d if x != 0]) for a, b, c, d in itemsa]
correlation_matrix = np.zeros((itemCount, itemCount))
# Compute the correlation matrix
for i in range(itemCount):
for j in range(itemCount):
correlation_matrix[i, j] = np.corrcoef(items[i][3], items[j][3])[0, 1]
corrind = np.zeros((itemCount, itemCount))
count=0
n = len(items)
UB = n
c = 24
u=100
bound=float(sys.argv[1])
np.set_printoptions(precision=1)
print(correlation_matrix)
for i,i1 in enumerate(items):
for j,j1 in enumerate(items):
if correlation_matrix[i][j]<bound:
corrind[i, j]=1
else:
corrind[i, j]=0
count=count+1
print(corrind)
model = gp.Model ()
x = model.addVars(n, UB, vtype=GRB.BINARY)
y = model.addVars (UB, vtype=GRB.BINARY)
# minimize the number of bins used
model.setObjective(gp.quicksum(y[j] for j in range(UB) ), GRB.MAXIMIZE)
#model.setObjective(gp.quicksum(y[j] for j in range(UB)), GRB.MAXIMIZE)
# pack each item in exactly one bin
model.addConstrs(gp.quicksum(x[i,j] for j in range(UB)) == 1 for i in range(n))
model.addConstrs((
gp.quicksum(np.corrcoef(items[i][3], items[j][3])[0, 1] * x[i, k] * x[j, k] for k in range(UB)) <= bound * (1 - y[j]) if bound < 0 else
gp.quicksum(np.corrcoef(items[i][3], items[j][3])[0, 1] * x[i, k] * x[j, k] for k in range(UB)) <= bound * y[j]
for i in range(n) for j in range(n) if i != j
), name='correlation_constraint')
# bin capacity constraint
model.addConstrs(gp.quicksum(items[i][1] * x[i,j] for i in range(n)) <= c * y[j] for j in range (UB))
# order of bin
model.addConstrs((y[i+1] <= y[i] for i in range(UB-1)), name="order")
#model.setParam('MIPGap', 1e-6)
model.setParam('OutputFlag', 0)
model.setParam('MIPGap', 1e-10) # Adjust the tolerance value as needed
model.setParam('FeasibilityTol', 1e-09) # Adjust the feasibility tolerance
model.optimize()
for c in model.getConstrs():
print(c)
if model.status == GRB.OPTIMAL:
bins = {}
for itemBinPair in x.keys():
# Check if the variable is part of the solution before accessing its value
if x[itemBinPair].X == 1:
itemNum = itemBinPair[0]
binNum = itemBinPair[1]
if binNum in bins:
bins[binNum].append(itemNum)
else:
bins[binNum] = [itemNum]
count = 0
for b in bins.keys():
count += 1
print("Bin " + str(b) + ":")
for item_index in bins[b]:
item = items[int(item_index)]
print("Item " + item[0] + ": Size-" + str(item[1]))
print("\n")
print(bins.keys())
print(f'Total number of GPUs used = {count}')
# Additional processing based on the solution
else:
print(f"Model status: {model.status}. No optimal solution found.")
for b in bins.keys():
bin_items = bins[b]
print(f"Correlation coefficients for bin {b}:")
for i in range(len(bin_items) - 1):
for j in range(i + 1, len(bin_items)):
item_index_i = int(bin_items[i])
item_index_j = int(bin_items[j])
coefficient, _ = pearsonr(items[item_index_i][3], items[item_index_j][3])
print(f"Correlation coefficient between items {item_index_i} and {item_index_j}: {coefficient}")
-
-
Gurobi Staff
Could you please elaborate on what you think is not working?
You can write the LP file of the model that Gurobi solves before calling optimize() with model.write("Test.lp") and then check Test.lp for the correlation constraints.
0 -
-
Hello Marika,
I have incorporated the correlation constraint into my model; however, it does not yield accurate results.
For instance, when the bound is set to -0.25, no tasks should be grouped in any bins as they do not meet the correlation condition. Nevertheless, the solver continues to binpack without considering this condition. This discrepancy was confirmed through the print results employed in the end.
0 -
-
-
I cannot see that a computed solution violates a constraint of the model.
I ran your code with -0.25, the first correlation constraint iscorrelation_constraint[0,1]: - 0.25 y[1] + [
0.37250842430155 x[0,0] * x[1,0] + 0.37250842430155 x[0,1] * x[1,1]
+ 0.37250842430155 x[0,2] * x[1,2] + 0.37250842430155 x[0,3] * x[1,3]
+ 0.37250842430155 x[0,4] * x[1,4] + 0.37250842430155 x[0,5] * x[1,5]
+ 0.37250842430155 x[0,6] * x[1,6] + 0.37250842430155 x[0,7] * x[1,7] ]
<= -0.25In the solution, y[1]=1 and all product terms are 0. Hence the constraint is satisfied.
I also see no violations for the other constraints.You probably need to redefine the constraints such that they map the conditions you have in mind.
0 -
-
Hi Marika,
The constraint i have in mind is
to only binpack tasks if they have a -ve correlation that is np.corrcoef(items[i][3], items[j][3])[0, 1] < bound if they have to be in the same bin k! This constraint does not seem to work sometimes.
#model.addConstrs((gp.quicksum(np.corrcoef(items[i][3], items[j][3])[0, 1] * x[i, k] * x[j, k] for k in range(UB)) <= bound for i in range(n) for j in range(n) if i != j), name='correlation_constraint')0 -
-
-
Hi Srinivasan,
I am not sure whether I understand you correctly. But why not add the constraints similar to the check you are doing at the end:
for i in range(n):
for j in range(i+1,n):
coefficient, _ = pearsonr(items[i][3], items[j][3])
if coefficient > bound:
model.addConstrs(x[i, k] + x[j, k] <= 1 for k in range(UB))It does not allow packing two items in the same bin if the coefficient is above the bound.Cheers,
Marika0 -
Please sign in to leave a comment.
Comments
5 comments