Problemas da mochila compartimentada: casos unidimensional e bidimensional

Resumo

O Problema da Mochila Compartimentada é uma extensão do Problema da Mochila, em que os itens solicitados são divididos em classes, de modo que a mochila deve ser subdividida em compartimentos, os quais têm capacidades limitadas e são carregados com itens de mesma classe. Além disso, a construção de um compartimento tem um custo fixo e ocasiona uma perda no espaço da mochila. O objetivo consiste em maximizar a soma dos valores dos itens, descontado o custo fixo de inclusão de compartimentos. Uma aplicação da Mochila Compartimentada surge em problemas de corte com vários estágios, nos quais os objetos em estoque devem ser cortados em objetos intermediários até a obtenção dos itens finais. Na literatura, o caso unidimensional deste problema foi aplicado em problemas de corte, em que bobinas de aço sujeito à laminação devem ser cortadas para obtenção de fitas, e no corte de bobinas de papel, em que dois estágios distintos de corte ocorrem. O problema foi modelado como otimização não linear inteira e métodos heurísticos foram propostos. Neste projeto buscamos desenvolver um método exato tipo branch-and-price para o Problema da Mochila Compartimentada Unidimensional. Pretende-se também estender esta abordagem na geração de padrões de corte para o caso bidimensional, visto que surgem naturalmente na prática, pelas mesmas razões que o caso unidimensional, ou seja, corte em vários estágios. (AU)