Combinatorial Variable-fixing and Lower-bound Techniques for the Bin Packing Problem

• Grant number: 24/17437-7
• Support Opportunities: Scholarships abroad - Research Internship - Master's degree
• Start date: February 03, 2025
• End date: August 02, 2025
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Rafael Crivellari Saliba Schouery
• Grantee: Renan Fernando Franco da Silva
• Supervisor: Manuel Iori
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Institution abroad: Università degli Studi di Modena e Reggio Emilia, Modena (UNIMORE), Italy
• Associated to the scholarship: 23/17964-4 - A Combinatorial Branch-and-Bound Algorithm for the Bin Packing Problem, BP.MS

Abstract

Cutting and Packing Problems are essential in manufacturing and logistics. They aim to minimize waste, directly influencing operational efficiency. The Cutting Stock Problem (CSP) optimizes material cutting, while the Bin Packing Problem (BPP) focuses on efficient item packing. Given their high practical applications in industry and intrinsic computational complexities, they have been widely studied in literature since the 1960s. The advancement of BPP algorithms in the literature in the last two decades was using (Integer) Linear Programming (LP), which essentially depends on the good performance of General-Purpose LP Solvers. Access to these LP solvers may inhibit or make the use of such algorithms impractical for some users since these tools have expensive licenses. This project will study combinatorial variable-fixing and lower-bound techniques for the BPP, supporting the development of branch-and-bound (B&B) approaches that do not rely on LP solvers. In addition to providing an academic contribution to a less-explored area in recent research, these techniques will be integrated into the combinatorial B&B framework currently being developed in the master's project, which will provide a standalone, open-source tool to solve BPP, CSP, and related problems.