Algoritmos Branch-and-Price para o Problema de Empacotamento em Recipientes com Restrições de Classe
Abstract
In the Class Constrained Binpacking Problem, a set of items of various sizes and classes must be packed in bins, each with a capacity B and a limit C on the amount of items from different classes used, in a way that minimizes the number of bins used. We present Branch-and-Price algorithms for this problem, as well as algorithms for the Class Constrained Knapsack Problem, which appears as a pricing subproblem. In the experiments, the best algorithm proposed solved 93% of the instances in less than 30 seconds.
References
Epstein, L., Imreh, C., and Levin, A. (2010). Class constrained bin packing revisited. Theoretical Computer Science, 411(34):3073–3089.
Gilmore, P. C. and Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6):849–859.
Shachnai, H. and Tamir, T. (2001). Polynomial time approximation schemes for class-constrained packing problems. Journal of Scheduling, 4(6):313–338.
Vance, P. H. (1998). Branch-and-price algorithms for the one-dimensional cutting stock problem. Computational Optimimization and Applications, 9(3):211–228.
Vance, P. H., Barnhart, C., Johnson, E. L., and Nemhauser, G. L. (1994). Solving binary cutting stock problems by column generation and branch-and-bound. Computational Optimization and Applications, 3(2):111–130.
Xavier, E. C. and Miyazawa, F. K. (2008). The class constrained bin packing problem with applications to video-on-demand. Theoretical Computer Science, 393(1):240–259.
Gilmore, P. C. and Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6):849–859.
Shachnai, H. and Tamir, T. (2001). Polynomial time approximation schemes for class-constrained packing problems. Journal of Scheduling, 4(6):313–338.
Vance, P. H. (1998). Branch-and-price algorithms for the one-dimensional cutting stock problem. Computational Optimimization and Applications, 9(3):211–228.
Vance, P. H., Barnhart, C., Johnson, E. L., and Nemhauser, G. L. (1994). Solving binary cutting stock problems by column generation and branch-and-bound. Computational Optimization and Applications, 3(2):111–130.
Xavier, E. C. and Miyazawa, F. K. (2008). The class constrained bin packing problem with applications to video-on-demand. Theoretical Computer Science, 393(1):240–259.
Published
2016-07-04
How to Cite
GLEBBYO, Yulle; MIYAZAWA, Flávio K.; SCHOUERY, Rafael C. S.; XAVIER, Eduardo C..
Algoritmos Branch-and-Price para o Problema de Empacotamento em Recipientes com Restrições de Classe. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 1. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 820-823.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2016.9833.
