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/a and 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. 0 would 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. invalid means 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

packingsolver3d (PackingSolver box)

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

py3dbp

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

jerry800416/3D-bin-packing

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

gedex/bp3d

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

U-Nesting ExtremePoint

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

U-Nesting BottomLeftFill

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

U-Nesting GA

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

U-Nesting BRKGA

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

U-Nesting SA

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

OR-Tools CP-SAT exact model

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

Martello-Pisinger-Vigo 3dbpp.c

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

  • / fixed / -

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)

packingsolver3d (PackingSolver box)

42,650,877 / 44,133,224 (-3.4%)

109 / 90 (+19)

689 / 655 (+34)

py3dbp

40,933,828 / 44,133,224 (-7.2%)

125 / 90 (+35)

822 / 655 (+167)

jerry800416/3D-bin-packing

41,234,099 / 44,133,224 (-6.6%)

125 / 90 (+35)

822 / 655 (+167)

gedex/bp3d

39,480,331 / 44,133,224 (-10.5%)

155 / 90 (+65)

890 / 655 (+235)

U-Nesting ExtremePoint

35,946,253 / 44,133,224 (-18.6%)

139 / 90 (+49)

821 / 655 (+166)

U-Nesting BottomLeftFill

27,458,255 / 44,133,224 (-37.8%)

203 / 90 (+113)

n/a / 655 (40/47 valid)

U-Nesting GA

36,172,709 / 44,133,224 (-18.0%)

176 / 90 (+86)

n/a / 655 (38/47 valid)

U-Nesting BRKGA

35,759,157 / 44,133,224 (-19.0%)

174 / 90 (+84)

n/a / 655 (38/47 valid)

U-Nesting SA

37,233,229 / 44,133,224 (-15.6%)

165 / 90 (+75)

n/a / 655 (38/47 valid)

OR-Tools CP-SAT exact model

42,808,814 / 44,133,224 (-3.0%)

n/a

n/a

Martello-Pisinger-Vigo 3dbpp.c

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*

packingsolver3d (PackingSolver box)

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

U-Nesting SA

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

U-Nesting GA

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

U-Nesting ExtremePoint

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*

U-Nesting BRKGA

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

U-Nesting BottomLeftFill

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

packingsolver3d (PackingSolver box)

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

U-Nesting SA

14

15

9

13

6

13

9

12

6

11

8

12

13

16

11

16

17

17

15

16

U-Nesting GA

13

15

9

13

6

13

8

11

6

10

7

10

12

16

11

15

17

17

14

16

U-Nesting ExtremePoint

6

14

8

10

5

12

5

11

4

6

4

6

11

13

4

15

17

16

10

13

U-Nesting BRKGA

13

15

9

13

6

12

7

11

6

10

7

12

12

13

12

15

17

17

14

15

U-Nesting BottomLeftFill

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

packingsolver3d (PackingSolver box)

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

U-Nesting SA

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

U-Nesting GA

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

U-Nesting ExtremePoint

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

U-Nesting BRKGA

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

U-Nesting BottomLeftFill

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

packingsolver3d (PackingSolver box)

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

U-Nesting ExtremePoint

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

U-Nesting SA

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

U-Nesting BRKGA

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

U-Nesting GA

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

U-Nesting BottomLeftFill

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

packingsolver3d (PackingSolver box)

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

U-Nesting ExtremePoint

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

U-Nesting SA

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

U-Nesting BRKGA

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

U-Nesting GA

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

U-Nesting BottomLeftFill

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

packingsolver3d (PackingSolver box)

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*

U-Nesting ExtremePoint

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

py3dbp

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

jerry800416/3D-bin-packing

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

gedex/bp3d

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

U-Nesting BottomLeftFill

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

U-Nesting GA

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

U-Nesting BRKGA

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

U-Nesting SA

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

packingsolver3d (PackingSolver box)

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

U-Nesting ExtremePoint

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

py3dbp

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

jerry800416/3D-bin-packing

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

gedex/bp3d

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

U-Nesting BottomLeftFill

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

U-Nesting GA

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

U-Nesting BRKGA

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

U-Nesting SA

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.