A Combinatorial Branch-and-Bound Algorithm for the Bin Packing Problem

• Grant number: 23/17964-4
• Support Opportunities: Scholarships in Brazil - Master
• Start date: July 01, 2024
• Status: Discontinued
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Rafael Crivellari Saliba Schouery
• Grantee: Renan Fernando Franco da Silva
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 22/05803-3 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings, AP.TEM
• Associated scholarship(s): 24/17437-7 - Combinatorial Variable-fixing and Lower-bound Techniques for the Bin Packing Problem, BE.EP.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 are problems that 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 such solvers may inhibit or make the use of such algorithms unfeasible for some users since these tools have expensive licenses. In this project, we will develop a combinatorial branch-and-bound (CBB) algorithm for the BPP, i.e., a branch-and-bound algorithm that does not use linear programming. Moreover, besides this CBB being an academic contribution to literature in an aspect less explored recently, it will be a standalone open-source tool to solve BPP, CSP, and related problems.