Optimization Probelm not working

import random
import time
import numpy as np
from itertools import zip_longest
from scipy.stats import pearsonr
import gurobipy as gp
from gurobipy import GRB

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
for i,i1 in enumerate(items):
for j,j1 in enumerate(items):
if correlation_matrix[i][j]>0:
corrind[i, j]=0
else:
corrind[i, j]=1
count=count+1

model = gp.Model("Bin_Packing_Problem")

# Create decision variables
maxBins = 8
binCapacity = 24
maxUtilization = 100
itemCount = len(items)
possible_ItemInBin = [(i, k) for i in range(itemCount) for k in range(maxBins)]

y = model.addVars(range(maxBins), vtype=GRB.BINARY, name="BinUsed")
x = model.addVars(possible_ItemInBin, vtype=GRB.BINARY, name="itemInBin")
z = model.addVars(((j, k, i) for j in range(itemCount) for k in range(itemCount) for i in range(maxBins)), vtype=GRB.BINARY, name="Combination")

# Set objective function
model.setObjective(gp.quicksum(y[i] for i in range(maxBins)), GRB.MINIMIZE)

# constraint 1
for j in items:
item_id = int(j[0])
model.addConstr(gp.quicksum(x[(item_id, i)] for i in range(maxBins)) == 1, "An_item_can_be_in_only_1_bin_" + str(item_id))

# constraint 2

for i in range(maxBins):
model.addConstr(gp.quicksum(items[j][1] * x[(int(items[j][0]), i)] for j in range(itemCount)) <= binCapacity * y[i], "The_sum_of_item_sizes_must_be_smaller_than_the_bin_" + str(i))

# constraint 3

for k in range(maxBins):
for i in range(itemCount - 1):
for j in range(i + 1, itemCount):
if corrind[i][j] == 1:
count = count + 1
constraint_name = f"Constraint_NEG_Correlation_{j}_{k}_{i}"
model.addConstr(z[(i, j, k)] <= 0, constraint_name)

# Optimize the model
model.optimize()

# Print the status and objective value
print("Status:", model.Status)

# Print the solution
bins = {}
for itemBinPair in x.keys():
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 = 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}')

# Print correlation coefficients for each bin using Gurobi
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}")

The optimization constraint 3 is not working and has no effect on the solution, what i wanted to do was to place the tasks in the bin who have negative correlation in the utilization. To do so i defined the corr_ind matrix and i want to place the task in the same bin k whose all possible combinations of corr_ind should be 1

Riley Clement

Gurobi Staff

2023年11月19日 10:39 編集済み

Hi Srinivasan,

If you were to remove "constraint 3" then notice that your z variables don't appear anywhere else in the model - not in any other constraints, not in the objective function. Gurobi will naturally set their values in an optimal solution to zero, which is why constraint 3 makes no difference to the optimal solution reported.

My guess is that you need to include some constraints that link the x and z variables together.

- Riley

Srinivasan Subramaniyan

2023年11月19日 13:10

Hi Riley,

I did make a change;
UB=len(items)
for k in range(UB):
for i in range(UB):
for j in range(UB):
if i != j: # Avoid self-correlation
corr_coefficient, _ = pearsonr(items[i][3], items[j][3])
model.addConstr(corr_coefficient * (x[i, k] - x[j, k]) <= y[k],name=f"constraint_{i}_{j}_{k}")

This only depends on x now; it seems the condition is still not influencing the optimizer.

2023年11月19日 22:35

Yes if I check the optimal solution with the following code:

for k,v in x.items():
    if v.X > 0.5:
        print(k, v)
for k,v in y.items():
    if v.X > 0.5:
        print(k, v)

then it is apparent these constraints are redundant with respect to the optimal solution, i.e. they are satisfied by the optimal solution whether they are included in the model or not.

I'm not sure these are the constraints you want. Is this what you are wanting to model:

"if correlation coefficient of item i and j is negative then they should be in the same bin"?

If this is correct here are a few follow up questions:

* if correlation coefficient of i and j is positive can they be in the same bin or must they be in different bins?
* if i and j are in the same bin do they have to have a negative correlation coefficient or can it be positive?

2023年11月20日 00:13

Hi Riley,

if the correlation coefficient of items i and j is negative then they should be in the same bin"Yes they should be in the same bin if they have -ve correlation.

if correlation coefficient of i and j is positive can they be in the same bin or must they be in different bins?
They must be on different bins

* if i and j are in the same bin do they have to have a negative correlation coefficient or can it be positive?
If they are in the same bin, they should be -ve

2023年11月20日 00:31

It sounds like you are describing a graph coloring problem.

The assignment based ILP model from section 2.2 of this paper:
https://arxiv.org/pdf/1706.10191.pdf
appears to be what you are trying to achieve. Can you take a look and see if you agree?

Optimization Probelm not working

コメント

お探しのものを見つけられませんでしたか？