Please use this identifier to cite or link to this item:
Type: Artigo
Title: Exact algorithms for class-constrained packing problems
Author: Borges, Yulle G.F.
Miyazawa, Flávio K.
Schouery, Rafael C.S.
Xavier, Eduardo C.
Abstract: 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
Subject: Algoritmos
Programação dinâmica
Country: Reino Unido
Editor: Elsevier
Rights: Fechado
Identifier DOI: 10.1016/j.cie.2020.106455
Date Issue: 2020
Appears in Collections:IC - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-85083382550.pdf2.85 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.