Um Algoritmo de Branch-and-Bound Combinatório para o Problema do Empacotamento

• Processo: 23/17964-4
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de julho de 2024
• Situação: Interrompido
• Á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
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Vinculado ao auxílio: 22/05803-3 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento e localização e suas integrações em contextos industriais e logísticos, AP.TEM
• Bolsa(s) vinculada(s): 24/17437-7 - Técnicas Combinatórias de Fixação de Variáveis e Limites Inferiores para o Problema de Empacotamento, BE.EP.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

Problemas de Corte e Empacotamento são fundamentais na manufatura e na logística. Estes problemas visam minimizar desperdícios, influenciando diretamente na eficiência operacional. O Problema de Corte de Estoque (CSP, do inglês: Cutting Stock Problem) otimiza o corte de materiais, enquanto o Problema do Empacotamento (BPP, do inglês: Bin Packing Problem) se concentra no empacotamento eficiente de itens. Dadas as suas altas aplicações práticas na indústria e complexidades computacionais intrínsecas, estes problemas estão sendo amplamente estudados na literatura desde a década de 1960. Os avanços na literatura dos algoritmos para o BPP nas últimas duas décadas foram todos utilizando Programação Linear (Inteira), técnica esta que depende essencialmente do bom desempenho dos solucionadores programação linear de propósito geral. O acesso a tais solucionadores pode inibir ou inviabilizar o uso de tais algoritmos para alguns usuários, uma vez que essas ferramentas possuem licenças caras. Neste projeto, desenvolveremos um algoritmo branch-and-bound combinatório (CBB, do inglês: Combinatorial Branch-and-Bound) para o BPP, ou seja, um algoritmo branch-and-bound que não utiliza programação linear. Ademais, além deste CBB ser uma contribuição acadêmica para a literatura em um aspecto pouco explorado recentemente, esta será uma ferramenta autônoma de código aberto para resolver tanto o BPP e o CSP, como outros problemas relacionados.