python - 垃圾箱包装

我有一个产品清单（一），每个都有一定的重量和体积。优化分为两步，其中第二步我一直无法解决。
第一个优化：最小化使用的料仓数量（已解决）
最小化用于包装产品列表的箱子数量。我有固定箱，具有最大的体积和重量限制。Python代码：

prob = pp.LpProblem("algorithm",pp.LpMinimize) #pp=pulp solver

Y_max=10  #bins will not exceed this number
#Y_min = minimum number of bins (calculated)
# j = index of jth bin
# i = index of ith product

w=weights #list of weights w_i for product i
v=volumes #list of volumes v_i for product i
W=W_max #maximum weight of a bin
V=V_max #maximum volume of a bin
#len(order) = number of products

x=pp.LpVariable.dicts("x_i,j", ((i, j) for i in range(len(order)) for j in range(Y_max)),0,1,pp.LpBinary) #variable indicating if product i is placed in bin j
y=pp.LpVariable.dicts("y_j", ((j,0) for j in range(Y_max)),0,1,pp.LpBinary) #variable indicating if bin j is used or unused
Y=pp.LpVariable('Y')

prob +=Y , 'objective function'
prob += pp.lpSum([y[j,0] for j in range(Y_max)]) == Y, ""

for i in range(len(order)):
    prob += pp.lpSum([x[i,j] for j in range(Y_max)]) == 1,''  #product i can only be placed in 1 bin

for j in range(Y_max):
    prob += pp.lpSum([x[i,j]*w[i] for i in range(len(order))]) <= W*y[j,0],""  #weight constraint

for j in range(Y_max):
    prob += pp.lpSum([x[i,j]*v[i] for i in range(len(order))]) <= V*y[j,0],""  #volume constraint

for j in range(Y_max):
    for i in range(len(order)):
        prob += x[i,j] <= y[j,0],"" #products i may not be placed in bin j if bin j is unnused.

prob += pp.lpSum([y[j,0] for i in range(len(order))]) >=Y_min,""
pp.LpSolverDefault.msg = 1
prob.solve()`

第二个优化：最小化垃圾箱移动到的区域数（如何在线性优化中求解？）
每个产品来自两个区域（区域1或区域2）中的一个。我们有一个z区i的列表（例如1区1，2区0）。
在料仓数量不超过最小料仓数量（在第一次优化中确定）的约束下，我是否可以在料仓上拆分产品，以使每个料仓移动到的区域数量最小化？
第一次优化的体积和重量约束仍然适用。
理想情况下，垃圾箱永远不会移动到两个区域，但在某些情况下，它是被迫这样做的（例如，第一次优化导致1个箱子包含1区和2区的产品）。

最佳答案

下面是一种方法-不一定是最简单或最有效的。类似于@juvian的建议
如果你慢慢地减少每个箱子的容量，你会发现虽然它很大，但你可以放在一小部分箱子里，每个箱子只访问一个区域当垃圾箱变小时，你不得不让垃圾箱移动到多个区域，当它们再次变小时，你不得不使用更多的垃圾箱。
目标函数中的注意事项：
prob += Y + pp.lpSum([two_zones[j] for j in range(Y_max)])/(Y_max+1)
我们把第二个目标（由两个区域的产品组成的箱的数量）除以最大箱数+ 1。这样我们总是优先考虑箱子数量的主要目标-即使每个箱子都有来自不同区域的物品，第二个和最多可以是Y_max，所以如果我们除以Y_max + 1，我们得到的值小于1.0，所以我们更愿意将使用的箱子数量减少1当你想确定目标的优先级时，这是一种常见的方法。

import numpy as np
import pulp as pp

prob = pp.LpProblem("algorithm",pp.LpMinimize) #pp=pulp solver

Y_max = 5 #bins will not exceed this number
#Y_min = minimum number of bins (calculated)
# j = index of jth bin
# i = index of ith product

# Some dummy data
n_prod = 10

np.random.seed(0)
w = np.random.uniform(2.5, 10, n_prod)  # product weights
v = np.random.uniform(0.1, 1, n_prod) # product volumes
W = 25 #maximum weight of a bin
V = 1.5  #maximum volume of a bin
z = np.random.randint(0, 2, n_prod) # product zones

x=pp.LpVariable.dicts("x_i,j", ((i, j) for i in range(n_prod) for j in range(Y_max)), cat='Binary') #variable indicating if product i is placed in bin j
y=pp.LpVariable.dicts("y_j", range(Y_max), cat='Binary') #variable indicating if bin j is used or unused
Y=pp.LpVariable('Y') # No. bins used
two_zones = pp.LpVariable.dicts("two_zones,j", range(Y_max), cat='Binary')
has_zone_0 = pp.LpVariable.dicts("has_zone_0,j", range(Y_max), cat='Binary')
has_zone_1 = pp.LpVariable.dicts("has_zone_1,j", range(Y_max), cat='Binary')

# Primary objective: minm No. bins, Secondary minimize bins that visit two zones
prob += Y + pp.lpSum([two_zones[j] for j in range(Y_max)])/(Y_max+1), 'objective function'

prob += pp.lpSum([y[j] for j in range(Y_max)]) == Y, 'set Y to No. bins'

for i in range(n_prod):
    prob += pp.lpSum([x[i,j] for j in range(Y_max)]) == 1,'each product in 1 bin %s' % i

for j in range(Y_max):
    prob += pp.lpSum([x[i,j]*w[i] for i in range(n_prod)]) <= W*y[j], 'weight constraint %s' % j

    prob += pp.lpSum([x[i,j]*v[i] for i in range(n_prod)]) <= V*y[j], 'volume constraint %s' % j

    for i in range(n_prod):
        prob += x[i,j] <= y[j], 'products only placed in used bin  %s_%s' % (j, i)

        prob += has_zone_0[j] >= x[i,j]*(z[i] == 0), 'set has_zone_0 flag %s_%s' % (j, i)
        prob += has_zone_1[j] >= x[i,j]*(z[i] == 1), 'set has_zone_1 flag %s_%s' % (j, i)

    prob += two_zones[j] >= has_zone_0[j] + has_zone_1[j] - 1, 'set two_zones flag %s' % j

prob.solve()

has_zone_0_soln = np.array([has_zone_0[j].varValue for j in range(Y_max)])
has_zone_1_soln = np.array([has_zone_1[j].varValue for j in range(Y_max)])
two_zones_soln = np.array([two_zones[j].varValue for j in range(Y_max)])
y_soln = np.array([y[j].varValue for j in range(Y_max)])

# Print some output:
print("Status:" + str(pp.LpStatus[prob.status]))
print('z: ' + str(z))
print('Y: ' + str(Y.varValue))
print('y_soln: ' + str(y_soln))
print('Objective: ' + str(pp.value(prob.objective)))
print('has_zone_0_soln: ' + str(has_zone_0_soln))
print('has_zone_1_soln: ' + str(has_zone_1_soln))
print('two_zones_soln: ' + str(two_zones_soln))