Я пытаюсь решить проблему трехмерной упаковки бинов, которая является NP-сложной (https://en.wikipedia.org/wiki/Bin_packing_problem), с использованием оптимизатора линейного программирования. Я только начал работать с PuLP и столкнулся с некоторыми проблемами. Я подробно добавил свои ограничения, код, вывод и помощь, в которой я нуждаюсь.
ОГРАНИЧЕНИЯ:
Целевая функция введите описание изображения здесь , и я хочу смоделировать следующие ограничения введите описание изображения здесь , где введите описание изображения здесь
КОД ПИТОНА:
from pulp import *
#Variable Decleration
prob = LpProblem('BinPacking', LpMinimize)
ps = [LpVariable("p{0}{1}".format(i + 1, j + 1), cat="Binary")
for i in range(parcel.parcels) for j in range(parcel.containers)]
print(ps)
us = [LpVariable("u{0}".format(j + 1), cat="Binary") for j in range(parcel.containers)]
print(us)
#location of left bottom (x,y,z)
xs = [LpVariable("x{0}".format(i+1), cat="Integer") for i in range(parcel.parcels)]
ys = [LpVariable("y{0}".format(i+1), cat="Integer") for i in range(parcel.parcels)]
zs = [LpVariable("z{0}".format(i+1), cat="Integer") for i in range(parcel.parcels)]
rs = [LpVariable("r{0}".format(i+1), cat="Integer") for i in range(parcel.parcels)]
ss = [LpVariable("s{0}".format(i+1), cat="Integer") for i in range(parcel.parcels)]
ts = [LpVariable("t{0}".format(i+1), cat="Integer") for i in range(parcel.parcels)]
#for the overlapping constraint
xik = [LpVariable("xik", cat="Binary")]
yik = [LpVariable("yik", cat="Binary")]
zik = [LpVariable("zik", cat="Binary")]
xki = [LpVariable("xki", cat="Binary")]
yki = [LpVariable("yki", cat="Binary")]
zki = [LpVariable("zki", cat="Binary")]
#orientation
a = ["1", "2", "3"]
b = ["1", "2", "3"]
os = [LpVariable("o{0}{1}".format(j, k), cat="Binary")for j in a for k in b]
print(os)
# Objective function
t = lpSum([us[i] * parcel.conVolume[i] for i in range(parcel.containers)]) - sum(parcel.parVolume)
prob += t
print(t)
# Dimension Constraint
a = []
for j in range(parcel.parcels):
b = rs[j] - xs[j]
a.append(b)
a[j] = parcel.parLength[j]
print(a)
for j in range(parcel.parcels):
u = ps[j * parcel.containers: (j + 1) * parcel.containers]
condition1 = sum([u1 * w for u1, w in zip(u, parcel.conLength)])
#print(rs[j])
t = rs[j] <= condition1
prob += t
print(t)
# Overlapping Constraint
for i in range(parcel.parcels):
if rs[i - 1] <= xs[i]:
xik = 1
xki = 0
elif xs[i] < rs[i + 1]:
xik = 0
xki = 1
print(xik, xki)
for i in range(parcel.parcels):
# for k in range(parcel.parcels):
# u = bs[i * parcel.containers: (i + 1) * parcel.containers]
if ss[i - 1] <= ys[i]:
yik = 1
yki = 0
elif ss[i] < ys[i - 1]:
yik = 0
yki = 1
print(yik, yki)
for i in range(parcel.parcels):
# for k in range(parcel.parcels):
# u = bs[i * parcel.containers: (i + 1) * parcel.containers]
if ts[i - 1] <= zs[i]:
zik = 1
zki = 0
elif ts[i] < zs[i - 1]:
zik = 0
zki = 1
print(zik, zki)
li = []
for j in range(parcel.parcels):
u = ps[j * parcel.containers: (j + 1) * parcel.containers]
# print(u)
li.append(u)
# print(li)
r = []
for i in range(parcel.containers):
z = [x[i] for x in li]
r.append(z)
for i in range(0, len(r)):
for j in range(0, len(r[i])):
if (j == len(r[i]) - 1):
s = r[i][-1] + r[i][0]
else:
s = r[i][j] + r[i][j + 1]
# print(s)
t = xik + xki + yik + yki + zik + zki >= s - 1
prob += t
print(t)
for i in range(parcel.containers):
for j in range(parcel.parcels):
a = rs[j - 1] <= xs[j] + (1 - xik) * parcel.conLength[i]
b = xs[j] + 1 <= rs[j-1] + (xik * parcel.conLength[i])
c = ss[j - 1] <= ys[j] + (1 - yik) * parcel.conWidth[i]
d = ys[j] + 1 <= ss[j-1] + (yik * parcel.conWidth[i])
e = ts[j - 1] <= zs[j] + (1 - zik) * parcel.conHeight[i]
f = zs[j] + 1 <= ts[j-1] + (zik * parcel.conHeight[i])
prob += a, b
prob += c, d
prob += e, f
print(a, b, c, d, e, f)
#
Orientation Constraint
for i in range(parcel.parcels):
p = (rs[i] - xs[i]) == ((os[0] * parcel.parLength[i])+(os[1] * parcel.parWidth[i])+(os[2]*parcel.parHeight[i]))
q = (ss[i] - ys[i]) == ((os[3] * parcel.parLength[i]) + (os[4] * parcel.parWidth[i]) + (os[5] * parcel.parHeight[i]))
r = (ts[i] - zs[i]) == ((os[6] * parcel.parLength[i])+(os[7] * parcel.parWidth[i])+(os[8]*parcel.parHeight[i]))
prob += q
prob += p, r
print(p)
print(q)
print(r)
# Output
o11 = 0.0
o12 = 0.0
o13 = 0.0
o21 = 0.0
o22 = 0.0
o23 = 0.0
p11 = 1.0
p12 = 0.0
p21 = 1.0
p22 = 0.0
p31 = 1.0
p32 = 0.0
r1 = 0.0
r2 = 0.0
r3 = 0.0
s1 = 0.0
s2 = 0.0
s3 = 0.0
t1 = 0.0
t2 = 0.0
t3 = 0.0
u1 = 1.0
u2 = 0.0
x1 = 0.0
x2 = 0.0
x3 = 0.0
y1 = 0.0
y2 = 0.0
y3 = 0.0
z1 = 0.0
z2 = 0.0
z3 = 0.0
ВОПРОСЫ / ПОМОЩЬ:
- Всевыходные значения равны 0. Я не уверен, есть ли какая-то проблема в моем определении ограничений. Может кто-нибудь помочь проверить мой код?
СПАСИБО!