Técnicas Combinatórias de Fixação de Variáveis e Limites Inferiores para o Problema de Empacotamento

• Processo: 24/17437-7
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Mestrado
• Data de Início da vigência: 03 de fevereiro de 2025
• Data de Término da vigência: 02 de agosto de 2025
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Rafael Crivellari Saliba Schouery
• Beneficiário: Renan Fernando Franco da Silva
• Supervisor: Manuel Iori
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Instituição Anfitriã: Università degli Studi di Modena e Reggio Emilia, Modena (UNIMORE), Itália
• Vinculado à bolsa: 23/17964-4 - Um Algoritmo de Branch-and-Bound Combinatório para o Problema do Empacotamento, BP.MS
• Assunto(s): Otimização combinatória
• Palavra(s)-Chave do Pesquisador: Algoritmo Exato | corte e empacotamento | Otimização Combinatória | Otimização Combinatória

Resumo

Os Problemas de Corte e Empacotamento são essenciais na manufatura e logística. Eles visam minimizar o desperdício, influenciando diretamente a eficiência operacional. O Problema de Corte de Estoque (CSP, do inglês: Cutting Stock Problem) otimiza o corte de materiais, enquanto o Problema de Empacotamento (BPP, do inglês: Bin Packing Problem) foca no empacotamento eficiente de itens. Dadas as suas altas aplicações práticas na indústria e as complexidades computacionais intrínsecas, eles têm sido amplamente estudados na literatura desde os anos 1960. O avanço dos algoritmos do BPP na literatura nas últimas duas décadas ocorreu com o uso da Programação Linear (Inteira), que essencialmente depende do bom desempenho de resolvedores de propósito geral para Programação Linear (PL). O acesso a esses resolvedores de PL pode inibir ou tornar o uso de tais algoritmos impraticável para alguns usuários, já que essas ferramentas possuem licenças caras. Este projeto estudará técnicas combinatórias de fixação de variáveis e limites inferiores para o BPP, apoiando o desenvolvimento de abordagens de branch-and-bound (B&B) que não dependam de resolvedores de PL. Além de fornecer uma contribuição acadêmica para uma área menos explorada em pesquisas recentes, essas técnicas serão integradas ao framework combinatório de B&B que está sendo desenvolvido no projeto de mestrado, o qual fornecerá uma ferramenta independente e de código aberto para resolver BPP, CSP e problemas relacionados.