装箱-多重约束:重量+体积 [英] Binpacking -- multiple constraints: weight+volume
问题描述
我有一个50,000个订单的数据集.每个订单有约20个产品.存在产品的体积和重量(以及x，y，z尺寸).我有固定体积V_max和最大重量W_max的运输箱.对于每个订单，我想在V≤V的约束下使所用盒子的数量最小化. V_max，并且W ＜； W_max.
I have a dataset with 50,000 orders. Each order has ~20 products. Product volume and weight are present (as well as x,y,z dimensions). I have shipping boxes of constant volume V_max and maximum weight capacity of W_max. Per order I want to minimize the number of boxes used under the constraint that V < V_max, and W < W_max.
在搜索网络时，我遇到了许多装箱算法，但似乎没有一个能解决问题.有谁知道一个优雅(快速)的python算法来解决这个问题?
In searching the web I have come across many binpacking algorithms, but none of them seem to do the trick. Does anyone know of an elegant (and fast) python algorithm for solving this problem?
推荐答案
以下是使用 cvxpy (1.0分支！)和 CoinOR的Cbc MIP求解器通过 cylp . (一切都是开源的)
Here is a quick prototype using cvxpy (1.0 branch!) and CoinOR's Cbc MIP-solver through cylp. (everything is open-source)
我正在使用cvxpy，因为它可以进行漂亮而简洁的建模(因为cvxpy的功能不只是建模，所以要付出一定的代价！).在现实世界的实现中，可以直接将这些求解器供入(不太好的代码)，这也将提高性能(cvxpy不花时间；并且我们可以利用诸如专用变量边界之类的Simplex功能).这也可以根据您的问题调整求解器(例如Cbc/Cgl的切割平面设置).如果实例太难(NP硬度！)，还可以使用时间限制或MIPgaps以获得良好的近似值.
I'm using cvxpy as it allows beautiful concise modelling (at some cost as cvxpy does more than modelling!). In a real-world implementation, one would feed those solvers directly (less nice code) which will also improve performance (no time taken by cvxpy; and we can make use of Simplex-features like dedicated variable-bounds). This also allows tuning the solver for your problem (e.g. cutting-plane setup of Cbc/Cgl). You also also use time-limits or MIPgaps then to get good approximations if your instances are too hard (NP-hardness!).
提高性能的第一种方法(使用cvxpy；此版本中没有求解器选项)将是某种减少对称性的方法(使用前N个框；不要在周围N个< M个框附近加扰) . 添加了最简单的方法->见下文！
The first approach of improving performance (using cvxpy; no solver-options in this version) would be some kind of symmetry-reduction (use the first N boxes; don't scramble those N << M boxes around). most simple approach added -> see below!
由于您似乎无限制地购买了相等数量的盒子，因此优化订单是独立的！使用这一事实，代码解决了优化单个订单的问题！ (如果您使用不同的框和基数，并且在某些订单中使用某些框，则不允许在其他订单中使用该框，这将会改变).独立求解遵循该理论.在实践中，当外部语言是python时，一次对所有订单进行一次大求解可能会有一些好处(求解器会在某种程度上识别出独立性；但是很难说是否可以尝试这种方法.)
As you seem to got one unlimited supply of equal boxes, optimizing orders are independent! This fact is used and the code tackles the problem of optimizing one single order! (this would change if you got different boxes and cardinalities and using some box for some order disallow it's usage in other orders). Independent-solving follows the theory. In practice, when the outer-language is python, there might be some merit in doing one big solve over all orders at once (solver will somewhat recognize independence; but it's hard to say if that's something to try).
此代码:
- 非常少 (liho)(imho)的数学形式很好
- 对于更大和更复杂的示例应该很好地扩展
- (鉴于这种高质量的求解器；出厂的默认求解器会尽早解决)
- is quite minimal
- is (imho) in a nice mathematical-form
- should scale well for larger and more complex examples
- (given this high-quality solver; the default one which is shipped will struggle early)
(在非Linux系统上安装可能会很麻烦；在这种情况下，请采用这种方法代替现成的代码)
(Install might be troublesome on non-Linux systems; In this case: take this as an approach instead of ready-to-use code)
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遵循您的尺寸的实例，例如:
An instance following your dimensions like:
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
Playing around with different formulations really shows that it's sometimes hard to say a-priori what helps and what does not!
但是便宜的，可以利用对称性进行的小的更改应该总是可行的(如果订单的大小不是太大:20没问题；在30时可能开始变得至关重要).这种方法称为字典扰动"(整数线性规划中的对称|FrançoisMargot).
But a cheap small symmetry-exploiting change should always work (if the size of an order is not too big: 20 is ok; at 30 it probably starts to be critical). The approach is called lexicographic perturbation (Symmetry in Integer Linear Programming | François Margot).
我们可以添加一个变量修复(如果有解决方案，那么使用此修复程序将始终有相同成本的解决方案):
We can add one variable-fixing (if there is a solution, there will always be a solution of same costs with this fixing):
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问题，我们现在实现了:For the above
N=20problem, we now achieve: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这篇关于装箱-多重约束:重量+体积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
