Binpacking -多个约束: weight+volume

Question

我有一个有5万份订单的数据集。每个订单有20种产品。产品体积和重量存在(以及x，y，z尺寸)。我有恒定体积V_max和W_max最大重量容量的装船箱。每个订单我希望最小化在V< V_max和W< W_max约束下使用的框数。

在搜索网页的过程中，我遇到了许多二进制打包算法，但它们似乎都没有奏效。有谁知道一个优雅(快速)的python算法来解决这个问题吗？

Answer 1

下面是一个使用cvxpy的快速原型(1.0分支！)CoinOR的Cbc MIP-求解器通过赛尔普。(一切都是开源的)

我使用cvxpy是因为它允许漂亮、简洁的建模(与cvxpy相比，cvxpy所做的不仅仅是建模！)在现实世界的实现中，人们会直接给那些求解者喂食(不太好的代码)，这也会提高性能(cvxpy不用花时间；我们可以使用Simplex特性，比如专用变量边界)。这也允许为您的问题调优解决程序(例如，Cbc/Cgl的切割平面设置)。如果实例太难，也可以使用时间限制或MIPgaps来获得良好的近似(NP-硬度！)。

提高性能的第一种方法(使用cvxpy；在此版本中没有求解器选项)将是某种对称缩减(使用第一个N个框；不要乱置N个<< M框)。编辑:添加->的最简单的方法见下面！

因为你似乎得到了一个无限的等盒供应，优化订单是独立的！使用了这个事实，并且代码解决了优化单个订单的问题！(如果您有不同的框和基数，并且在某些订单中使用某个方框，则会改变这种情况，不允许它在其他订单中使用)。独立解决遵循理论。在实践中，当外部语言是python时，一次对所有命令进行一次大的解决可能有一些好处(求解者会在某种程度上承认独立性；但很难说这是否值得尝试)。

此代码：

• 是很小的
• 是一种很好的数学形式
• 对于更大和更复杂的示例，应该扩展得很好
  • (考虑到这种高质量的解决方案，默认的解决方案将早早地陷入困境)

​

• 将在有限时间内找到一个全局最优(完全)。

(在非Linux系统上安装可能很麻烦；在本例中:将此作为一种方法而不是现成的代码)

代码

import numpy as np
import cvxpy as cvx
from timeit import default_timer as time

# Data
order_vols = [8, 4, 12, 18, 5, 2, 1, 4]
order_weights = [5, 3, 2, 5, 3, 4, 5, 6]

box_vol = 20
box_weight = 12

N_ITEMS = len(order_vols)
max_n_boxes = len(order_vols) # real-world: heuristic?

""" Optimization """
M = N_ITEMS + 1

# VARIABLES
box_used = cvx.Variable(max_n_boxes, boolean=True)
box_vol_content = cvx.Variable(max_n_boxes)
box_weight_content = cvx.Variable(max_n_boxes)
box_item_map = cvx.Variable((max_n_boxes, N_ITEMS), boolean=True)

# CONSTRAINTS
cons = []

# each item is shipped once
cons.append(cvx.sum(box_item_map, axis=0) == 1)

# box is used when >=1 item is using it
cons.append(box_used * M >= cvx.sum(box_item_map, axis=1))

# box vol constraints
cons.append(box_item_map * order_vols <= box_vol)

# box weight constraints
cons.append(box_item_map * order_weights <= box_weight)

problem = cvx.Problem(cvx.Minimize(cvx.sum(box_used)), cons)
start_t = time()
problem.solve(solver='CBC', verbose=True)
end_t = time()
print('time used (cvxpys reductions & solving): ', end_t - start_t)
print(problem.status)
print(problem.value)
print(box_item_map.value)

""" Reconstruct solution """
n_boxes_used = int(np.round(problem.value))
box_inds_used = np.where(np.isclose(box_used.value, 1.0))[0]

print('N_BOXES USED: ', n_boxes_used)
for box in range(n_boxes_used):
    print('Box ', box)
    raw = box_item_map[box_inds_used[box]]
    items = np.where(np.isclose(raw.value, 1.0))[0]
    vol_used = 0
    weight_used = 0
    for item in items:
        print('   item ', item)
        print('       vol: ', order_vols[item])
        print('       weight: ', order_weights[item])
        vol_used += order_vols[item]
        weight_used += order_weights[item]
    print(' total vol: ', vol_used)
    print(' total weight: ', weight_used)

