Advanced search
Start date

Meta-heuristics for the colored bin packing problem

Grant number: 20/06511-0
Support type:Scholarships in Brazil - Scientific Initiation
Effective date (Start): September 01, 2020
Effective date (End): August 31, 2021
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Rafael Crivellari Saliba Schouery
Grantee:Renan Fernando Franco da Silva
Home 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


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.

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items