Possible algorithmic improvements

[ktnr]

In Clautiaux, F., Carlier, J., & Moukrim, A. (2007). A new exact method for the two-dimensional orthogonal packing problem. European Journal of Operational Research, 183(3), 1196-1211, it was observed that hard instances exhibit a low area waste (epsilon) in the range of 2%-7%, i.e., the sum of item areas is close the area of the bin.

From our observation, the hardest instances appear to be those that only contain items that are smaller than half of the the bin's width and height, whereas epsilon might play an additional complicating factor. This can be explained by the fact that many preprocessing and simplification techniques leverage items that are larger than half the bin dimension. Consequently, the absence of those items increases the complexity. For a collection of such instances see https://github.com/ktnr/TwoStepBranchingProcedure/tree/main/data/input/BPP-Subproblems. They are derived from subproblems of hard 2D bin packing instances that are solved by branch-and-cut. If those 2D-OPP instances can be solved efficiently, it opens the door to also close some of the hard 2D bin packing instances that still remain open after more than 30 years since they have been first introduced.

Relevant references for ideas to improve solution times for problematic 2D-OPP instances with numerous small items using ideas from:

• subsequent improvements of the main paper Clautiaux, Carlier, Moukrim, A. (2007) (skimming 103 results of referencing articles, accessed 19.08.2021):
  • Grandcolas, S., & Pinto, C. (2015). A new search procedure for the two-dimensional orthogonal packing problem. Journal of Mathematical Modelling and Algorithms in Operations Research, 14(3), 343-361.
• Clautiaux, F., Jouglet, A., Carlier, J., & Moukrim, A. (2008). A new constraint programming approach for the orthogonal packing problem. Computers & Operations Research, 35(3), 944-959 is often cited as the method with the best performance to date.
  Unfortunately, we could not reproduce the reported performance even with modern hardware and solvers, see Performance of packing problems google/or-tools#3177 and https://github.com/ktnr/BinPacking2D.
• Fekete, S. P., Schepers, J., & Van der Veen, J. C. (2007). An exact algorithm for higher-dimensional orthogonal packing. Operations Research, 55(3), 569-587. and subsequent improvements described in section 7.2 of Iori, M., de Lima, V. L., Martello, S., Miyazawa, F. K., & Monaci, M. (2021). Exact solution techniques for two-dimensional cutting and packing. European Journal of Operational Research, 289(2), 399-415.
  • Joncour, C., Pêcher, A., & Valicov, P. (2012). MPQ-trees for the orthogonal packing problem. Journal of Mathematical Modelling and Algorithms, 11(1), 3-22.
  • Joncour, C., & Pêcher, A. (2012). Consecutive ones matrices for multi-dimensional orthogonal packing problems. Journal of Mathematical Modelling and Algorithms, 11(1), 23-44.
  • Belov, G., Kartak, V., & Scheithauer, G. (2008). Lower-dimensional relaxations of higher-dimensional orthogonal packing.
• Belov, G., & Rohling, H. (2009). A branch-and-price graph-theoretical algorithm for orthogonal-packing feasibility. Technical report, Preprint MATH-NM-10-2009, Technische Universität Dresden, which has similar performance as CJCM08
• Mesyagutov, M., Scheithauer, G., & Belov, G. (2012). LP bounds in various constraint programming approaches for orthogonal packing. Computers & operations research, 39(10), 2425-2438.
• Belov, G., & Rohling, H. (2013). LP bounds in an interval-graph algorithm for orthogonal-packing feasibility. Operations Research, 61(2), 483-497.
• Korf, R. E., Moffitt, M. D., & Pollack, M. E. (2010). Optimal rectangle packing. Annals of Operations Research, 179(1), 261-295.
• Kartak, V. M., & Ripatti, A. V. (2018). The minimum raster set problem and its application to the d-dimensional orthogonal packing problem. European Journal of Operational Research, 271(1), 33-39.
• Kenmochi, M., Imamichi, T., Nonobe, K., Yagiura, M., & Nagamochi, H. (2009). Exact algorithms for the two-dimensional strip packing problem with and without rotations. European Journal of Operational Research, 198(1), 73-83. in principle quite similar to TSBP and incorporates some ideas from CJCM08 such as subset sum calculations to detect infeasibility early. And an improved algorithm from Arahori, Y., Imamichi, T., & Nagamochi, H. (2012). An exact strip packing algorithm based on canonical forms. Computers & Operations Research, 39(12), 2991-3011.

Feel free to get in touch if you want to talk about improvements or contribute.