输出

Welcome to the CBC MILP Solver 
Version: 2.9.9 
Build Date: Jan 15 2018 

command line - ICbcModel -solve -quit (default strategy 1)
Continuous objective value is 0.888889 - 0.00 seconds
Cgl0006I 8 SOS (64 members out of 72) with 0 overlaps - too much overlap or too many others
Cgl0009I 8 elements changed
Cgl0003I 0 fixed, 0 tightened bounds, 19 strengthened rows, 0 substitutions
Cgl0004I processed model has 32 rows, 72 columns (72 integer (72 of which binary)) and 280 elements
Cutoff increment increased from 1e-05 to 0.9999
Cbc0038I Initial state - 9 integers unsatisfied sum - 2.75909
Cbc0038I Pass   1: suminf.    1.60000 (5) obj. 3 iterations 10
Cbc0038I Pass   2: suminf.    0.98824 (5) obj. 3 iterations 5
Cbc0038I Pass   3: suminf.    0.90889 (5) obj. 3.02 iterations 12
Cbc0038I Pass   4: suminf.    0.84444 (3) obj. 4 iterations 8
Cbc0038I Solution found of 4
Cbc0038I Before mini branch and bound, 60 integers at bound fixed and 0 continuous
Cbc0038I Full problem 32 rows 72 columns, reduced to 0 rows 0 columns
Cbc0038I Mini branch and bound did not improve solution (0.01 seconds)
Cbc0038I Round again with cutoff of 2.97509
Cbc0038I Pass   5: suminf.    1.62491 (7) obj. 2.97509 iterations 2
Cbc0038I Pass   6: suminf.    1.67224 (8) obj. 2.97509 iterations 7
Cbc0038I Pass   7: suminf.    1.24713 (5) obj. 2.97509 iterations 3
Cbc0038I Pass   8: suminf.    1.77491 (5) obj. 2.97509 iterations 9
Cbc0038I Pass   9: suminf.    1.08405 (6) obj. 2.97509 iterations 8
Cbc0038I Pass  10: suminf.    1.57481 (7) obj. 2.97509 iterations 12
Cbc0038I Pass  11: suminf.    1.15815 (6) obj. 2.97509 iterations 1
Cbc0038I Pass  12: suminf.    1.10425 (7) obj. 2.97509 iterations 17
Cbc0038I Pass  13: suminf.    1.05568 (8) obj. 2.97509 iterations 17
Cbc0038I Pass  14: suminf.    0.45188 (6) obj. 2.97509 iterations 15
Cbc0038I Pass  15: suminf.    1.67468 (8) obj. 2.97509 iterations 22
Cbc0038I Pass  16: suminf.    1.42023 (8) obj. 2.97509 iterations 2
Cbc0038I Pass  17: suminf.    1.92437 (7) obj. 2.97509 iterations 15
Cbc0038I Pass  18: suminf.    1.82742 (7) obj. 2.97509 iterations 8
Cbc0038I Pass  19: suminf.    1.31741 (10) obj. 2.97509 iterations 15
Cbc0038I Pass  20: suminf.    1.01947 (6) obj. 2.97509 iterations 12
Cbc0038I Pass  21: suminf.    1.57481 (7) obj. 2.97509 iterations 14
Cbc0038I Pass  22: suminf.    1.15815 (6) obj. 2.97509 iterations 1
Cbc0038I Pass  23: suminf.    1.10425 (7) obj. 2.97509 iterations 15
Cbc0038I Pass  24: suminf.    1.08405 (6) obj. 2.97509 iterations 1
Cbc0038I Pass  25: suminf.    3.06344 (10) obj. 2.97509 iterations 13
Cbc0038I Pass  26: suminf.    2.57488 (8) obj. 2.97509 iterations 10
Cbc0038I Pass  27: suminf.    2.43925 (7) obj. 2.97509 iterations 1
Cbc0038I Pass  28: suminf.    0.91380 (3) obj. 2.97509 iterations 6
Cbc0038I Pass  29: suminf.    0.46935 (3) obj. 2.97509 iterations 6
Cbc0038I Pass  30: suminf.    0.46935 (3) obj. 2.97509 iterations 0
Cbc0038I Pass  31: suminf.    0.91380 (3) obj. 2.97509 iterations 8
Cbc0038I Pass  32: suminf.    1.96865 (12) obj. 2.97509 iterations 23
Cbc0038I Pass  33: suminf.    1.40385 (6) obj. 2.97509 iterations 13
Cbc0038I Pass  34: suminf.    1.90833 (7) obj. 2.79621 iterations 16
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 42 integers at bound fixed and 0 continuous
Cbc0038I Full problem 32 rows 72 columns, reduced to 20 rows 27 columns
Cbc0038I Mini branch and bound improved solution from 4 to 3 (0.06 seconds)
Cbc0038I After 0.06 seconds - Feasibility pump exiting with objective of 3 - took 0.06 seconds
Cbc0012I Integer solution of 3 found by feasibility pump after 0 iterations and 0 nodes (0.06 seconds)
Cbc0001I Search completed - best objective 3, took 0 iterations and 0 nodes (0.06 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from 2.75 to 2.75
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Optimal solution found

Objective value:                3.00000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.07
Time (Wallclock seconds):       0.05

Total time (CPU seconds):       0.07   (Wallclock seconds):       0.05

更有趣的是：

time used (cvxpys reductions & solving):  0.07740794896380976
optimal
3.0
[[0. 0. 0. 1. 0. 0. 1. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0.]
 [1. 0. 0. 0. 1. 1. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 1. 1. 0. 0. 0. 0. 1.]
 [0. 0. 0. 0. 0. 0. 0. 0.]]
N_BOXES USED:  3
Box  0
   item  3
       vol:  18
       weight:  5
   item  6
       vol:  1
       weight:  5
 total vol:  19
 total weight:  10
Box  1
   item  0
       vol:  8
       weight:  5
   item  4
       vol:  5
       weight:  3
   item  5
       vol:  2
       weight:  4
 total vol:  15
 total weight:  12
Box  2
   item  1
       vol:  4
       weight:  3
   item  2
       vol:  12
       weight:  2
   item  7
       vol:  4
       weight:  6
 total vol:  20
 total weight:  11

跟随您的维度的实例如下：

order_vols = [8, 4, 12, 18, 5, 2, 1, 4, 6, 5, 3, 2, 5, 11, 17, 15, 14, 14, 12, 20]
order_weights = [5, 3, 2, 5, 3, 4, 5, 6, 3, 11, 3, 8, 12, 3, 1, 5, 3, 5, 6, 7]

box_vol = 20
box_weight = 12

当然，这将是更多的工作：

Result - Optimal solution found

Objective value:                11.00000000
Enumerated nodes:               0
Total iterations:               2581
Time (CPU seconds):             0.78
Time (Wallclock seconds):       0.72

Total time (CPU seconds):       0.78   (Wallclock seconds):       0.72

N_BOXES USED:  11

编辑:对称约简

玩弄不同的配方确实表明，有时很难事先说出什么是有用的，什么是不管用的！

但是，一种廉价的、小的对称性--利用变化的方式--应该总是有效的(如果一个订单的大小不是太大的话: 20是可以的；到了30岁的时候，它可能开始变得至关重要)。这种方法称为字典微扰(整数线性规划中的对称性)。

我们可以添加一个变量-固定(如果有一个解决方案，将始终有一个相同成本的解决方案与此固定)：

cons.append(box_item_map[0,0] == 1)

我们改变了目标：

# lex-perturbation
c = np.power(2, np.arange(1, max_n_boxes+1))
problem = cvx.Problem(cvx.Minimize(c * box_used), cons)

# small change in reconstruction due to new objective
n_boxes_used = int(np.round(np.sum(box_used.value)))

对于上述N=20问题，我们现在实现：

Result - Optimal solution found

Objective value:                4094.00000000
Enumerated nodes:               0
Total iterations:               474
Time (CPU seconds):             0.60
Time (Wallclock seconds):       0.44

Total time (CPU seconds):       0.60   (Wallclock seconds):       0.44

time used (cvxpys reductions & solving):  0.46845901099732146

N_BOXES USED:  11