Advanced search
Start date

Algoritmos branch-and-price para o problema de empacotamento em recipientes com restrições de classe

Full text
Yulle Glebbyo Felipe Borges
Total Authors: 1
Document type: Master's Dissertation
Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
Defense date:
Examining board members:
Kelly Cristina Poldi; Fábio Luiz Usberti
Advisor: Flávio Keidi Miyazawa; Rafael Crivellari Saliba Schouery; Eduardo Candido

In the Class Constrained Bin Packing Problem (CCBPP), a set of items of various sizes and classes must be packed into the smallest number of bins possible, each bin with a capacity and with a bound on the amount of different classes that can be packed in it. This problem has applications in many areas, such as packages manufacturing, the textile industry, and in multimedia applications. In this dissertation, we present a family of exact algorithms based on Branch-and-Price for the CCBPP, as well as exact algorithms for a few variations of the Class Constrained Knapsack Problem (CCKP), that appears as a subproblem in the resolution of the CCBPP with Branch-and-Price. Since, to the best of our knowledge, there are no exact solution approaches to the CCBPP in the literature, we propose adaptations of popular instances for the Bin Packing Problem (BPP) so that we can validate our algorithms through empirical experiments. Our best algorithm found an optimal solution for 92% of the proposed instances in up to 30 seconds, and for 98% of the instances in an imposed time limit of 15 minutes (AU)

FAPESP's process: 14/25892-4 - Class constrained cutting stock problems
Grantee:Yulle Glebbyo Felipe Borges
Support type: Scholarships in Brazil - Master