Modelos Pseudo Polinomiais para o Problema do Empacotamento Colorido
Resumo
O Problema do Empacotamento Colorido consiste em empacotar um conjunto de itens, cada um com um tamanho e cor, na menor quantidade possível derecipientes de uma dada capacidade, de forma que não haja dois itens de uma mesma cor em sequência em nenhum recipiente. Propomos formulações pseudo polinomiais de Programação Inteira que resolvem instâncias geradas aleatoriamente com até 500 itens e 15 cores em segundos.
Palavras-chave:
Otimização Combinatória, Programação Matemática
Referências
Balogh, J., Békési, J., Dósa, G., Epstein, L., Kellerer, H., Levin, A., e Tuza, Z. (2015). Offline black and white bin packing. Theoretical Computer Science, 596:92–101.
Balogh, J., Békési, J., Dosa, G., Kellerer, H., e Tuza, Z. (2013). Black and white bin packing. In Proceedings of the 10 th International Workshop on Approximation and Online Algorithms, pages 131–144.
Böhm, M., Dósa, G., Epstein, L., Sgall, J., e Veselý, P. (2018). Colored bin packing: Online algorithms and lower bounds. Algorithmica, 80(1):155–184.
Christofides, N. e Whitlock, C. (1977). An algorithm for two-dimensional cutting problems. Operations Research, 25(1):30–44.
Dolan, E. D. e Moré, J. J. (2002). Benchmarking optimization software with performance profiles. Mathematical programming, 91(2):201–213.
Gurobi Optimization, L. (2020). Gurobi optimizer reference manual.
Herz, J. (1972). Recursive computational procedure for two-dimensional stock cutting. IBM Journal of Research and Development, 16(5):462–469.
Kantorovich, L. V. (1939). The mathematical method of production planning and organization. Management Science, 6:363–422.
Valério De Carvalho, J. (1999). Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research, 86:629-659.
Balogh, J., Békési, J., Dosa, G., Kellerer, H., e Tuza, Z. (2013). Black and white bin packing. In Proceedings of the 10 th International Workshop on Approximation and Online Algorithms, pages 131–144.
Böhm, M., Dósa, G., Epstein, L., Sgall, J., e Veselý, P. (2018). Colored bin packing: Online algorithms and lower bounds. Algorithmica, 80(1):155–184.
Christofides, N. e Whitlock, C. (1977). An algorithm for two-dimensional cutting problems. Operations Research, 25(1):30–44.
Dolan, E. D. e Moré, J. J. (2002). Benchmarking optimization software with performance profiles. Mathematical programming, 91(2):201–213.
Gurobi Optimization, L. (2020). Gurobi optimizer reference manual.
Herz, J. (1972). Recursive computational procedure for two-dimensional stock cutting. IBM Journal of Research and Development, 16(5):462–469.
Kantorovich, L. V. (1939). The mathematical method of production planning and organization. Management Science, 6:363–422.
Valério De Carvalho, J. (1999). Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research, 86:629-659.
Publicado
30/06/2020
Como Citar
BORGES, Yulle G. F.; SCHOUERY, Rafael C. S..
Modelos Pseudo Polinomiais para o Problema do Empacotamento Colorido. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 37-40.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2020.11084.
