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

Author(s)

Yulle Glebbyo Felipe Borges

• Document type: Master's Dissertation
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2016-09-12

Examining board members

Flávio Keidi Miyazawa; Kelly Cristina Poldi; Fábio Luiz Usberti

• Advisor: Eduardo Candido Xavier; Flávio Keidi Miyazawa; Rafael Crivellari Saliba Schouery

Abstract

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 Opportunities: Scholarships in Brazil - Master