Ao formalizar problemas de LP, muitas vezes é necessário lidar com variáveis de múltiplos índices. Ao trabalhar com problemas de grandes dimensões, isso é, francamente, uma coisa comum.
As inter-relações de tais variáveis de múltiplos índices na função objetivo (a forma linear também é um critério de otimização linear) e as restrições (na forma de igualdades e desigualdades lineares) devem ser geradas programaticamente. Ao trabalhar com PuLP (porta de biblioteca LP para Python), existem duas abordagens principais para essa geração:
- Gerando matriz A (matriz de restrição) com geradores de lista Python explicitamente. Por exemplo, assim: Problema de Sudoku
- Geração de variáveis simbólicas com ligação a índices através de dicionários de forma implícita. Isso pode ser feito manualmente por meio de um dicionário ou usando um plugin PuLP
O problema LP clássico de quase qualquer dimensão pode ser facilmente formalizado de qualquer uma dessas maneiras, mas ao desenvolver novas estruturas de restrições (especialmente quando a lógica de inter-relações de variáveis se torna mais complicada, novas variáveis de significado aparecem, alguns índices são abandonados ou novos índices são introduzidos) agregação / decomposição de grupos de variáveis, etc.) requer fácil rastreamento de variáveis de múltiplos índices no próprio código Python, que está diretamente ausente nas abordagens acima.
Para resolver este problema, propõe-se a utilização do add -on PuLP-MiA (link para o repositório com uma breve descrição da funcionalidade).
O autor está longe de pensar que esta seja uma solução para todos os problemas que surgem na formalização e solução de problemas de PL com uma estrutura complexa de restrições, porém, em muitos anos de prática (principalmente quando a modificação ocorre com longos intervalos de tempo), a abordagem tem se mostrado bem, principalmente pelas seguintes conveniências:
- A criação / vinculação a variáveis existentes acontece automaticamente
- Associação explícita de um nome de variável e seus índices
- Nome da variável - string arbitrária
- Índices - valores numéricos
- O número de índices é condicionalmente ilimitado (pode não haver nenhum índice)
- Os resultados da solução do problema de LP são exibidos na forma de um dicionário, onde as chaves são variáveis de múltiplos índices diferentes de zero (o comportamento pode ser alterado)
Talvez o addon seja muito útil para alguém em uma pesquisa de operações de longo prazo. Licença do MIT. É instalado tradicionalmente via pip .
PS Para quem acabou de ler, ainda será pequeno
exemplo de formação de uma série de restrições))
from itertools import product
from pulp_mia import Task, Constraint
i_set = list(range(5))
j_set = list(range(5))
m_set = list(range(2))
g_set = list(range(4))
s_set = list(range(5))
k_set = list(range(5))
task = Task(debug=True)
for i, m, g, s, k in product(i_set, m_set, g_set, s_set, k_set):
a_new = Constraint('<=')
for j in j_set:
a_new.setCoeff(('x', i, j, m, g, s, k), 1)
a_new.setBValue(1)
task.addConstraint(a_new)
print(task)
#TASK info:
# NAME: test-task
# SIZE: 5000 x 1000
(para o resto, veja a breve descrição do addon )
PPS sim, em algum lugar nas profundezas do capô existe um dicionário comum.