Busca avançada
Ano de início
Entree

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

Processo: 19/12728-5
Linha de fomento:Auxílio à Pesquisa - Pesquisador Visitante - Internacional
Vigência: 09 de fevereiro de 2020 - 22 de fevereiro de 2020
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Flávio Keidi Miyazawa
Beneficiário:Flávio Keidi Miyazawa
Pesquisador visitante: Manuel Iori
Inst. do pesquisador visitante: Università degli Studi di Modena e Reggio Emilia, Reggio Emilia (UNIMORE), Itália
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Vinculado ao auxílio:15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural, AP.TEM
Assunto(s):Otimização combinatória  Otimização  Problemas de corte e empacotamento  Intercâmbio de pesquisadores 

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)