Otimização de Mochilas Múltiplas com Afinidades de Alocação.
Neste artigo apresento uma extensão contextual do Problema de Mochilas Múltiplas (MKP), incorporando restrições ambientais de temperatura e umidade em um modelo MILP implementado com Google OR-Tools e SCIP.
O Multiple Knapsack Problem (MKP) é um dos problemas clássicos da otimização combinatória, utilizado para modelar cenários em que múltiplos recipientes com capacidade limitada precisam acomodar itens com diferentes pesos e valores. Em sua formulação tradicional, o problema considera apenas o lucro associado a cada item e as restrições de capacidade de cada recipiente.
No entanto, o que acontece quando os itens não podem ser alocados em qualquer recipiente devido a condições climáticas ou operacionais? Os problemas de alocação do mundo real frequentemente exigem mecanismos de atribuição que levem em conta a compatibilidade entre o item e o local em que ele será armazenado.
Neste trabalho, apresento uma extensão prática do MKP que incorpora afinidades item–mochila. Nessa abordagem, restrições qualitativas associadas tanto ao produto quanto ao recipiente são convertidas em critérios quantitativos. A partir dessa transformação, cconstrói-se uma função de afinidade contextual capaz de quantificar a compatibilidade entre item e recipiente.
Em vez de apenas maximizar valor, este modelo maximiza adequação contextual, aproximando a otimização matemática do comportamento humano real em tarefas de empacotamento.
Para ilustrar a aplicação, utilizaremos o cenário de compras de supermercado, onde diferentes produtos devem ser distribuídos em sacolas de transporte. Nesse cenário, sacolas térmicas são mais adequadas para itens como frangos congelados e sorvetes, enquanto sacolas de papel são menos apropriadas para produtos pesados ou úmidos. Esse exemplo permite demonstrar como características ambientais e físicas podem influenciar diretamente a qualidade da alocação.
O problema é formulado como um Mixed-Integer Linear Program (MILP) utilizando Google OR-Tools em Python, com resolução via solver SCIP. O objetivo consiste em maximizar o valor contextual das alocações, respeitando restrições de capacidade física e compatibilidade ambiental.
Definição do problema
No cenário hipotético considerado, utilizam-se quatro tipos de sacolas de supermercado: térmica, de papel, de plástico e de tecido. Cada uma delas possui uma capacidade máxima de peso e apresenta diferentes níveis de afinidade em relação às condições de umidade e temperatura dos itens transportados.
A tabela a seguir descreve as sacolas disponíveis:
| ID | Tipo | Capacidade (kg) | Temperaturas Compatíveis | Umidade Compatível | Observações |
|---|---|---|---|---|---|
| B1 | Térmica | 10 | Frio, Fresco, Muito Frio | Úmido | Ideal para itens refrigerados |
| B2 | Tecido | 8 | Fresco, Ambiente | Seco | Respirável, não impermeável |
| B3 | Plástico | 6 | Ambiente, Fresco | Seco, Úmido | Proteção contra líquidos |
| B4 | Papel | 5 | Ambiente | Seco | Inadequado para umidade |
Os itens considerados no exemplo representam produtos com diferentes requisitos ambientais, pesos e valores econômicos. Produtos refrigerados, como frango congelado e sorvete, exigem compatibilidade térmica, enquanto itens secos demandam ambientes com baixa umidade.
A tabela a seguir descrevem os itens utilizados no experimento computacional:
| ID | Nome | Peso (kg) | Valor | Tipo de Armazenamento | Temperatura | Umidade |
|---|---|---|---|---|---|---|
| I1 | Frango Congelado | 3.0 | 25.00 | Refrigerado | Frio | Úmido |
| I2 | Arroz | 2.0 | 12.00 | Seco | Ambiente | Seco |
| I3 | Sabonete Líquido | 1.5 | 9.50 | Líquido | Ambiente | Úmido |
| I4 | Livro | 1.0 | 22.00 | Seco | Ambiente | Seco |
| I5 | Sorvete | 2.5 | 18.00 | Congelado | Muito Frio | Úmido |
| I6 | Tomate | 2.0 | 7.00 | Fresco | Fresco | Úmido |
| I7 | Panetone | 3.0 | 20.00 | Seco | Ambiente | Seco |
| I8 | Shampoo | 1.2 | 15.00 | Líquido | Ambiente | Úmido |
Matriz de Afinidade
Para cada par item–sacola, calcula-se um valor contextual $v_{ib}$ com base na afinidade de temperatura, afinidade de umidade e valor econômico do item.
Diferentemente do Multiple Knapsack Problem tradicional, em que o valor depende apenas do item:
- MKP Tradicional
- Modelo Proposto
No modelo proposto, o valor passa a depender simultaneamente do item $i$ e da sacola $b$, introduzindo dependência contextual na função objetivo.
\[v_{ib} = \frac{ Score^{temp}_{ib} + Score^{hum}_{ib} + Value_i^{norm} }{3}\]Exemplo de cálculo
Para o item I1 (Frango Congelado) e a sacola B1 (Térmica):
| Critério | Score |
|---|---|
| Temperatura compatível | 1 |
| Umidade compatível | 1 |
| Valor normalizado | $25/25 = 1$ |
Score final:
\[\frac{1 + 1 + 1}{3} = 1.0\]A matriz de compatibilidade foi construída utilizando restrições ambientais de umidade, evitando, por exemplo, a alocação de produtos úmidos em sacolas de papel.
O principal diferencial do modelo está na transformação de regras qualitativas em coeficientes quantitativos utilizados diretamente pela função objetivo do problema de otimização.
Na implementação em Python, os scores são armazenados na estrutura values[(item, bag)] e utilizados posteriormente na formulação matemática do MILP.
Otimização
O problema é formulado como um programa linear inteiro binário, no qual cada variável de decisão representa a atribuição de um item a uma sacola.
Natureza do Modelo
O modelo proposto caracteriza-se como uma extensão contextual do Multiple Knapsack Problem clássico, uma vez que o valor do item deixa de ser fixo e passa a depender da combinação item–sacola.
Índices
$i = 1, \dots, m$: itens
$b = 1, \dots, n$: sacola
Parâmetros
$w_i$: peso do item $i$
$v_{ib}$: valor contextual do item $i$ quando atribuído à sacola $b$
$c_b$: capacidade da sacola $b$
Variáveis de decisão
Variável binária:
\[x_{i,b} = \begin{cases} 1, & \text{se o item } i \text{ será designado a sacola } b \\ 0, & \text{caso contrário} \end{cases}\] \[x_{i,b} \in \{0,1\}, \quad \forall i = 1, \dots, m, \quad \forall b = 1, \dots, n\]Restrição de capacidade
A soma dos pesos atribuídos a cada sacola não pode ultrapassar sua capacidade máxima.
\[\sum_{i=1}^{m} w_i x_{ib} \leq c_b \quad \forall b=1, \dots,n\]Restrição de atribuição única
Cada item pode ser atribuído a, no máximo, uma sacola:
\[\sum_{b=1}^{n} x_{ib} \leq 1 \quad \forall i = 1, \dots, m\]Restrição de compatibilidade
Essa restrição impede que itens sejam atribuídos a sacolas incompatíveis ambientalmente.
\[Compatibility_{i,b} = \begin{cases} 1, & \text{ se o item } i \text{ é compatível com a sacola } b \\ 0, & \text{ se o item } i \text{ não é compatível com a sacola } b \end{cases}\] \[Compatibility_{i,b} \in \{0,1\}, \quad \forall i = 1, \dots, m, \quad \forall b = 1, \dots, n\] \[x_{ib} \leq Compatibility_{ib}\]Quando $Compatibility_{ib} = 0$, a variável de decisão $x_{ib}$ é forçada a assumir valor zero.
Função Objetivo
Maximizar o valor total dos itens atribuídos às sacolas:
\[\max Z = \sum_{i=1}^{m} \sum_{b=1}^{n} v_{ib} x_{ib}\]Dessa forma, o modelo busca simultaneamente maximizar adequação contextual e respeitar restrições físicas e ambientais de alocação.
Implementação no Python
A implementação foi desenvolvida em Python utilizando Google OR-Tools com o solver SCIP para modelagem e resolução do problema de otimização.
O trecho abaixo apresenta o núcleo da formulação MILP, incluindo:
- criação das variáveis binárias de decisão;
- restrições de capacidade;
- restrições de atribuição única;
- restrições de compatibilidade ambiental;
- definição da função objetivo;
- resolução do modelo.
A etapa de pré-processamento responsável pela construção da matriz de afinidade contextual foi apresentada anteriormente.
Resultado Final
O modelo prioriza a maximização da afinidade contextual entre item e sacola, não necessariamente a ocupação ótima da capacidade física. Isso evidencia a natureza da função objetivo baseada em score de compatibilidade ambiental.
Além disso, o valor total obtido não deve ser interpretado como valor monetário absoluto, mas sim como a soma dos scores contextualizados de afinidade entre itens e sacolas.
Alocação das Sacolas
Sacola Térmica (B1)
Capacidade: 10 kg | Ocupado: 7.5 kg (75%)
- Frango congelado (3.0 kg) - Score: 1.000
- Sorvete (2.5 kg) - Score: 0.907
- Tomate (2.0 kg) - Score: 0.760
Sacola de Plástico (B3)
Capacidade: 6 kg | Ocupado: 2.7 kg (45%)
- Sabonete Líquido (1.5 kg) - Score: 0.793
- Shampoo (1.2 kg) - Score: 0.867
Sacola de Tecido (B2)
Capacidade: 8 kg | Ocupado: 6.0 kg (75%)
- Arroz (2.0 kg) - Score: 0.827
- Livro (1.0 kg) - Score: 0.960
- Panetone (3.0 kg) - Score: 0.933
Score Total
\[Z = 7.047\]Diferentemente do Multiple Knapsack Problem tradicional, no qual o valor do item é fixo, o modelo proposto introduz uma dependência contextual da atribuição item–sacola. Dessa forma, o valor associado ao item passa a variar conforme as características ambientais da sacola utilizada.
Podemos observar também que o modelo não necessariamente utiliza todas as sacolas disponíveis, uma vez que a formulação atual não impõe restrições ou incentivos de utilização mínima. Assim, a solução final reflete exclusivamente a maximização do valor marginal contextual definido pela função objetivo.
Código-Fonte
O código completo em Python, incluindo a construção da matriz de afinidade e a modelagem matemática no Google OR-Tools, está disponível no repositório abaixo:
Multi-Knapsack Optimization with Preference-Based Item Assignment
Referências
Google OR-Tools - Assignment with Task Sizes
[link]Google OR-Tools - Linear Optimization and Knapsack Examples
[link]Kellerer, H.; Pferschy, U.; Pisinger, D.
Knapsack Problems. Springer, 2004.Martello, S.; Toth, P.
Knapsack Problems: Algorithms and Computer Implementations. Wiley, 1990.