Estudo de problemas de otimização combinatória teóricos e aplicados em cenários reais

Resumo

Estamos interessados em investigar problemas de otimização combinatória, tanto de maneira teórica como prática, voltados para aplicações reais. A principal linha a ser investigada é a dos problemas de empacotamento. No problema de empacotamento unidimensional, objetiva-se empacotar um conjunto de itens unidimensionais, cada um com dado peso, dentro de recipientes de dada capacidade. Os itens empacotados em um mesmo recipiente devem respeitar sua limitação de capacidade e o número de recipientes usados para empacotar todos os itens deve ser mínimo. O problema de empacotamento unidimensional foi bastante investigado na literatura e possui diversas aplicações, seja como problemas de corte e empacotamento, como em problemas de escalonamento de tarefas, alocação de processos, entre outras. Uma das formulações de programação linear inteira para o problema de empacotamento unidimensional é baseada na abordagem de cobertura por conjuntos. Uma conjectura atesta que a diferença entre o arredondamento do valor da relaxação linear desta formulação e uma solução ótima é no máximo 1. O Prof. Manuel Iori já obteve importantes resultados publicados para esta conjectura e esperamos investigar e obter novas propriedades relacionadas a esta conjectura. Também iremos investigar técnicas para gerar conjuntos de pontos de discretização para problemas de corte e empacotamento. Conjuntos de pontos de discretização são usadas nas formulações baseadas na discretização de possíveis posicionamentos dos itens em contêineres e também para subdividir o problema em subproblemas menores. Tais formulações são frequentemente utilizadas tanto para problemas de empacotamento unidimensional como nas versões de corte e empacotamento multidimensionais. O Prof. Iori possui atualmente as melhores estratégias de pontos discretização existentes na literatura e esperamos conseguir avançar nesta linha com esta cooperação. Por fim, o Prof. Iori possui diversos problemas de colaboração com indústrias e esperamos investigar pelo menos um destes problemas em colaboração.Manuel Iori e um pesquisador reconhecido internacionalmente e e especialista em vários metodos de resoluçãoo de problemas combinatórios. Manuel possui autoria do estado-da-arte para geração de malha de pontos para problemas de empacotamento, assim como o estado-da-arte para formulações para o problema de empacotamento em bins e problema de múltiplas mochilas. No entanto, o escopo de pesquisa de Manuel e diverso, envolvendo problemas de empacotamento, roteamento, escalonamento, problemas de teoria da computação, incluindo métodos exatos, heurísticos e algoritmos baseados em inteligência artificial. (AU)