25, September 2025

Applications of Bin Packing with Colocation Constraints in Real Life – A Review

VOLUME-11; ISSUE-9; SEPT-2025

Author(s): Debajit Sensarma

Authors Affiliations:

Assistant Professor, Department of Computer Science, Viveakananda Mission Mahavidyalaya, Chaitanyapur, Purba Medinipur, Haldia, West Bengal

DOIs:10.2015/IJIRMF/202509006     |     Paper ID: IJIRMF202509006


Abstract
Keywords
Cite this Article/Paper as
References

The Bin Packing Problem (BPP) is a well-known NP-hard optimization problem that consists of packing items of different sizes into a fixed number of containers (bins) with limited capacity in such a way that the total number of bins used is minimized. Traditionally, the focus of research has been on capacity constraints, but most real-life problems require the consideration of colocation constraints—requirements that certain items must be placed together in the same bin because of functional interdependencies, safety regulations, or operational efficiency. This review paper addresses the problem of incorporating colocations into the classic framework of BPP and its importance to contemporary computational and industrial systems. The article systematically maps the domain of application of bin packing with collocated placement constraints, including cloud computing, container orchestration, distributed storage systems, logistics, database sharding, and energy-efficient operations of data centers. These and other domains increasingly adopt collocated placement strategies because of the need to minimize latency and better resource allocation, which improves system performance. The study also classifies and analyzes heuristic, metaheuristic, exact, and machine learning approaches for solving these enhanced bin packing problems. It emphasizes critical issues like dynamic environments, conflicting constraints, and computational complexity. Using practical cases and real-life scenarios, the article explains the operational advantages of colocation-aware bin packing such as increased cost efficiency, enhanced throughput, regulatory compliance, and energy conservation. The paper ends with mentioning the selection of sustainable optimization, quantum computing, and hybrid algorithmic frameworks with real-time scheduling as active areas of future research focus. This review acts as the starting block for many researchers and practitioners looking to study and design bin packing models with real, constraint-laden, realistic requirements across a multitude of impactful fields.

Bin Packing Problem, Colocation Constraints, Resource Optimization, Cloud Computing, Heuristic Algorithms, Server Consolidation

