An Analysis of Solutions to the 2D Bin Packing Problem and Additional Complexities

Amitesh Anand Pandey1

1Lotus Valley International School, Gurugram, Haryana, India.

Abstract: The Bin Packing problem in 2 space is an NP-Hard combinatorial problem in optimization of packing and arrangement of objects in a given space. It has a wide variety of applications ranging from logistics in retail industries to resource allocation in cloud computing. In this paper, we discuss the mathematical formulation of this problem. Furthermore, we analyse its time complexity, its NP-Hardness and some of its stochastic solutions with their efficiencies. We then propose additional complexities that would make the problem more fit for industrial use and discuss in depth the domains in which it might prove to be useful. We conclude while suggesting areas of improvement in operations research on this subject.
Keywords: Linear Programming, Bin-Packing, Operations Research, Computational Geometry, Heuristic Programming.

Cite this article as: Amitesh Anand Pandey, An Analysis of Solutions to the 2D Bin Packing Problem and Additional Complexities, Int. J. Math. And Appl., vol. 9, no. 3, 2021, pp. 111-118.

  1. Roy P. Pargas and Rajat Jain, A parallel stochastic optimization algorithm for solving 2D bin packing problems, Proceedings of 9th IEEE Conference on Artificial Intelligence for Applications, (1993), 18-25.
  2. D. S. Liu, K. C. Tan, S. Y. Huang, C. K. Goh and W. K. Ho, On solving multiobjective bin packing problems using evolutionary particle swarm optimization, European Journal of Operational Research, 190(2)(2008), 357-382.
  3. Thomas Hage, Kyrre Begnum and Anis Yazidi, Saving the Planet with Bin Packing - Experiences Using 2D and 3D Bin Packing of Virtual Machines for Greener Clouds, 2014 IEEE 6th International Conference on Cloud Computing Technology and Science, (2014), 240-245.
  4. Chanalea Munien and Absalom E. Ezugwu, Metaheuristic algorithms for one-dimensional bin-packing problems: A survey of recent advances and applications, Journal of Intelligent Systems, 30(1)(2021), 636-663.
  5. Andrew Chi-Chih Yao, New algorithms for bin packing, Journal of the ACM, 27(2)(1980), 207-227.
  6. Benoit Chachuat, Mixed-integer linear programming (MILP): Model formulation, McMaster University Department of Chemical Engineering, 17(2019).
  7. Eva Tardos and Jon Kleinberg, Algorithm design, Pearson Education India, (2006).
  8. Christian Blum and Verena Schmid, Solving the 2D Bin Packing Problem by Means of a Hybrid Evolutionary Algorithm, Procedia Computer Science, 18(2013), 899-908.
  9. Ian P Gent, Heuristic solution of open bin packing problems, Journal of Heuristics, 3(4)(1998), 299-304.
  10. N. M. Cid-Garcia and Y. A. Rios-Solis, Positions and covering: A two-stage methodology to obtain optimal solutions for the 2d-bin packing problem, PloS ONE, 15(4)(2020).
  11. Silvano Martello and Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley and Sons, (1990).
  12. Jakob Puchinger and Gunther R. Raidl, An Evolutionary Algorithm for Column Generation in Integer Programming: An Effective Approach for 2D Bin Packing, PPSN VIII, 8th International Conference, (2004), 642-651.
  13. Tijana Sukilovic and Filipovic Vladimir, Solving the two-dimensional packing problem with mM calculus, Yugoslav Journal of Operations Research, 21(2011), 93-102.
  14. Charles Robert Darwin, On the Origin of Species, Routledge, (2004).
  15. Khaoula Hamdi-Dhaoui, Nacima Labadie and Alice Yalaoui, Algorithms for the Two Dimensional Bin Packing Problem with Partial Conflicts, RAIRO Operations Research, 46(2012), 41-62.
  16. Bhuvaneshwaran Ravi, Kameswaran Rangasamy and Serlin Tamilselvam, Bin Packing, Proof of NP Completeness and Hardness, University of Bishops, (2006).
  17. Samir Elhedhli, Fatma Gzara and Burak Yildiz, Three-Dimensional Bin Packing and Mixed-Case Palletization, Informs Journal on Optimizaiton, 1(4)(2019), 323-352.