Advanced search
Start date
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Exact algorithms for class-constrained packing problems

Full text
Borges, Yulle G. F. [1] ; Miyazawa, Flavio K. [1] ; Schouery, Rafael C. S. [1] ; Xavier, Eduardo C. [1]
Total Authors: 4
[1] Univ Estadual Campinas, Av Albert Einstein 1251, Cidade Univ, Campinas, SP - Brazil
Total Affiliations: 1
Document type: Journal article
Web of Science Citations: 1

We consider a generalization of the classic Bin Packing Problem, called the Class-Constrained Bin Packing Problem (CCBPP), in which given a set of items, each one with a size and a class, one must pack the items in the least amount of bins respecting the bin capacity and the number of different classes that it can hold. We also consider the Class-Constrained Knapsack Problem (CCKP), in which items also have a value and one must select a subset of items with a maximum value which fits in a single bin. We consider a Branch-and-Price framework for CCBPP, exploring several options in the design of a Branch-and-Price algorithm. For the Pricing Problem, which is equivalent to the CCKP, we present two dynamic programming algorithms and a Branch-and-Bound algorithm. We also present other exact algorithms for generalizations of CCKP. These generalized problems also appear as Pricing Problems when solving the CCBPP. Our best algorithm for CCBPP was able to solve 95% of the instances considered in less than 15 min. (AU)

FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
Grantee:Flávio Keidi Miyazawa
Support type: Research Projects - Thematic Grants
FAPESP's process: 14/25892-4 - Class constrained cutting stock problems
Grantee:Yulle Glebbyo Felipe Borges
Support type: Scholarships in Brazil - Master
FAPESP's process: 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings
Grantee:Reinaldo Morabito Neto
Support type: Research Projects - Thematic Grants
FAPESP's process: 16/23552-7 - Cutting and Packing Problems: Practical and Theoretical Approaches
Grantee:Rafael Crivellari Saliba Schouery
Support type: Regular Research Grants