Creating a relaxed version of my model
回答済みHello everyone,
I'm attempting to solve a 2D knapsack problem where each item has both height and width, and my goal is to pack as many items as possible(given the height and width of the knapsack) without any overlap. I would like to relax the variable that indicates which items are packed and which ones are not so that I can obtain a fractional solution that can be passed as an input to a heuristic. However, when I try to relax the model using
for i in range(nr):
u[i].setAttr('vtype', 'C')
nothing changes, what could be the reason behind that?
here is my Python code:
from io import StringIO
import pandas as pd
import numpy as np
from gurobipy import GRB
import gurobipy as gp
#---------------------------------------------------
# data
#---------------------------------------------------
data = '''
item width height color
k1 1 1 blue
k2 2 1 orange
k3 1 2 green
k4 1 3 red
k5 3 2 purple
'''
df = pd.read_table(StringIO(data),sep='\s+')
print("Input data")
display(df)
# Define the knapsack dimensions
H = 4
W = 5
print(f"Container width:{W} height:{H}")
#---------------------------------------------------
# derived data
# expand to individual items to
#implement rotation
#---------------------------------------------------
colors=df['color']
w = df['width'].to_numpy()
h = df['height'].to_numpy()
indx = np.arange(np.size(w))
n = len(w)
print(f"Number of individual original items: {n}")
#---------------------------------------------------
# create rotated items
# by duplicating
#---------------------------------------------------
wr = np.concatenate((w,h))
hr = np.concatenate((h,w))
indxr = np.concatenate((indx,indx))
nr = 2*n
print(f"Number of individual items (after adding rotations): {nr}")
#%%
# Create the Gurobi model
m = gp.Model('2D_Knapsack')
# variables
# u[i] : item i is used
u = m.addVars(nr, vtype=gp.GRB.BINARY, name="u")
# x[i],y[i] : location of item i
x = m.addVars(nr,lb=0,ub=W, vtype=GRB.INTEGER, name="x")
y = m.addVars(nr,lb=0,ub=H, vtype=GRB.INTEGER, name="y")
# xw[i],yh[i] : width/height item i based on the orientaton i choose
xw = m.addVars(nr,lb=0,ub=max(wr), vtype=GRB.INTEGER, name="xw")
yh = m.addVars(nr,lb=0,ub=max(hr), vtype=GRB.INTEGER, name="yh")
# Define the binary variables to indicate whether two items overlap
#overlap = m.addVars(nr, nr, vtype=gp.GRB.BINARY, name="overlap")
l = m.addVars(nr, nr, vtype=GRB.BINARY, name="l") # lij = 1 if i is left of j, 0 otherwise
b = m.addVars(nr, nr, vtype=GRB.BINARY, name="b") # bij = 1 if i is below j, 0 otherwise
m.update
#%%
m.setObjective(gp.quicksum(u[i] for i in range(nr)), gp.GRB.MAXIMIZE)
#%%
# constraints
for i in range(nr):
m.addConstr(xw[i]==wr[i]*u[i])
m.addConstr(yh[i]==hr[i]*u[i])
# only one of non-rotated/rotated pair can be used
for i in range(n):
m.addConstr(u[i]+u[i+n]<=1)
#%% overlap constraint
# #Add constraints to ensure that two items do not overlap
for i in range(nr):
for j in range(nr):
if i != j:
# If item i and item j overlap, then the overlap[i,j] binary variable must be equal to 1
m.addConstr(x[i] + xw[i] <=W)
m.addConstr(y[i] + yh[i] <=H)
m.addConstr(x[i] - x[j] + W*l[i,j] <= W- xw[i])
m.addConstr(y[i] - y[j] + H*b[i,j] <= H- yh[i])
m.addConstr(l[i,j] + l[j,i] + b[i,j] + b[j,i] >= 1)
#%%
# extra: this constraint helps performance enormously
m.addConstr(sum([wr[i]*hr[i]*u[i] for i in range(nr)])<=W*H)
#%%
#Relaxation
for i in range(nr):
u[i].setAttr('vtype', 'C')
m.update()
m.optimize()
print([u[i].X for i in range(nr)])
#%%
a=[]
used=[]
for i in range(nr):
a.append(u[i].X)
for i in range(nr):
if a[i]==1:
used.append(i)
#%%
import matplotlib.pyplot as plt
# positions and dimensions
x_values = [x[i].X for i in used]
y_values = [y[i].X for i in used]
w_values = [wr[i] for i in used]
h_values = [hr[i] for i in used]
# plot
fig = plt.figure()
ax = fig.add_subplot(111)
for i in range(len(x_values)):
ax.add_patch(plt.Rectangle((x_values[i], y_values[i]), w_values[i], h_values[i], edgecolor='black', facecolor=colors[i]))
plt.xlim([0, W])
plt.ylim([0, H])
plt.gca().set_aspect('equal', adjustable='box')
plt.show()
-
Hi Miriana,
Your code:
for i in range(nr): u[i].setAttr('vtype', 'C')
is doing what is it supposed to do.
You can see this by running
for i in range(nr):
print(u[i].vType)after calling m.update().
At the optimal solution the values of u are 0 or 1 - regardless of whether u is declared binary or not. This can be seen by setting the u variables to be continuous right from the start and solving:
u = m.addVars(nr, vtype=gp.GRB.CONTINUOUS, name="u")
Will u variables take binary values in every feasible solution? Perhaps. Some MILP models produce polyhedra which are naturally integral and the solution to the LP is the solution to the MILP. Although your model does not produce a polyhedron that is integral in general, it may be integral when projected onto the u variables (i.e. with respect to the u variables).
- Riley
0
サインインしてコメントを残してください。
コメント
1件のコメント