装箱——多重约束：重量+体积
Binpacking -- multiple constraints: weight+volume
我有一个包含 50,000 个订单的数据集。每个订单有大约 20 种产品。存在产品体积和重量（以及 x、y、z 尺寸）。我有固定体积 V_max 和最大承重量 W_max 的运输箱。每个订单我想在 V < V_max 和 W < W_max 的约束下最小化使用的盒子数量。
在网上搜索时，我遇到过许多装箱算法，但其中 none 似乎可以解决问题。有谁知道解决这个问题的优雅（快速）python 算法？
这是一个使用 cvxpy (1.0 branch!) and CoinOR's Cbc MIP-solver through cylp 的快速原型。 （一切都是open-source）
我正在使用 cvxpy，因为它允许漂亮简洁的建模（需要一些成本，因为 cvxpy 做的不仅仅是建模！）。在 real-world 实现中，人们会直接提供那些求解器（不太好的代码），这也会提高性能（cvxpy 不会花费时间；我们可以像专用 variable-bounds 一样使用 Simplex-features ).这也允许针对您的问题调整求解器（例如 cutting-plane 设置 Cbc/Cgl）。如果您的实例太难，您还可以使用 time-limits 或 MIPgaps 来获得良好的近似值 (NP-hardness!)。
提高性能的第一种方法（使用 cvxpy；此版本中没有 solver-options）是某种 symmetry-reduction（使用前 N 个框；不要打乱那些 N << M个盒子左右）。 编辑：添加了最简单的方法 -> 见下文！
由于您似乎得到了一个无限供应的相同盒子，因此优化订单是独立的！使用了这个事实，代码解决了优化单个订单的问题！ （如果你有不同的盒子和基数，并且对某些订单使用某些盒子不允许它在其他订单中使用，这将会改变）。 Independent-solving遵循理论。实际上，当 outer-language 为 python 时，一次对所有订单进行一次大求解可能会有一些好处（求解器会在某种程度上识别独立性；但很难说这是否值得尝试） .
此代码：
- 非常小
- （恕我直言）很不错 mathematical-form
- 应该可以很好地扩展更大更复杂的例子
- （考虑到这个 high-quality 解算器；默认的解算器会很早就出货）
- 会在有限的时间内找到一个global-optimum(完成)
（在 non-Linux 系统上安装可能会很麻烦；在这种情况下：将此作为一种方法而不是 ready-to-use 代码）
代码
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
编辑：Symmetry-reduction
尝试不同的公式确实表明，有时很难说 a-priori 什么有用什么没用！
但是便宜的小 symmetry-exploiting 更改应该总是有效（如果订单的大小不是太大：20 是可以的；在 30 时它可能开始批评）。该方法称为 词典扰动（整数线性规划中的对称性 | François Margot）。
我们可以添加一个variable-fixing（如果有解决方案，那么在这个固定的情况下总会有一个成本相同的解决方案）：
cons.append(box_item_map[0,0] == 1)
然后我们更改 objective:
# 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
我有一个包含 50,000 个订单的数据集。每个订单有大约 20 种产品。存在产品体积和重量（以及 x、y、z 尺寸）。我有固定体积 V_max 和最大承重量 W_max 的运输箱。每个订单我想在 V < V_max 和 W < W_max 的约束下最小化使用的盒子数量。
在网上搜索时，我遇到过许多装箱算法，但其中 none 似乎可以解决问题。有谁知道解决这个问题的优雅（快速）python 算法？
这是一个使用 cvxpy (1.0 branch!) and CoinOR's Cbc MIP-solver through cylp 的快速原型。 （一切都是open-source）
我正在使用 cvxpy，因为它允许漂亮简洁的建模（需要一些成本，因为 cvxpy 做的不仅仅是建模！）。在 real-world 实现中，人们会直接提供那些求解器（不太好的代码），这也会提高性能（cvxpy 不会花费时间；我们可以像专用 variable-bounds 一样使用 Simplex-features ).这也允许针对您的问题调整求解器（例如 cutting-plane 设置 Cbc/Cgl）。如果您的实例太难，您还可以使用 time-limits 或 MIPgaps 来获得良好的近似值 (NP-hardness!)。
提高性能的第一种方法（使用 cvxpy；此版本中没有 solver-options）是某种 symmetry-reduction（使用前 N 个框；不要打乱那些 N << M个盒子左右）。 编辑：添加了最简单的方法 -> 见下文！
由于您似乎得到了一个无限供应的相同盒子，因此优化订单是独立的！使用了这个事实，代码解决了优化单个订单的问题！ （如果你有不同的盒子和基数，并且对某些订单使用某些盒子不允许它在其他订单中使用，这将会改变）。 Independent-solving遵循理论。实际上，当 outer-language 为 python 时，一次对所有订单进行一次大求解可能会有一些好处（求解器会在某种程度上识别独立性；但很难说这是否值得尝试） .
此代码：
- 非常小
- （恕我直言）很不错 mathematical-form
- 应该可以很好地扩展更大更复杂的例子
- （考虑到这个 high-quality 解算器；默认的解算器会很早就出货）
- 会在有限的时间内找到一个global-optimum(完成)
（在 non-Linux 系统上安装可能会很麻烦；在这种情况下：将此作为一种方法而不是 ready-to-use 代码）
代码
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
编辑：Symmetry-reduction
尝试不同的公式确实表明，有时很难说 a-priori 什么有用什么没用！
但是便宜的小 symmetry-exploiting 更改应该总是有效（如果订单的大小不是太大：20 是可以的；在 30 时它可能开始批评）。该方法称为 词典扰动（整数线性规划中的对称性 | François Margot）。
我们可以添加一个variable-fixing（如果有解决方案，那么在这个固定的情况下总会有一个成本相同的解决方案）：
cons.append(box_item_map[0,0] == 1)
然后我们更改 objective:
# 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