04 jul 2023
14:00 Defesa de Doutorado Auditório do IC3
Tema
Algoritmos Exatos e Heurísticos para Problemas de Empacotamento: Alternância de Cores, Incerteza e em Smart Grids
Aluno
Yulle Glébbyo Felipe Borges
Orientador / Docente
Rafael Crivellari Saliba Schouery - Coorientador: Flávio Keidi Miyazawa
Breve resumo
No problema do empacotamento (BPP, do inglês Bin Packing Problem), dados uma capacidade unidimensional de recipientes e um conjunto de itens unidimensionais, cada um com um comprimento, devemos empacotar todos os itens no menor número possível de recipientes. Nesta tese, desenvolvemos algoritmos e heurísticas para algumas variações e generalizações do BPP. Para o problema do empacotamento colorido, uma generalização do BPP na qual cada item também possui uma cor, e, em cada recipiente, os itens são empacotados em uma ordem de forma que as cores são alternadas, propomos quatro modelos matemáticos. Dois deles são baseados na formulação pseudo-polinomial de fluxo em arcos de Valério de Carvalho, e os outros dois são modelos exponenciais de particionamento de conjuntos, resolvidos por um algoritmo de branch-cut-and-price usando o VRPSolver. Para o problema do empacotamento com cenários, uma generalização do BPP que considera a presença de cenários incertos, propomos vários algoritmos: dois algoritmos de aproximação, um algoritmo exato de branch-and-price com dual feasible functions, e uma meta-heurística de busca em vizinhança variável. Por fim, propomos um leilão para Smart Grids. Especificamente, consideramos um problema em que um consumidor deve calcular um lance para um dado plano de uso de energia de acordo com suas preferências de uso, e um problema em que o provedor de energia deve acomodar os planos de uso de energia dos consumidores restrito à capacidade de geração de energia. Ambos os problemas são modelados como variações diferentes de um problema de empacotamento multidimensional e são resolvidos com um modelo de programação linear inteira mista.
Banca examinadora
Titulares:
| Rafael Crivellari Saliba Schouery | IC/UNICAMP |
| Reinaldo Morabito Neto | CCET/UFSCar |
| Edilson Fernandes de Arruda | University of Southampton |
| Kelly Cristina Poldi | IMECC/UNICAMP |
| Mário César San Felice | DC/UFSCar |
Suplentes:
| Guilherme Pimentel Telles | IC/UNICAMP |
| Pedro Augusto Munari Junior | CCET/UFSCar |
| Vinicius Fernandes dos Santos | ICEx/UFMG |