Leaderboards and full results
This page holds every number of the study: 97 cases, eleven participants, all in the same tables. Each benchmark gets four tables: the cases (what each instance is, what the best available bound is and where that bound comes from), the leaderboard (one row per participant, sorted by total, one column per case), the items placed per case where the objective is profit, and the time each participant spent per case. The participant roster and a cross-benchmark summary come first. The rules behind every cell are on Protocol and caveats; the participants are described in depth on Participants; the drawings are in Gallery.
How to read a leaderboard
Column 1 names the participant and links to its project. A suffix “(rotation relaxed)” means the participant could not keep the fixed orientation of that benchmark and solved a relaxed problem; “(reference)” marks an exact code run at its own budget to certify optima.
Column 2 is the total over all cases and orders the rows: packed profit for the knapsack family (higher is better), bins for the two bin packing families (lower is better). A participant with any missing or invalid case gets
n/aand sorts last.Column 3 repeats the theoretical bound total and gives the gap to it in parentheses: a percentage for profit, a bin count for bins.
0would mean every case reached the bound.Columns 4 onward are the cases.
*after a value means it equals the best available bound for that case, that is a proven optimum; only participants that solved the same variant can earn it.invalidmeans the placements failed the independent geometry check.The first data row, Theoretical bound, is not a participant: it lists the best bound per case, whose origin is given in the cases table of each benchmark. A bound that no participant reached is still a bound, not a known optimum.
Participants at a glance
All eleven participants, the version that ran, how each was driven, and which variant it solved on each of the three benchmarks. “fixed” means the orientation of every item was kept, “all rotations” means the benchmark allows every orientation for everybody, “rotation relaxed” means the participant rotated freely on a fixed-orientation benchmark.
Participant |
Language |
Version tested |
Method |
Driven as / budget |
Variant: knapsack / class 9 / THPACK9 |
Role |
|---|---|---|---|---|---|---|
C++ core, Python API |
upstream commit a7e53303 |
anytime portfolio: iterative beam search on an insertion branching scheme, dual-feasible-function bounds; sequential single knapsack, sequential value correction, column generation and dichotomic search for several bins |
box.solve, time_limit=10.0, memory_limit=1024, default options |
fixed / fixed / all rotations |
participant |
|
Python |
1.1.2 (PyPI) |
pivot-point greedy heuristic (Dube & Kanavathy): items by volume, first fitting pivot, six orientations tried |
best of two item orders, distribute_items=True, always rotates |
rotation relaxed / rotation relaxed / all rotations |
participant |
|
Python |
commit 75764a2 |
py3dbp fork: pivot-point greedy plus fix-point gravity drop, optional stability and load-bearing checks |
fix_point=True, check_stable=False, best of two item orders, always rotates |
rotation relaxed / rotation relaxed / all rotations |
participant |
|
Go |
commit 0ba3dcd |
Go port of the pivot-point greedy heuristic (after bom-d-van/binpacking), float64 geometry |
one greedy pass, cannot fix the orientation |
rotation relaxed / rotation relaxed / all rotations |
participant |
|
Rust |
0.9.0, commit 8cde85b |
extreme-point constructive heuristic (Crainic, Perboli & Tadei style) |
single-container API repeated per bin, fixed pose honoured |
fixed / fixed / all rotations |
participant |
|
Rust |
0.9.0, commit 8cde85b |
layer-building bottom-left-fill constructive heuristic |
single-container API repeated per bin, fixed pose honoured |
fixed / fixed / all rotations |
participant |
|
Rust |
0.9.0, commit 8cde85b |
genetic algorithm over item sequences, constructive decoder |
single-container API repeated per bin, 10 s per call, fixed pose honoured |
fixed / fixed / all rotations |
participant |
|
Rust |
0.9.0, commit 8cde85b |
biased random-key genetic algorithm over item sequences |
single-container API repeated per bin, 10 s per call, fixed pose honoured |
fixed / fixed / all rotations |
participant |
|
Rust |
0.9.0, commit 8cde85b |
simulated annealing over item sequences |
single-container API repeated per bin, 10 s per call, fixed pose honoured |
fixed / fixed / all rotations |
participant |
|
C++ core, Python API |
OR-Tools 9.15 |
exact constraint-programming model of the fixed-pose 3D knapsack: optional intervals per axis, pairwise non-overlap, maximise profit |
20 s, one thread, 4 GiB; OPTIMAL status is the proof used in the bound row |
fixed / - / - |
reference |
|
C |
new3dbpp general-packing code |
branch-and-bound over bin assignments with an exact one-bin routine and lower bounds |
1 s, one thread, generator default parameters; reports a lower and an upper bound |
|
reference |
Summary across benchmarks
Totals per benchmark with the bound total and the gap. packingsolver3d reaches every proven knapsack optimum (sixteen of the twenty cases are proven; the four open ones are all ratio-90 cases) and ends 3.4 percent below the bound total, next to the exact CP-SAT reference at 3.0 percent; it proves all ten 30-item class-9 replicates and stays within one bin of the construction on the 60- and 90-item ones; on THPACK9 it proves 31 of the 47 instances and is 34 containers over the bound total, where every heuristic is at least 166 over. The heuristics that could not keep the orientation are marked as relaxed on the two fixed-pose benchmarks.
Participant |
Egeblad-Pisinger 3D knapsack: Total / bound (gap) |
Martello-Pisinger-Vigo generator class 9: Total / bound (gap) |
Ivancic-Mathur-Mohanty THPACK9: Total / bound (gap) |
|---|---|---|---|
42,650,877 / 44,133,224 (-3.4%) |
109 / 90 (+19) |
689 / 655 (+34) |
|
40,933,828 / 44,133,224 (-7.2%) |
125 / 90 (+35) |
822 / 655 (+167) |
|
41,234,099 / 44,133,224 (-6.6%) |
125 / 90 (+35) |
822 / 655 (+167) |
|
39,480,331 / 44,133,224 (-10.5%) |
155 / 90 (+65) |
890 / 655 (+235) |
|
35,946,253 / 44,133,224 (-18.6%) |
139 / 90 (+49) |
821 / 655 (+166) |
|
27,458,255 / 44,133,224 (-37.8%) |
203 / 90 (+113) |
n/a / 655 (40/47 valid) |
|
36,172,709 / 44,133,224 (-18.0%) |
176 / 90 (+86) |
n/a / 655 (38/47 valid) |
|
35,759,157 / 44,133,224 (-19.0%) |
174 / 90 (+84) |
n/a / 655 (38/47 valid) |
|
37,233,229 / 44,133,224 (-15.6%) |
165 / 90 (+75) |
n/a / 655 (38/47 valid) |
|
42,808,814 / 44,133,224 (-3.0%) |
n/a |
n/a |
|
n/a |
168 / 90 (+78) |
n/a |
Egeblad-Pisinger 3D knapsack, twenty items
What the instances test. One container, twenty items with profit equal to volume plus 200, fixed orientation. At ratio 50 the container holds half of the total item volume, so choosing which items to pack matters as much as placing them: the constant makes fourteen small items worth more than six large ones of the same volume, and a heuristic that fills the container with the largest pieces first leaves profit on the table even when its packing is tight. At ratio 90 the container holds ninety percent of the item volume, almost everything should fit, and the difficulty moves to the placement itself. The five shape classes vary the geometry from cubes (C) to near-cubic (D), flat (F), long (L) and mixed (U) boxes.
Cases. Sixteen of the twenty optima are proven: thirteen by the CP-SAT reference, whose OPTIMAL status is a proof, and six by PackingSolver’s own bound meeting its incumbent (three of those are also CP-SAT proofs). On the four remaining cases, all at ratio 90 (D-C-90, D-R-90, F-R-90, L-C-90), neither code closed the gap within its budget and the bound row shows PackingSolver’s open bound. The last column is the status packingsolver3d itself reported and how long it ran.
Case |
Bin (x y z) |
Items (types) |
Item volume / bin volume |
Theoretical bound |
Bound source |
packingsolver3d status, time |
|---|---|---|---|---|---|---|
ep3d-20-C-C-50 |
99 x 99 x 199 |
20 (20) |
2.04 |
1,388,961 |
CP-SAT proof (20 s) |
feasible, 10.0 s |
ep3d-20-C-C-90 |
121 x 121 x 243 |
20 (20) |
1.12 |
1,907,577 |
CP-SAT proof (20 s) |
feasible, 10.0 s |
ep3d-20-C-R-50 |
120 x 120 x 241 |
20 (20) |
2.04 |
1,994,518 |
CP-SAT proof (20 s) |
feasible, 10.1 s |
ep3d-20-C-R-90 |
147 x 147 x 294 |
20 (20) |
1.11 |
3,395,391 |
CP-SAT proof (20 s) |
feasible, 10.0 s |
ep3d-20-D-C-50 |
131 x 131 x 263 |
20 (20) |
2.04 |
3,172,296 |
PackingSolver bound, closed |
optimal, 1.0 s |
ep3d-20-D-C-90 |
160 x 160 x 321 |
20 (20) |
1.12 |
7,207,521 |
PackingSolver bound, open |
feasible, 10.0 s |
ep3d-20-D-R-50 |
126 x 126 x 253 |
20 (20) |
2.03 |
3,150,255 |
CP-SAT proof (20 s) |
feasible, 10.1 s |
ep3d-20-D-R-90 |
154 x 154 x 308 |
20 (20) |
1.12 |
6,643,068 |
PackingSolver bound, open |
feasible, 10.0 s |
ep3d-20-F-C-50 |
118 x 118 x 237 |
20 (20) |
2.02 |
2,028,100 |
CP-SAT proof (20 s) |
optimal, 1.0 s |
ep3d-20-F-C-90 |
144 x 144 x 288 |
20 (20) |
1.11 |
3,484,268 |
PackingSolver bound, closed |
optimal, 2.0 s |
ep3d-20-F-R-50 |
108 x 108 x 216 |
20 (20) |
2.00 |
1,792,327 |
PackingSolver bound, closed |
optimal, 5.1 s |
ep3d-20-F-R-90 |
131 x 131 x 262 |
20 (20) |
1.12 |
3,251,350 |
PackingSolver bound, open |
feasible, 10.0 s |
ep3d-20-L-C-50 |
85 x 85 x 170 |
20 (20) |
2.02 |
867,538 |
CP-SAT proof (20 s) |
optimal, 1.0 s |
ep3d-20-L-C-90 |
103 x 103 x 207 |
20 (20) |
1.13 |
1,847,484 |
PackingSolver bound, open |
feasible, 10.0 s |
ep3d-20-L-R-50 |
68 x 68 x 137 |
20 (20) |
2.03 |
471,034 |
CP-SAT proof (20 s) |
feasible, 10.1 s |
ep3d-20-L-R-90 |
83 x 83 x 166 |
20 (20) |
1.13 |
787,377 |
CP-SAT proof (20 s) |
feasible, 10.0 s |
ep3d-20-U-C-50 |
48 x 48 x 96 |
20 (20) |
2.06 |
155,288 |
CP-SAT proof (20 s) |
optimal, 1.0 s |
ep3d-20-U-C-90 |
58 x 58 x 117 |
20 (20) |
1.16 |
234,784 |
CP-SAT proof (20 s) |
feasible, 10.0 s |
ep3d-20-U-R-50 |
47 x 48 x 81 |
20 (20) |
1.48 |
161,193 |
CP-SAT proof (20 s) |
feasible, 10.0 s |
ep3d-20-U-R-90 |
49 x 49 x 99 |
20 (20) |
1.14 |
192,893 |
CP-SAT proof (20 s) |
feasible, 10.0 s |
Leaderboard.
Participant |
Total |
Bound (gap) |
C-C-50 |
C-C-90 |
C-R-50 |
C-R-90 |
D-C-50 |
D-C-90 |
D-R-50 |
D-R-90 |
F-C-50 |
F-C-90 |
F-R-50 |
F-R-90 |
L-C-50 |
L-C-90 |
L-R-50 |
L-R-90 |
U-C-50 |
U-C-90 |
U-R-50 |
U-R-90 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Theoretical bound |
44,133,224 |
- |
1,388,961 |
1,907,577 |
1,994,518 |
3,395,391 |
3,172,296 |
7,207,521 |
3,150,255 |
6,643,068 |
2,028,100 |
3,484,268 |
1,792,327 |
3,251,350 |
867,538 |
1,847,484 |
471,034 |
787,377 |
155,288 |
234,784 |
161,193 |
192,893 |
OR-Tools CP-SAT exact model (reference) |
42,808,814 |
44,133,224 (-3.0%) |
1,388,961* |
1,907,577* |
1,994,518* |
3,395,391* |
3,172,296* |
6,649,101 |
3,150,255* |
6,218,886 |
2,028,100* |
3,484,268* |
1,792,327* |
3,114,463 |
867,538* |
1,642,564 |
471,034* |
787,377* |
155,288* |
234,784* |
161,193* |
192,893* |
42,650,877 |
44,133,224 (-3.4%) |
1,388,961* |
1,907,577* |
1,994,518* |
3,395,391* |
3,172,296* |
6,649,101 |
3,150,255* |
6,060,949 |
2,028,100* |
3,484,268* |
1,792,327* |
3,114,463 |
867,538* |
1,642,564 |
471,034* |
787,377* |
155,288* |
234,784* |
161,193* |
192,893* |
|
jerry800416/3D-bin-packing (rotation relaxed) |
41,234,099 |
44,133,224 (-6.6%) |
1,265,340 |
1,907,577 |
1,842,558 |
2,674,126 |
2,631,374 |
6,756,027 |
2,523,743 |
5,478,424 |
2,028,100 |
4,444,824 |
1,837,531 |
3,211,124 |
769,320 |
1,745,024 |
533,311 |
804,537 |
155,288 |
256,688 |
166,243 |
202,940 |
py3dbp (rotation relaxed) |
40,933,828 |
44,133,224 (-7.2%) |
1,265,340 |
1,907,577 |
1,842,558 |
2,674,126 |
2,631,374 |
5,975,879 |
2,523,743 |
5,608,635 |
2,028,100 |
4,444,824 |
1,837,531 |
3,612,020 |
769,320 |
1,693,794 |
533,311 |
804,537 |
155,288 |
256,688 |
166,243 |
202,940 |
gedex/bp3d (rotation relaxed) |
39,480,331 |
44,133,224 (-10.5%) |
1,265,340 |
1,907,577 |
1,842,558 |
2,674,126 |
2,631,374 |
5,699,205 |
2,207,343 |
5,369,131 |
2,028,100 |
4,444,824 |
1,837,531 |
3,138,587 |
769,320 |
1,693,794 |
471,295 |
743,766 |
155,288 |
256,688 |
144,574 |
199,910 |
37,233,229 |
44,133,224 (-15.6%) |
1,070,882 |
1,663,786 |
1,994,518* |
3,181,210 |
2,826,579 |
5,718,796 |
2,930,347 |
4,965,491 |
1,806,706 |
3,089,476 |
1,672,197 |
2,755,343 |
795,098 |
1,456,988 |
279,875 |
493,405 |
155,288* |
155,288 |
95,603 |
126,353 |
|
36,172,709 |
44,133,224 (-18.0%) |
996,594 |
1,345,707 |
1,953,182 |
3,252,374 |
2,659,505 |
5,718,796 |
2,467,028 |
5,083,095 |
1,806,706 |
3,284,568 |
1,663,322 |
2,522,046 |
743,868 |
1,211,372 |
330,938 |
608,890 |
155,288* |
155,288 |
87,789 |
126,353 |
|
35,946,253 |
44,133,224 (-18.6%) |
1,265,340 |
1,907,577* |
1,842,558 |
2,674,126 |
2,439,574 |
5,987,983 |
2,416,784 |
4,976,375 |
2,028,100* |
2,710,262 |
1,504,881 |
2,101,611 |
696,880 |
1,570,124 |
386,111 |
708,450 |
155,288* |
234,784* |
146,552 |
192,893* |
|
35,759,157 |
44,133,224 (-19.0%) |
796,057 |
1,345,707 |
1,943,009 |
3,280,875 |
2,826,579 |
5,549,470 |
2,658,133 |
4,677,981 |
1,806,706 |
3,284,568 |
1,772,071 |
2,494,339 |
743,868 |
1,349,960 |
252,965 |
523,972 |
155,288* |
155,288 |
71,873 |
70,448 |
|
27,458,255 |
44,133,224 (-37.8%) |
965,560 |
1,759,001 |
1,630,338 |
1,899,938 |
1,856,461 |
4,264,018 |
1,520,061 |
3,501,290 |
1,557,889 |
2,657,870 |
1,414,269 |
1,665,311 |
550,741 |
938,254 |
187,065 |
455,655 |
143,236 |
231,244 |
121,287 |
138,767 |
Items placed. The same packings counted in items rather than profit. At ratio 50 the greedy libraries place four to six large items where the optimum places nine to seventeen; at ratio 90 everybody places most of the twenty and the profit differences come from the last two or three items.
Participant (items placed of 20) |
C-C-50 |
C-C-90 |
C-R-50 |
C-R-90 |
D-C-50 |
D-C-90 |
D-R-50 |
D-R-90 |
F-C-50 |
F-C-90 |
F-R-50 |
F-R-90 |
L-C-50 |
L-C-90 |
L-R-50 |
L-R-90 |
U-C-50 |
U-C-90 |
U-R-50 |
U-R-90 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
OR-Tools CP-SAT exact model (reference) |
14 |
14 |
9 |
13 |
9 |
15 |
9 |
15 |
4 |
12 |
6 |
14 |
14 |
14 |
15 |
17 |
17 |
16 |
14 |
13 |
14 |
14 |
9 |
13 |
9 |
15 |
9 |
15 |
4 |
12 |
6 |
14 |
14 |
14 |
15 |
17 |
17 |
16 |
14 |
13 |
|
jerry800416/3D-bin-packing (rotation relaxed) |
6 |
14 |
8 |
10 |
5 |
14 |
5 |
12 |
4 |
13 |
6 |
11 |
12 |
16 |
9 |
16 |
17 |
18 |
10 |
14 |
py3dbp (rotation relaxed) |
6 |
14 |
8 |
10 |
5 |
12 |
5 |
12 |
4 |
13 |
6 |
13 |
12 |
15 |
9 |
16 |
17 |
18 |
10 |
14 |
gedex/bp3d (rotation relaxed) |
6 |
14 |
8 |
10 |
5 |
11 |
4 |
11 |
4 |
13 |
6 |
11 |
12 |
15 |
6 |
12 |
17 |
18 |
6 |
12 |
14 |
15 |
9 |
13 |
6 |
13 |
9 |
12 |
6 |
11 |
8 |
12 |
13 |
16 |
11 |
16 |
17 |
17 |
15 |
16 |
|
13 |
15 |
9 |
13 |
6 |
13 |
8 |
11 |
6 |
10 |
7 |
10 |
12 |
16 |
11 |
15 |
17 |
17 |
14 |
16 |
|
6 |
14 |
8 |
10 |
5 |
12 |
5 |
11 |
4 |
6 |
4 |
6 |
11 |
13 |
4 |
15 |
17 |
16 |
10 |
13 |
|
13 |
15 |
9 |
13 |
6 |
12 |
7 |
11 |
6 |
10 |
7 |
12 |
12 |
13 |
12 |
15 |
17 |
17 |
14 |
15 |
|
11 |
12 |
8 |
10 |
4 |
9 |
3 |
8 |
5 |
8 |
5 |
5 |
11 |
11 |
8 |
9 |
15 |
13 |
8 |
9 |
Time. packingsolver3d stops early when its bound meets its incumbent and otherwise uses the whole 10 s; the greedy libraries finish in milliseconds; the U-Nesting metaheuristics ran with the 10 s budget; CP-SAT is shown with its own solver time under a 20 s limit.
Participant (time (s)) |
C-C-50 |
C-C-90 |
C-R-50 |
C-R-90 |
D-C-50 |
D-C-90 |
D-R-50 |
D-R-90 |
F-C-50 |
F-C-90 |
F-R-50 |
F-R-90 |
L-C-50 |
L-C-90 |
L-R-50 |
L-R-90 |
U-C-50 |
U-C-90 |
U-R-50 |
U-R-90 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
OR-Tools CP-SAT exact model (reference) |
0.08 |
0.12 |
0.11 |
0.10 |
20.0 |
20.0 |
1.6 |
20.0 |
19.6 |
20.0 |
20.0 |
20.0 |
0.06 |
20.0 |
0.05 |
0.05 |
0.06 |
0.10 |
0.05 |
0.08 |
10.0 |
10.0 |
10.1 |
10.0 |
1.0 |
10.0 |
10.1 |
10.0 |
1.0 |
2.0 |
5.1 |
10.0 |
1.0 |
10.0 |
10.1 |
10.0 |
1.0 |
10.0 |
10.0 |
10.0 |
|
jerry800416/3D-bin-packing (rotation relaxed) |
0.55 |
0.56 |
0.46 |
0.47 |
0.41 |
0.42 |
0.40 |
0.43 |
0.39 |
0.42 |
0.38 |
0.39 |
0.36 |
0.38 |
0.36 |
0.37 |
0.38 |
0.37 |
0.36 |
0.36 |
py3dbp (rotation relaxed) |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.02 |
0.01 |
0.02 |
0.01 |
0.02 |
0.01 |
0.02 |
0.01 |
0.02 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
gedex/bp3d (rotation relaxed) |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.01 |
0.01 |
0.01 |
0.02 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.02 |
0.02 |
0.02 |
0.02 |
|
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.03 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.02 |
0.02 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
|
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
|
0.01 |
0.01 |
0.01 |
0.01 |
0.00 |
0.01 |
0.00 |
0.01 |
0.00 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
0.01 |
|
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
Reading the results. packingsolver3d reaches the proven optimum on all sixteen proven cases and totals 42,650,877, 3.4 percent below the bound total; the exact CP-SAT reference totals 42,808,814, 3.0 percent below, and the whole difference between the two is one case, D-R-90, where CP-SAT’s incumbent after 20 s (6,218,886) is above PackingSolver’s after 10 s (6,060,949) and neither is proven. On six cases (D-C-50, F-C-50, F-C-90, F-R-50, L-C-50, U-C-50) PackingSolver’s dual-feasible-function bound closes and the solve ends after one to five seconds with status optimal; on the other proven cases it holds the optimal packing but its bound stays open, so it keeps searching until the 10 s limit and reports feasible – the proof there comes from CP-SAT. The three greedy libraries share one algorithm, py3dbp’s pivot-point rule, its fork with a gravity step and its Go port, and return identical packings on most ratio-50 cases; with free rotation they total 41,234,099 (jerry800416), 40,933,828 (py3dbp) and 39,480,331 (gedex/bp3d), 6.6 to 10.5 percent below the fixed-pose bound total, and on seven or eight cases each, nearly all of them ratio 90 or random-profit cases, their relaxed value exceeds the fixed-pose bound: that is the rotation freedom, not a better packing, and their rows carry no star for that reason. On D-C-90 jerry800416’s relaxed 6,756,027 is above every fixed-pose value; whether a fixed-pose packing of that profit exists is open. Among the participants that kept the orientation, U-Nesting SA is closest at 15.6 percent below the bound with two proven cases, then GA, ExtremePoint and BRKGA at 18 to 19 percent (ExtremePoint hits five optima, all on cube or U instances, but collapses on the flat and long classes), and BottomLeftFill at 37.8 percent: a layer builder wastes the height above every short layer, which on a knapsack means fewer items. The cube instance C-C-50 is the clearest picture of the difference and is drawn in the gallery: every greedy library packs six cubes for 1,265,340 while the optimum packs fourteen for 1,388,961.
Martello-Pisinger-Vigo generator class 9, thirty to ninety items
What the instances test. Three 100 x 100 x 100 bins are cut into 30, 60 or 90 boxes by random orthogonal guillotine cuts; the boxes fill the three bins with no slack at all. The optimum is therefore three bins for every replicate and known by construction, and reaching it means rediscovering an exact cut: a single box in the wrong place forces a fourth bin. The three sizes show at which item count each participant stops finding the cut. Orientation is fixed, as in the generator’s own solver.
Cases. Every replicate has the same bound, three bins, from the construction; the volume bound and PackingSolver’s reported bound agree with it. The last column shows where PackingSolver closed the proof.
Case |
Bin (x y z) |
Items (types) |
Item volume / bin volume |
Theoretical bound |
Bound source |
packingsolver3d status, time |
|---|---|---|---|---|---|---|
MPV-GEN-T9-N30-R01 |
100 x 100 x 100 |
30 (30) |
3.00 |
3 |
construction: three bins cut |
optimal, 1.0 s |
MPV-GEN-T9-N30-R02 |
100 x 100 x 100 |
30 (30) |
3.00 |
3 |
construction: three bins cut |
optimal, 1.0 s |
MPV-GEN-T9-N30-R03 |
100 x 100 x 100 |
30 (30) |
3.00 |
3 |
construction: three bins cut |
optimal, 1.0 s |
MPV-GEN-T9-N30-R04 |
100 x 100 x 100 |
30 (30) |
3.00 |
3 |
construction: three bins cut |
optimal, 1.0 s |
MPV-GEN-T9-N30-R05 |
100 x 100 x 100 |
30 (30) |
3.00 |
3 |
construction: three bins cut |
optimal, 1.0 s |
MPV-GEN-T9-N30-R06 |
100 x 100 x 100 |
30 (30) |
3.00 |
3 |
construction: three bins cut |
optimal, 1.0 s |
MPV-GEN-T9-N30-R07 |
100 x 100 x 100 |
30 (30) |
3.00 |
3 |
construction: three bins cut |
optimal, 1.0 s |
MPV-GEN-T9-N30-R08 |
100 x 100 x 100 |
30 (30) |
3.00 |
3 |
construction: three bins cut |
optimal, 1.0 s |
MPV-GEN-T9-N30-R09 |
100 x 100 x 100 |
30 (30) |
3.00 |
3 |
construction: three bins cut |
optimal, 1.0 s |
MPV-GEN-T9-N30-R10 |
100 x 100 x 100 |
30 (30) |
3.00 |
3 |
construction: three bins cut |
optimal, 1.0 s |
MPV-GEN-T9-N60-R01 |
100 x 100 x 100 |
60 (60) |
3.00 |
3 |
construction: three bins cut |
optimal, 1.0 s |
MPV-GEN-T9-N60-R02 |
100 x 100 x 100 |
60 (60) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N60-R03 |
100 x 100 x 100 |
60 (60) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N60-R04 |
100 x 100 x 100 |
60 (60) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N60-R05 |
100 x 100 x 100 |
60 (60) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N60-R06 |
100 x 100 x 100 |
60 (60) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N60-R07 |
100 x 100 x 100 |
60 (60) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N60-R08 |
100 x 100 x 100 |
60 (60) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N60-R09 |
100 x 100 x 100 |
60 (60) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N60-R10 |
100 x 100 x 100 |
60 (60) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N90-R01 |
100 x 100 x 100 |
90 (90) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N90-R02 |
100 x 100 x 100 |
90 (90) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N90-R03 |
100 x 100 x 100 |
90 (90) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N90-R04 |
100 x 100 x 100 |
90 (90) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N90-R05 |
100 x 100 x 100 |
90 (90) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N90-R06 |
100 x 100 x 100 |
90 (90) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N90-R07 |
100 x 100 x 100 |
90 (90) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N90-R08 |
100 x 100 x 100 |
90 (90) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N90-R09 |
100 x 100 x 100 |
90 (90) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
MPV-GEN-T9-N90-R10 |
100 x 100 x 100 |
90 (90) |
3.00 |
3 |
construction: three bins cut |
feasible, 10.0 s |
Leaderboard.
Participant |
Total |
Bound (gap) |
N30-R01 |
N30-R02 |
N30-R03 |
N30-R04 |
N30-R05 |
N30-R06 |
N30-R07 |
N30-R08 |
N30-R09 |
N30-R10 |
N60-R01 |
N60-R02 |
N60-R03 |
N60-R04 |
N60-R05 |
N60-R06 |
N60-R07 |
N60-R08 |
N60-R09 |
N60-R10 |
N90-R01 |
N90-R02 |
N90-R03 |
N90-R04 |
N90-R05 |
N90-R06 |
N90-R07 |
N90-R08 |
N90-R09 |
N90-R10 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Theoretical bound |
90 |
- |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
109 |
90 (+19) |
3* |
3* |
3* |
3* |
3* |
3* |
3* |
3* |
3* |
3* |
3* |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
|
py3dbp (rotation relaxed) |
125 |
90 (+35) |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
5 |
4 |
4 |
4 |
4 |
4 |
5 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
5 |
5 |
4 |
4 |
4 |
5 |
jerry800416/3D-bin-packing (rotation relaxed) |
125 |
90 (+35) |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
5 |
4 |
4 |
4 |
4 |
4 |
5 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
5 |
5 |
4 |
4 |
4 |
5 |
139 |
90 (+49) |
4 |
4 |
4 |
5 |
4 |
4 |
5 |
4 |
4 |
4 |
4 |
5 |
5 |
5 |
4 |
4 |
4 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
6 |
|
gedex/bp3d (rotation relaxed) |
155 |
90 (+65) |
5 |
5 |
5 |
4 |
4 |
4 |
4 |
5 |
4 |
6 |
5 |
5 |
5 |
5 |
6 |
5 |
4 |
5 |
5 |
5 |
6 |
6 |
6 |
6 |
6 |
6 |
5 |
6 |
6 |
6 |
165 |
90 (+75) |
5 |
6 |
4 |
5 |
4 |
6 |
5 |
5 |
5 |
5 |
5 |
6 |
5 |
5 |
5 |
5 |
5 |
5 |
6 |
6 |
6 |
6 |
6 |
7 |
6 |
6 |
7 |
6 |
6 |
6 |
|
Martello-Pisinger-Vigo 3dbpp.c (reference) |
168 |
90 (+78) |
4 |
5 |
5 |
4 |
5 |
3* |
3* |
3* |
3* |
5 |
6 |
7 |
5 |
6 |
6 |
6 |
4 |
6 |
7 |
6 |
6 |
7 |
8 |
7 |
7 |
6 |
7 |
6 |
7 |
8 |
174 |
90 (+84) |
5 |
6 |
5 |
5 |
4 |
6 |
5 |
6 |
5 |
5 |
5 |
6 |
6 |
5 |
6 |
5 |
5 |
6 |
6 |
6 |
7 |
6 |
7 |
7 |
6 |
7 |
7 |
6 |
7 |
6 |
|
176 |
90 (+86) |
5 |
5 |
4 |
5 |
4 |
6 |
5 |
6 |
5 |
5 |
6 |
6 |
6 |
5 |
6 |
5 |
5 |
6 |
5 |
7 |
7 |
7 |
7 |
6 |
7 |
7 |
8 |
6 |
7 |
7 |
|
203 |
90 (+113) |
6 |
6 |
5 |
5 |
6 |
6 |
6 |
6 |
7 |
6 |
6 |
8 |
6 |
7 |
7 |
8 |
6 |
6 |
7 |
7 |
9 |
7 |
8 |
7 |
7 |
7 |
8 |
8 |
8 |
7 |
Time.
Participant (time (s)) |
N30-R01 |
N30-R02 |
N30-R03 |
N30-R04 |
N30-R05 |
N30-R06 |
N30-R07 |
N30-R08 |
N30-R09 |
N30-R10 |
N60-R01 |
N60-R02 |
N60-R03 |
N60-R04 |
N60-R05 |
N60-R06 |
N60-R07 |
N60-R08 |
N60-R09 |
N60-R10 |
N90-R01 |
N90-R02 |
N90-R03 |
N90-R04 |
N90-R05 |
N90-R06 |
N90-R07 |
N90-R08 |
N90-R09 |
N90-R10 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
10.0 |
|
py3dbp (rotation relaxed) |
0.02 |
0.02 |
0.02 |
0.02 |
0.02 |
0.03 |
0.02 |
0.02 |
0.02 |
0.02 |
0.12 |
0.10 |
0.12 |
0.11 |
0.12 |
0.12 |
0.13 |
0.12 |
0.14 |
0.13 |
0.27 |
0.29 |
0.31 |
0.29 |
0.32 |
0.32 |
0.26 |
0.29 |
0.25 |
0.27 |
jerry800416/3D-bin-packing (rotation relaxed) |
0.46 |
0.48 |
0.49 |
0.48 |
0.51 |
0.50 |
0.47 |
0.47 |
0.49 |
0.48 |
0.62 |
0.57 |
0.66 |
0.61 |
0.63 |
0.61 |
0.61 |
0.62 |
0.61 |
0.60 |
0.77 |
0.79 |
0.83 |
0.76 |
0.84 |
0.80 |
0.73 |
0.75 |
0.70 |
0.70 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
|
gedex/bp3d (rotation relaxed) |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.16 |
0.19 |
0.09 |
0.06 |
0.10 |
0.14 |
0.06 |
0.09 |
0.06 |
0.06 |
0.09 |
0.13 |
0.09 |
0.11 |
0.10 |
0.08 |
0.08 |
0.07 |
0.07 |
0.08 |
0.13 |
0.10 |
0.15 |
0.13 |
0.17 |
0.16 |
0.13 |
0.11 |
0.09 |
0.09 |
|
Martello-Pisinger-Vigo 3dbpp.c (reference) |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
0.43 |
0.41 |
0.01 |
0.12 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
1.0 |
0.03 |
0.07 |
0.05 |
0.06 |
0.09 |
0.06 |
0.10 |
0.08 |
0.07 |
0.03 |
0.11 |
0.13 |
0.13 |
0.10 |
0.22 |
0.18 |
0.19 |
0.18 |
0.16 |
0.17 |
0.22 |
0.14 |
0.23 |
0.27 |
0.24 |
0.21 |
0.22 |
0.14 |
0.14 |
0.19 |
|
0.06 |
0.04 |
0.07 |
0.06 |
0.05 |
0.03 |
0.04 |
0.04 |
0.04 |
0.04 |
0.12 |
0.10 |
0.16 |
0.16 |
0.15 |
0.12 |
0.20 |
0.10 |
0.17 |
0.14 |
0.28 |
0.16 |
0.21 |
0.31 |
0.23 |
0.34 |
0.23 |
0.27 |
0.24 |
0.24 |
|
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
Reading the results. packingsolver3d rebuilds the three-bin cut of all ten 30-item replicates in about one second each and its bound proves them; at 60 items it finds the cut once (N60-R01) and packs four bins on the other nine, at 90 items four bins on all ten, always with the bound at three, so its total is 109 bins for a construction of 90: 30 + 39 + 40. The authors’ own branch-and-bound, run for one second as a reference, closes four 30-item replicates (N30-R06 to R09) and none of the larger ones, 168 bins in total; it is an exact method and would close them with more time, so its row measures speed, not quality. No heuristic reaches three bins on any replicate. py3dbp and jerry800416 total 125 (41 + 41 + 43) even though they rotate freely, so at 60 and 90 items they are only two or three bins behind packingsolver3d, whose proof is gone there too; U-Nesting ExtremePoint, the best participant that kept the orientation, totals 139 (42 + 46 + 51); gedex/bp3d 155; U-Nesting SA, BRKGA and GA 165 to 176, no better than the constructive ExtremePoint despite their 10 s budget; BottomLeftFill 203, more than twice the optimum. The mechanism is visible in the gallery: greedy placement leaves gaps that the last few boxes cannot use, and every extra bin is one of those.
Ivancic-Mathur-Mohanty THPACK9, all 47 instances
What the instances test. Weakly heterogeneous cargo: two to five item types with many copies each, 47 to 180 boxes, one container type per instance, every orientation allowed for every participant, so no row is relaxed and the comparison is direct. Optima range from two to about fifty containers.
Cases. No published optimality proof ships with the files. The bound is the tighter of the volume bound and PackingSolver’s reported bound; where PackingSolver’s incumbent meets it the instance is proven, elsewhere the gap between the best solution and the bound stays open and can be either a weak bound or a missed loading.
Case |
Bin (x y z) |
Items (types) |
Item volume / bin volume |
Theoretical bound |
Bound source |
packingsolver3d status, time |
|---|---|---|---|---|---|---|
IMM-01 |
10 x 6 x 16 |
70 (2) |
18.67 |
25 |
PackingSolver bound (volume bound 19) |
optimal, 1.0 s |
IMM-02 |
14 x 14 x 14 |
70 (2) |
6.53 |
8 |
PackingSolver bound (volume bound 7) |
feasible, 10.0 s |
IMM-03 |
20 x 16 x 20 |
180 (4) |
18.15 |
19 |
volume bound |
optimal, 1.0 s |
IMM-04 |
24 x 12 x 16 |
180 (4) |
25.21 |
26 |
volume bound |
optimal, 1.0 s |
IMM-05 |
20 x 8 x 16 |
180 (4) |
45.38 |
51 |
PackingSolver bound (volume bound 46) |
optimal, 5.0 s |
IMM-06 |
20 x 15 x 25 |
103 (3) |
9.37 |
10 |
volume bound |
optimal, 1.0 s |
IMM-07 |
15 x 15 x 20 |
103 (3) |
15.61 |
16 |
volume bound |
optimal, 1.0 s |
IMM-08 |
45 x 20 x 20 |
103 (3) |
3.90 |
4 |
volume bound |
optimal, 1.0 s |
IMM-09 |
60 x 40 x 72 |
110 (2) |
15.89 |
17 |
PackingSolver bound (volume bound 16) |
feasible, 10.0 s |
IMM-10 |
40 x 36 x 52 |
110 (2) |
36.67 |
55 |
PackingSolver bound (volume bound 37) |
optimal, 1.0 s |
IMM-11 |
60 x 52 x 64 |
110 (2) |
13.75 |
14 |
volume bound |
feasible, 10.0 s |
IMM-12 |
35 x 30 x 20 |
95 (3) |
44.40 |
53 |
PackingSolver bound (volume bound 45) |
optimal, 1.0 s |
IMM-13 |
35 x 35 x 40 |
95 (3) |
19.03 |
25 |
PackingSolver bound (volume bound 20) |
optimal, 9.0 s |
IMM-14 |
35 x 25 x 40 |
95 (3) |
26.64 |
27 |
volume bound |
optimal, 1.0 s |
IMM-15 |
24 x 20 x 24 |
95 (3) |
10.15 |
11 |
volume bound |
optimal, 1.0 s |
IMM-16 |
18 x 16 x 20 |
95 (3) |
20.29 |
26 |
PackingSolver bound (volume bound 21) |
optimal, 3.0 s |
IMM-17 |
30 x 20 x 30 |
95 (3) |
6.49 |
7 |
volume bound |
optimal, 1.0 s |
IMM-18 |
21 x 18 x 30 |
47 (3) |
1.69 |
2 |
volume bound |
optimal, 1.0 s |
IMM-19 |
20 x 15 x 29 |
47 (3) |
2.20 |
3 |
volume bound |
optimal, 1.0 s |
IMM-20 |
17 x 12 x 24 |
47 (3) |
3.91 |
5 |
PackingSolver bound (volume bound 4) |
optimal, 1.0 s |
IMM-21 |
17 x 16 x 20 |
95 (5) |
16.37 |
17 |
volume bound |
feasible, 10.0 s |
IMM-22 |
23 x 18 x 30 |
95 (5) |
7.17 |
8 |
volume bound |
optimal, 2.0 s |
IMM-23 |
15 x 12 x 30 |
95 (5) |
16.49 |
17 |
volume bound |
feasible, 10.0 s |
IMM-24 |
40 x 22 x 26 |
72 (4) |
4.64 |
5 |
volume bound |
optimal, 1.0 s |
IMM-25 |
30 x 30 x 30 |
72 (4) |
3.93 |
4 |
volume bound |
feasible, 10.0 s |
IMM-26 |
35 x 32 x 40 |
72 (4) |
2.37 |
3 |
volume bound |
optimal, 1.0 s |
IMM-27 |
25 x 17 x 30 |
95 (3) |
3.80 |
4 |
volume bound |
optimal, 2.0 s |
IMM-28 |
20 x 20 x 15 |
95 (3) |
8.08 |
9 |
volume bound |
optimal, 1.0 s |
IMM-29 |
21 x 18 x 24 |
118 (4) |
14.22 |
15 |
volume bound |
feasible, 10.0 s |
IMM-30 |
19 x 15 x 26 |
118 (4) |
17.41 |
18 |
volume bound |
feasible, 10.0 s |
IMM-31 |
23 x 20 x 27 |
118 (4) |
10.38 |
11 |
volume bound |
feasible, 10.0 s |
IMM-32 |
30 x 15 x 18 |
90 (3) |
3.11 |
4 |
volume bound |
optimal, 1.0 s |
IMM-33 |
28 x 25 x 10 |
90 (3) |
3.60 |
4 |
volume bound |
optimal, 1.0 s |
IMM-34 |
20 x 18 x 10 |
90 (3) |
7.00 |
7 |
volume bound |
feasible, 10.0 s |
IMM-35 |
25 x 21 x 25 |
84 (2) |
1.84 |
2 |
volume bound |
feasible, 10.0 s |
IMM-36 |
18 x 15 x 9 |
84 (2) |
9.96 |
14 |
PackingSolver bound (volume bound 10) |
optimal, 1.0 s |
IMM-37 |
30 x 24 x 12 |
102 (3) |
11.39 |
14 |
PackingSolver bound (volume bound 12) |
feasible, 10.0 s |
IMM-38 |
20 x 20 x 10 |
102 (3) |
24.60 |
45 |
PackingSolver bound (volume bound 25) |
optimal, 8.0 s |
IMM-39 |
18 x 16 x 30 |
102 (3) |
11.39 |
12 |
volume bound |
feasible, 10.0 s |
IMM-40 |
28 x 14 x 18 |
85 (4) |
6.81 |
7 |
volume bound |
feasible, 10.0 s |
IMM-41 |
15 x 12 x 20 |
85 (4) |
13.35 |
14 |
volume bound |
feasible, 10.0 s |
IMM-42 |
48 x 70 x 32 |
90 (3) |
3.31 |
4 |
volume bound |
optimal, 1.0 s |
IMM-43 |
57 x 69 x 44 |
90 (3) |
2.05 |
3 |
volume bound |
optimal, 1.0 s |
IMM-44 |
38 x 71 x 55 |
90 (3) |
2.40 |
3 |
volume bound |
optimal, 1.0 s |
IMM-45 |
40 x 55 x 38 |
99 (4) |
1.96 |
2 |
volume bound |
feasible, 10.0 s |
IMM-46 |
33 x 51 x 68 |
99 (4) |
1.43 |
2 |
volume bound |
optimal, 1.0 s |
IMM-47 |
25 x 60 x 43 |
99 (4) |
2.54 |
3 |
volume bound |
optimal, 1.0 s |
Leaderboard.
Participant |
Total |
Bound (gap) |
01 |
02 |
03 |
04 |
05 |
06 |
07 |
08 |
09 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
33 |
34 |
35 |
36 |
37 |
38 |
39 |
40 |
41 |
42 |
43 |
44 |
45 |
46 |
47 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Theoretical bound |
655 |
- |
25 |
8 |
19 |
26 |
51 |
10 |
16 |
4 |
17 |
55 |
14 |
53 |
25 |
27 |
11 |
26 |
7 |
2 |
3 |
5 |
17 |
8 |
17 |
5 |
4 |
3 |
4 |
9 |
15 |
18 |
11 |
4 |
4 |
7 |
2 |
14 |
14 |
45 |
12 |
7 |
14 |
4 |
3 |
3 |
2 |
2 |
3 |
689 |
655 (+34) |
25* |
9 |
19* |
26* |
51* |
10* |
16* |
4* |
19 |
55* |
16 |
53* |
25* |
27* |
11* |
26* |
7* |
2* |
3* |
5* |
20 |
8* |
19 |
5* |
5 |
3* |
4* |
9* |
16 |
22 |
12 |
4* |
4* |
8 |
3 |
14* |
23 |
45* |
15 |
8 |
15 |
4* |
3* |
3* |
3 |
2* |
3* |
|
821 |
655 (+166) |
50 |
10 |
23 |
30 |
52 |
10* |
16* |
4* |
22 |
55* |
18 |
55 |
40 |
40 |
15 |
33 |
10 |
2* |
3* |
6 |
23 |
10 |
26 |
7 |
5 |
4 |
5 |
11 |
21 |
25 |
14 |
5 |
5 |
10 |
3 |
14* |
23 |
45* |
18 |
11 |
21 |
4* |
4 |
4 |
3 |
2* |
4 |
|
822 |
655 (+167) |
50 |
10 |
23 |
30 |
52 |
10* |
16* |
4* |
22 |
55* |
20 |
56 |
40 |
40 |
15 |
33 |
10 |
2* |
3* |
6 |
23 |
10 |
22 |
7 |
5 |
4 |
5 |
11 |
21 |
25 |
14 |
5 |
5 |
11 |
3 |
14* |
23 |
45* |
18 |
11 |
21 |
5 |
4 |
4 |
3 |
2* |
4 |
|
822 |
655 (+167) |
50 |
10 |
23 |
30 |
52 |
10* |
16* |
4* |
22 |
55* |
20 |
56 |
40 |
40 |
15 |
33 |
10 |
2* |
3* |
6 |
23 |
10 |
22 |
7 |
5 |
4 |
5 |
11 |
21 |
25 |
14 |
5 |
5 |
11 |
3 |
14* |
23 |
45* |
18 |
11 |
21 |
5 |
4 |
4 |
3 |
2* |
4 |
|
890 |
655 (+235) |
50 |
10 |
24 |
27 |
65 |
11 |
16* |
4* |
25 |
55* |
25 |
68 |
40 |
40 |
15 |
33 |
10 |
3 |
4 |
6 |
23 |
11 |
24 |
7 |
5 |
4 |
5 |
12 |
22 |
25 |
16 |
5 |
18 |
20 |
3 |
16 |
23 |
45* |
18 |
12 |
23 |
5 |
4 |
4 |
3 |
2* |
4 |
|
n/a |
655 (40/47 valid) |
invalid |
15 |
30 |
invalid |
invalid |
17 |
22 |
6 |
28 |
55* |
28 |
invalid |
28 |
invalid |
15 |
33 |
11 |
3 |
4 |
6 |
32 |
18 |
invalid |
8 |
6 |
4 |
7 |
16 |
26 |
invalid |
20 |
6 |
6 |
13 |
4 |
25 |
27 |
58 |
21 |
12 |
27 |
5 |
4 |
5 |
3 |
3 |
5 |
|
n/a |
655 (38/47 valid) |
invalid |
11 |
26 |
invalid |
invalid |
11 |
17 |
6 |
20 |
invalid |
20 |
invalid |
27 |
invalid |
14 |
invalid |
10 |
3 |
4 |
6 |
25 |
12 |
invalid |
7 |
6 |
4 |
7 |
12 |
20 |
invalid |
16 |
6 |
6 |
13 |
4 |
20 |
26 |
50 |
17 |
11 |
20 |
5 |
3* |
4 |
3 |
3 |
5 |
|
n/a |
655 (38/47 valid) |
invalid |
11 |
27 |
invalid |
invalid |
11 |
17 |
6 |
20 |
invalid |
19 |
invalid |
28 |
invalid |
14 |
invalid |
10 |
3 |
4 |
6 |
25 |
12 |
invalid |
7 |
6 |
4 |
7 |
12 |
20 |
invalid |
16 |
6 |
7 |
13 |
4 |
20 |
26 |
50 |
17 |
11 |
19 |
5 |
4 |
4 |
4 |
3 |
5 |
|
n/a |
655 (38/47 valid) |
invalid |
11 |
27 |
invalid |
invalid |
11 |
17 |
6 |
23 |
invalid |
20 |
invalid |
28 |
invalid |
14 |
invalid |
9 |
3 |
4 |
6 |
25 |
12 |
invalid |
7 |
6 |
4 |
7 |
13 |
21 |
invalid |
16 |
6 |
7 |
13 |
4 |
19 |
27 |
50 |
17 |
10 |
19 |
5 |
4 |
4 |
3 |
3 |
4 |
Time.
Participant (time (s)) |
01 |
02 |
03 |
04 |
05 |
06 |
07 |
08 |
09 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
33 |
34 |
35 |
36 |
37 |
38 |
39 |
40 |
41 |
42 |
43 |
44 |
45 |
46 |
47 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1.0 |
10.0 |
1.0 |
1.0 |
5.0 |
1.0 |
1.0 |
1.0 |
10.0 |
1.0 |
10.0 |
1.0 |
9.0 |
1.0 |
1.0 |
3.0 |
1.0 |
1.0 |
1.0 |
1.0 |
10.0 |
2.0 |
10.0 |
1.0 |
10.0 |
1.0 |
2.0 |
1.0 |
10.0 |
10.0 |
10.0 |
1.0 |
1.0 |
10.0 |
10.0 |
1.0 |
10.0 |
8.0 |
10.0 |
10.0 |
10.0 |
1.0 |
1.0 |
1.0 |
10.0 |
1.0 |
1.0 |
|
0.00 |
0.00 |
0.01 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.01 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
|
0.15 |
0.26 |
1.0 |
0.76 |
0.50 |
0.57 |
0.43 |
1.0 |
0.39 |
0.26 |
0.38 |
0.26 |
0.25 |
0.24 |
0.40 |
0.40 |
0.77 |
0.25 |
0.23 |
0.17 |
0.42 |
0.57 |
0.37 |
0.28 |
0.36 |
0.43 |
0.83 |
0.49 |
0.66 |
0.68 |
0.97 |
0.87 |
0.87 |
0.55 |
1.4 |
0.48 |
0.47 |
0.22 |
0.52 |
0.41 |
0.44 |
0.91 |
0.90 |
0.96 |
1.5 |
1.1 |
1.6 |
|
0.64 |
0.67 |
1.5 |
1.3 |
1.0 |
1.0 |
0.93 |
1.6 |
0.85 |
0.75 |
0.90 |
0.63 |
0.78 |
0.79 |
0.97 |
0.83 |
1.4 |
0.64 |
0.70 |
0.57 |
0.80 |
1.2 |
1.1 |
0.72 |
0.82 |
0.92 |
1.9 |
1.1 |
1.0 |
1.1 |
1.4 |
1.6 |
1.9 |
1.1 |
1.9 |
0.92 |
1.0 |
1.0 |
1.2 |
1.1 |
0.88 |
1.9 |
1.5 |
1.8 |
2.6 |
1.6 |
1.7 |
|
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.01 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
|
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.01 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
0.00 |
|
0.16 |
0.20 |
0.55 |
0.60 |
0.66 |
0.19 |
0.25 |
0.28 |
0.29 |
0.58 |
0.29 |
0.42 |
0.34 |
0.34 |
0.20 |
0.38 |
0.18 |
0.08 |
0.08 |
0.10 |
0.33 |
0.28 |
0.36 |
0.12 |
0.17 |
0.20 |
0.40 |
0.28 |
0.50 |
0.48 |
0.52 |
0.39 |
0.45 |
0.38 |
0.17 |
0.26 |
0.36 |
0.44 |
0.28 |
0.30 |
0.36 |
0.27 |
0.24 |
0.27 |
0.47 |
0.25 |
0.34 |
|
0.09 |
0.07 |
0.34 |
0.44 |
0.55 |
0.11 |
0.17 |
0.09 |
0.20 |
0.47 |
0.21 |
0.28 |
0.19 |
0.16 |
0.19 |
0.29 |
0.19 |
0.03 |
0.03 |
0.04 |
0.29 |
0.16 |
0.26 |
0.06 |
0.06 |
0.05 |
0.11 |
0.19 |
0.43 |
0.55 |
0.32 |
0.12 |
0.08 |
0.14 |
0.10 |
0.20 |
0.26 |
0.34 |
0.22 |
0.13 |
0.19 |
0.08 |
0.08 |
0.12 |
0.14 |
0.06 |
0.14 |
|
0.15 |
0.12 |
0.35 |
0.43 |
0.65 |
0.13 |
0.16 |
0.09 |
0.25 |
0.56 |
0.27 |
0.40 |
0.17 |
0.26 |
0.18 |
0.30 |
0.14 |
0.03 |
0.03 |
0.04 |
0.22 |
0.23 |
0.43 |
0.07 |
0.06 |
0.06 |
0.11 |
0.18 |
0.45 |
0.40 |
0.33 |
0.15 |
0.10 |
0.12 |
0.10 |
0.14 |
0.21 |
0.42 |
0.19 |
0.12 |
0.16 |
0.10 |
0.10 |
0.15 |
0.13 |
0.08 |
0.16 |
Reading the results. packingsolver3d proves 31 of the 47 instances, most of them within about a second, and uses 689 containers in total against a bound total of 655: nine instances are one container over the bound, three are two over, two three over, instance 30 four over and instance 37 nine over (23 containers against a bound of 14, the one case where the bound is plainly far from anything found). Sixteen instances ran to the 10 s limit. The greedy libraries agree with it on the loose instances – py3dbp ties it on 13 instances, U-Nesting ExtremePoint on 14 – and fall behind as the fit tightens: U-Nesting ExtremePoint totals 821 (+166), py3dbp and jerry800416 822 (+167), gedex/bp3d 890 (+235). The largest single differences are instance 1 (50 containers against 25 for seventy boxes in a 10 x 6 x 16 container, one or two boxes per container), instance 13 (40 against 25), instance 14 (40 against 27) and instance 16 (33 against 26). The four U-Nesting metaheuristics returned placements that stick out of the container on seven (BottomLeftFill) to nine (GA, BRKGA, SA) instances, shown as invalid; their totals are therefore n/a, and on the instances where they are valid they sit between ExtremePoint and gedex/bp3d. Every non-invalid solution on this page, ours included, passed the same geometry check.
What the numbers do and do not say
They say that on small, constraint-free instances with a known or proven optimum, the anytime search of PackingSolver box reaches the optimum within ten seconds far more often than greedy loading heuristics and sequence metaheuristics driven through a constructive placer, that its own bound certifies a good share of those optima, and that the difference is largest exactly where the fit is tight; they also say where its ten seconds are not enough – the 60- and 90-item class-9 cuts, the open ratio-90 knapsack cases, sixteen THPACK9 instances – and that an exact CP-SAT model with twice the time is a fair match on the knapsack family. They do not rank the libraries as software: the greedy libraries answer in milliseconds and several of them handle weight, stability and stacking that box does not; every number here is a single run on one machine; and PackingSolver used several threads on the knapsack cases while everything else ran on one. The caveats are spelled out on Protocol and caveats.