O problema da mochila compartimenta é uma variação do clássico problema da mochila. As mochilas compartimentadas surgem quando itens são agrupados de acordo com uma necessidade ou característica específica, dessa forma, ao preencher uma mochila itens de agrupamentos diferentes não podem ser misturados. Para resolver este problema, criam-se compartimentos que serão preenchidos por itens de um único agrupamento. O problema da mochila compartimentada consiste na determinação da quantidade de compartimentos, do tamanho de cada compartimento e da forma de preenchê-los, buscando maximizar o valor de utilidade da mochila. A mochila compartimentada pode ainda ser sub-dividida em duas classes, as irrestritas e as restritas. Neste trabalho é apresentada uma proposta de resolução do problema da mochila compartimentada restrita por meio de uma decomposição.

Em ambiente Linux, rodando sob o kernel 2.6.11, utilizando o compilador g++ versão 3.3, realizando a linkagem com a Glib 2.2, implementamos a heurística do melhor compartimento para W-capacidades diferentes, que até o momento era a que fornecia o melhor resultado computacional, e a estratégia de decomposição.Todas as implementações foram realizadas com o auxílio das bibliotecas presentes no solver Xpress, cedido pela Dash Optimization. Os dados das simulações foram gerados uniformemente em três categorias, que delimitavam o intervalo onde poderiam ser gerados os valores de peso e utilidade de cada item. Foram geradas mochilas com 5,10,20 e 50 agrupamentos. Para cada valor de agrupamento foram construídos exemplos com 5,10,20 e 50 itens. Para a heurística do melhor compartimento para w-capacidades, os valores de w foram: 5 ,10,25 e 50. Foram resolvidas um total de 1440 mochilas , permitindo dessa forma calcular a diferença entre as soluções fornecidas pelas heurísticas.

Como esperado as soluções fornecidas pela decomposição foram sempre melhores que as soluções fornecidas pela heurística do melhor compartimento para W-Capacidades diferentes. A gap das soluções diminiu com o aumento do número de itens e de compartimentos. A maior diferença observada é de cerca de 20,920 % e ocorreu quando foram simuladas mochilas com 5 agrupamentos e 50 itens. A menor diferença ocorreu com os exemplos de 50 agrupamentos e 10 itens e foi de cerca de 0,0011%. Em ambos os casos os itens foram gerados de acordo com o intervalo da primeira categoria. Os gaps de solução foram semelhantes nas três categorias.

Pelo que podemos observar, a heurística de w-capacidades apresenta um desempenho ruim para mochilas com um número pequeno de agrupamentos e de itens, que melhora sensivelmente à medida que estas entradas aumentam. Aparentemente, a qualidade das soluções não apresenta melhoria significativa crescendo w de 25 para 50, indicando que o aumento excessivo de w não é recomendável. A heurística de decomposição parece ser uma alternativa razoável para compartimentações restritas e, em casos onde o problema é intratável, o uso de geração de colunas pode ser uma abordagem promissora.