Otimização Linear e Inteira com Python e PuLP

Neste artigo, vamos discutir sobre dois modelos comuns em Pesquisa Operacional (PO) e como usar o PuLP, um pacote do Python, para resolver um problema aplicado.

Figura 1: Foto Dan Gold em Unsplash

Vamos supor que você esteja gerenciando o plano alimentar do almoço de uma escola. Seu trabalho é garantir que os alunos tenham o balanceamento nutricional adequado para cada alimento escolhido.

Podemos considerar a situação como um problema de tomada de decisão que envolve a resposta a três perguntas:

1. Quais são as alternativas de decisão? As variáveis que temos que determinar.
2. Sob quais restrições a decisão é tomada?
3. Qual seria o critério de decisão objetivo para avaliar as alternativas?

Cada alternativa corresponde a um tipo de alimento que está disponível para compra pela escola.

No entanto, existem restrições em termos do orçamento disponível e da variedade de alimentos que precisam estar na dieta para torná-la adequada. Ou seja, devem ser consideradas as restrições em calorias totais, mas também em cada componente nutricional, por exemplo, colesterol, vitamina A, cálcio, etc.

Um critério de objetivo para avaliar as alternativas propostas é o custo do almoço. A alternativa de menor custo é a melhor. A função que define o objetivo que queremos otimizar (minimizar ou maximizar) é chamada, obviamente, de função objetivo.

Com base nessa estrutura, o modelo geral de Pesquisa Operacional pode ser organizado no seguinte formato (Figura 1):

Figura 2: Estrutura padrão de um modelo de otimização

Uma solução do modelo é viável se garantir todas as restrições e é ótima se, além de viável, resultar no melhor valor possível (seja máximo ou mínimo) para a função objetivo.

O tipo mais comum de aplicação envolve o problema de distribuir recursos limitados, entre necessidades que competem por aqueles recursos, da melhor forma possível. Exemplos de soluções que os métodos de Pesquisa Operacional resolvem são: roteamento de veículos, alocação de tarefas, gestão de estoques, dimensionamento de lotes e alocação de investimentos. Além disso, os métodos de Pesquisa Operacional também são usados para solucionar problemas de machine learning.

Na Porto Seguro, os métodos de otimização são usados, sobretudo, para dar suporte às nossas operações de guincho e serviços domiciliares, bem como na otimização de carteira de investimentos e no dimensionamento de equipes.

Formulando o problema de otimização usando a biblioteca PuLP do Python

Primeiramente, começaremos importando as bibliotecas necessárias. Caso não tenha o Pandas e o PuLP instalados, use o comando pip install nome_do_pacote no terminal de comandos para instalar.

Primeiro, nós criamos o problema de LP com o método LpProblem do PuLP.

As tabelas a seguir mostram, em detalhes, o valor nutricional completo de cada item alimentar e sua ingestão diária máxima / mínima.

Figura 3: Primeiras linhas do dataframe com as informações nutricionais por item

['Frozen Broccoli' 'Frozen Corn' 'Raw Lettuce Iceberg' 'Tofu'
 'Baked Potatoes' 'Roasted Chicken' 'Spaghetti W/ Sauce' 
 'Raw Apple' 'Banana' 'Wheat Bread' 'White Bread' 'Apple Pie'
 'Oatmeal Cookies' 'Scrambled Eggs' 'Turkey Bologna' 
 'Beef Frankfurter' 'Chocolate Chip Cookies']

Figura 4: Dataframe com as informações de limites inferiores e superiores de nutrientes e minerais

Vamos criar uma lista com as variáveis. Esse passo não é obrigatório, mas facilita a construção das restrições.

Os algoritmos que resolvem esses tipos de problema buscam, na região delimitada pelas restrições, soluções viáveis para a função objetivo. Sem uma declaração específica sobre os limites, a solução pode ficar sem sentido. O algoritmo pode alocar quantidades negativas sobre as quantidades de alimentos para reduzir o custo total, enquanto busca conformidade com as restrições.

Figura 5: Busca no espaço de soluções da região viável (linha vermelha da intersecção)

Diante disso, vamos criar um dicionário com as variáveis dos itens de comida com limite inferior igual a zero e tipo categórico. Com isso, a solução ótima pode tomar qualquer número real maior ou igual a zero.

