PackSolver: an exact algorithm for Orthogonal Packing Problems

Stéphane Grandcolas - Cédric Pinto "A new search procedure for the two-dimensional orthogonal packing problem", in Journal of Mathematical Modelling and Algorithms in Operations Research, Vol. 14 (3), pp. 343-361, 2015, DOI 10.1007/s10852-015-9278-z (pdf).

Download: PackSolver for PC x86_64 on Linux.
Try -help for the full list of options and parameters.

Solves an orthogonal packing problem (try -help for the full list of options):
$ ./packsolver -placement -file benchs-clautiaux/E03N17.txt
E03N17.txt 16 19 x 20 U 306848 0 0.33s 0 nminext 12955 sets 83424 profiles 94515 failures
The problem E03N17.txt has no solution (Unsatisfiable). The program explores 306848 nodes in 0.33 seconds.

$ ./packsolver -placement -file benchs-clautiaux/E02F20.txt
E02F20.txt 20 20 x 20 S 2014 3383 0.06s 0 nminext 19153 sets 391 profiles 328 failures
The problem E02F20.txt is satisfiable. The program explores 2014 nodes in the first phase and 3383 in the second phase.

$ ./packsolver -placement -file benchs-clautiaux/E00X23.txt
E00X23.txt 23 20 x 20 Uph2 11521230 32410 34.74s 46 nminext 450920 sets 2506107 profiles 2232958 failures
The problem E00X23.txt has no solution but there were valid horizontal placements (Unsatisfiable phase2). During the exploration 46 non-minimal extensions were performed.

Equi-perimeter instance with 24 items

The problem is to pack items of sizes 1x24, 2x23, 3x22,... in a bin whose area is as small as possible. With 24 items there are two solutions: 57x46 and 69x38. It takes 18 hours, 32 minutes and 41 seconds to the program to discover these solutions and to prove that there is no other optimal solution.

Minimal placements: counter example

Instance: 11 items of sizes 15x3, 15x3, 3x10, 3x10, 13x2, 13x2, 14x1, 2x7, 2x7, 2x4 and 2x4, and a bin of size 20x15. This instance is satisfiable but no solutions exists whose projection on the x-axis is minimal: if we consider the placement of the items on the x-axis in the following solution (that is ignoring the positions of the items on the y-axis), the position of item 6' is not minimal. Indeed it could be moved on the left not violating the height constraint.

This work is supported by the Region Provence-Cote d'Azur and the ICIA Technologies company.