Meta-heuristics for the colored bin packing problem

• Grant number: 20/06511-0
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: September 01, 2020
• End date: August 31, 2021
• 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: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points, AP.TEM

Abstract

The Bin Packing Problem consists of: given a set of items of different sizes, we have as objective distribute them in bins with limited capacity, minimizing the number of bins used. A generalization for the Bin Packing Problem is the Colored Bin Packing Problem, in which each item has a size and a color, with an extra restriction in which say that two items of the same color cannot be packed one after the other. Both problems belonging to the NP-hard class, what implies not there are algorithms that optimally solve them in polynomial time, unless than P = NP. Since, in general, algorithms not polynomial time are expensive, then is support the use of meta-heuristics for the solution of NP-hard problems, which usually provide solutions near the optimal solutions in a computationally reasonable time. In this project, will be studied meta-heuristics for the Colored Bin Packing Problem, an approach that is still unexplored in the literature. Besides, the project also aims to enroll the candidate in the field of scientific research and complementing his graduation.