Debajit Sensarma  (2025); Applications of Bin Packing with Colocation Constraints in Real Life – A Review, International Journal for Innovative Research in Multidisciplinary Field, ISSN(O): 2455-0620, Vol-11, Issue-9, Pp. 40-49.         Available on –   https://www.ijirmf.com/

  1. Zhu, W., Chen, S., Dai, M., & Tao, J. (2024). Solving a 3D bin packing problem with stacking constraints. Computers & Industrial Engineering, 188, 109814.
  2. Meshram, S., & Wagh, K. P. A Survey on Recent Advances in Spatio-temporal Co-location Pattern Mining. JOURNAL OF TECHNICAL EDUCATION, 218.
  3. Anand, S., & Guericke, S. (2020, September). A bin packing problem with mixing constraints for containerizing items for logistics service providers. In International Conference on Computational Logistics(pp. 342-355). Cham: Springer International Publishing.
  4. Bermond, J. C., Cohen, N., Coudert, D., Letsios, D., Milis, I., Perennes, S., & Zissimopoulos, V. (2016, August). Bin packing with colocations. In International Workshop on Approximation and Online Algorithms(pp. 40-51). Cham: Springer International Publishing.
  5. Akin, Melissa (2020). Two Dimensional Bin Packing. Industrial Engineering, Atlim University Research and Project Articles.
  6. Sensarma, D. (2024). A Study on Graph-Based Affinity Aware VM Colocation Problems. International Journal of Research Publication and Reviews. ISSN 2582-7421, Vol. 5, no. 1, pp-190-194.
  7. Naresh R.  (2023). Bin Packing Problem, Industrial Engineering, Operational Research, https://www.researchgate.net/publication/343880146_Bin_Packing_Problem_Industrial_Engineering_Operational_Research
  8. Aiyar¹, S., Gupta¹, K., Rajaraman, R., Shen, B., Sun, Z., & Sundaram, R. (2019, April). Colocation, Colocation, Colocation: Optimizing Placement in the Hybrid. In Algorithmic Aspects of Cloud Computing: 4th International Symposium, ALGOCLOUD 2018, Helsinki, Finland, August 20–21, 2018, Revised Selected Papers(Vol. 11409, p. 25). Springer.
  9. Wu, W., Fan, C., Huang, J., Liu, Z., & Yan, J. (2023). Machine learning for the multi-dimensional bin packing problem: Literature review and empirical evaluation. arXiv preprint arXiv:2312.08103.
  10. Grange, A., Kacem, I., & Martin, S. (2018). Algorithms for the bin packing problem with overlapping items. Computers & Industrial Engineering, 115, 331-341.
  11. Han, B. T., Diehr, G., & Cook, J. S. (1994). Multiple-type, two-dimensional bin packing problems: Applications and algorithms. Annals of Operations Research, 50, 239-261.
  12. Tardivo, F., Michel, L., & Pontelli, E. (2024). CP for Bin Packing with Multi-Core and GPUs. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)(pp. 28-1). Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  13. González-San-Martín, J., Cruz-Reyes, L., Dorronsoro, B., Fraire-Huacuja, H., Balderas-Jaramillo, F., Quiroz-Castellanos, M., & Rangel-Valdez, N. (2024). Deep Study on the Application of Machine Learning in Bin Packing Problems. Computación y Sistemas, 28(3), 1275-1290.
  14. González-San-Martín, J., Cruz-Reyes, L., Dorronsoro, B., Fraire-Huacuja, H., Balderas-Jaramillo, F., Quiroz-Castellanos, M., & Rangel-Valdez, N. (2024). Deep Study on the Application of Machine Learning in Bin Packing Problems. Computación y Sistemas, 28(3), 1275-1290.
  15. De Niz, D., & Rajkumar, R. (2006). Partitioning bin-packing algorithms for distributed real-time systems. International Journal of Embedded Systems, 2(3-4), 196-208.
  16. Fahmy, M. M., Elghandour, I., & Nagi, M. (2016, December). CoS-HDFS: co-locating geo-distributed spatial data in hadoop distributed file system. In Proceedings of the 3rd IEEE/ACM International Conference on Big Data Computing, Applications and Technologies(pp. 123-132).
  17. Voievodin, Y., Rozlomii, I., & Yarmilko, A. (2023, November). Approach to Evaluate Scheduling Strategies in Container Orchestration Systems. In Modeling, Control and Information Technologies: Proceedings of International scientific and practical conference(No. 6, pp. 292-295).
  18. Kanellopoulos, G. (2021). Efficient workload co-location on a Kubernetes cluster.
  19. Wickramanayaka, N. N., Keppitiyagama, C. I., & Thilakarathna, K. (2022). Communication-Affinity Aware Colocation and Merging of Containers. International Journal on Advances in ICT for Emerging Regions (ICTer), 15(3).
  20. Meyer, D. T., & Bolosky, W. J. (2012). A study of practical deduplication. ACM Transactions on Storage (ToS), 7(4), 1-20.
  21. Azar, Y., Kamara, S., Menache, I., Raykova, M., & Shepard, B. (2014, November). Co-location-resistant clouds. In Proceedings of the 6th Edition of the ACM Workshop on Cloud Computing Security(pp. 9-20).
  22. Breslow, A. D., Porter, L., Tiwari, A., Laurenzano, M., Carrington, L., Tullsen, D. M., & Snavely, A. E. (2016). The case for colocation of high performance computing workloads. Concurrency and Computation: Practice and Experience, 28(2), 232-251.
  23. Solanki, N., & Purohit, R. (2016). Energy-aware virtual machine allocations using bin packing algorithms in cloud data centers. Int J Eng and Tech Res, 5(12), 305-307.
  24. Kumar, N., Ruiz, P. M., Menon, V., Kabiljo, I., Pundir, M., Newell, A., … & Tang, C. (2024). Optimizing resource allocation in hyperscale datacenters: Scalability, usability, and experiences. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24)(pp. 507-528).
  25. Cambazard, H., Mehta, D., O’Sullivan, B., & Simonis, H. (2013). Bin packing with linear usage costs–an application to energy management in data centres. In Principles and Practice of Constraint Programming: 19th International Conference, CP 2013, Uppsala, Sweden, September 16-20, 2013. Proceedings 19(pp. 47-62). Springer Berlin Heidelberg.
  26. González-San-Martín, J., Cruz-Reyes, L., Dorronsoro, B., Fraire-Huacuja, H., Balderas-Jaramillo, F., Quiroz-Castellanos, M., & Rangel-Valdez, N. (2024). Deep Study on the Application of Machine Learning in Bin Packing Problems. Computación y Sistemas, 28(3), 1275-1290.
  27. Romero, S., Osaba, E., Villar-Rodriguez, E., Oregi, I., & Ban, Y. (2023). Hybrid approach for solving real-world bin packing problem instances using quantum annealers. Scientific Reports, 13(1), 11777.
Post Views: 20

Download Full Paper

Download PDF No. of Downloads:3 | No. of Views: 16