{'Frozen Broccoli': 13.6, 'Frozen Corn': 17.1, 'Raw Lettuce   Iceberg': 0.4, 'Baked Potatoes': 39.9, 'Tofu': 2.2, 'Roasted Chicken': 0.0, 'Spaghetti W/ Sauce': 58.3, 'Raw Apple': 21.0, 'Banana': 26.7, 'Wheat Bread': 12.4, 'White Bread': 11.8, 'Oatmeal Cookies': 12.4, 'Apple Pie': 9.6, 'Scrambled Eggs': 1.3, 'Turkey Bologna': 0.3, 'Beef Frankfurter': 0.8, 'Chocolate Chip Cookies': 9.3}

Para a construção do problema de otimização, iniciamos adicionando uma função objetivo. Perceba que o método usado é o lpSum. A função objetivo nada mais é que o somatório do custo unitário pela unidade métrica correspondente de cada uma das alternativas de decisão.

Agora podemos adicionar as restrições. Não foram adicionadas todas as possíveis restrições para simplificar o problema e garantir sua viabilidade. Caso tenha curiosidade, mude as restrições e/ou adicione e veja como isso impacta a função objetivo.

Solucionando o problema e mostrando a solução

PuLP tem algumas opções de solvers (por exemplo o COIN_MP, Gurobi, CPLEX, etc.). Para este problema, deixamos o solver default, o CBC.

'Optimal'

A solução completa contém todas as variáveis, incluindo aquelas para as quais foram atribuídas valor zero. Para nós, apenas as variáveis diferentes de zero são importantes.

Food_Baked_Potatoes = 0.7539
Food_Frozen_Broccoli = 6.7750
Food_Roasted_Chicken = 0.0692
Food_Scrambled_Eggs = 5.9839

Finalmente, nós podemos mostrar o valor da função objetivo.

O custo total para uma dieta balanceada é: $5.54

Como lidar com números inteiros

O algoritmo usado para a otimização anterior é uma programação linear simples, onde as variáveis podem assumir qualquer número real. Programação inteira força as variáveis a assumirem apenas valores inteiros.

Otimização linear inteira é um problema computacional mais difícil que a otimização linear. Variáveis inteiras fazem o problema de otimização não-convexo, tornando-o mais difícil de resolver. Memória e tempo de solução podem crescer exponencialmente com a adição de mais variáveis inteiras.

Felizmente, PuLP pode solucionar um problema de otimização com esse tipo de restrição também. O código é quase idêntico ao anterior, então não vamos repeti-lo. A única diferença é que as variáveis são definidas previamente como Integer ao invés de Continuos.

Como incorporar decisões binárias em programação linear

Frequentemente, nós precisamos incluir algum tipo de ‘If-then-else” para acrescentar uma lógica de decisão ao problema de otimização.

Por exemplo, se nós quisermos que apenas brocólis ou alface seja incluído na dieta. Como incluiremos isso no processo?

Para lidar com isso, usamos uma lógica com variáveis binárias. Podemos indicar a variável binária food_chosen alocando limite inferior e superior como 0 e 1, respectivamente, numa variável inteira.

Para incorporar a condição brócolis ou alface, adicionamos apenas o código abaixo.

Isso garante que a soma dessas duas variáveis deve ser no máximo 1, o que significa que apenas uma das duas pode ser incluída na solução ótima.

Considerações finais

A solução do modelo pode apoiar o processo de tomada de decisão de uma instituição real, mas vale salientar que, na decisão, outros diversos fatores não tão determinísticos, não quantificáveis, precisam ser levados em consideração (por exemplo, a preferência alimentar dos alunos). Soluções que não levem em consideração o comportamento humano podem falhar.

Você pode fazer download do notebook com todo o código e a base de dados no Github do Tirthajyoti Sarkar.

Agradecimentos

JoaoGuilherme Araujo pela colaboração e revisão.

Bibliografia

ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H. Pesquisa operacional para cursos de engenharia, Editora Elsevier, São Paulo, 2015.

TAHA, H. A. Introdução a pesquisa operacional, Editora Pearson, São Paulo, 2015.