Não importa se é a atribuição de departamentos para salas vazias em um prédio, máquinas para células de manufatura, fábricas para regiões geográficas, produtos para racks em um armazém, sensores para dispositivos, computadores de borda dentro da rede da internet das coisas, estações de transporte público para diferentes zonas em uma cidade, pode ser necessário modelar e resolver um problema de atribuição quadrática (também conhecido como QAP). O termo Quadrático vem do fato de que as variáveis de atribuição são multiplicadas entre si (na função objetivo) para considerar o efeito simultâneo de atribuir duas facilidades a duas posições diferentes. O objetivo é fornecer interações mútuas eficientes entre instalações dentro de um sistema. Este artigo apresenta e analisa um modelo QAP simples com Pyomo em Python
Modelando e resolvendo problemas de atribuição quadrática em Python
Aqui, codifico o problema de decisão de acordo com as seguintes suposições:
As instalações (cessionários):
- São estáticos.
- Necessidade de comunicar (interagir) uns com os outros.
- Pode ser atribuído a apenas uma única sala, célula de fabricação,
- região geográfica, etc. (em geral, uma posição).
- Ter um volume de interação específico entre si.
Os cargos (atribuições):
- São ocupados por uma instalação
- Têm uma distância específica (semelhança) um do outro.
As relações cessionário-atribuição:
- São um a um.
Em resumo, o objetivo é fazer instalações com maior interação posicionadas mais próximas umas das outras.
import pyomo.environ as op
import itertools as it
import os
#Developer: @KeivanTafakkori, 4 April 2022
def model(I,J,a,dispmodel="y",solve="y", dispresult="y"):
m = op.ConcreteModel("QuadraticAssignmentProblem")
m.I = op.Set(initialize=I)
m.J = op.Set(initialize=J)
m.K = op.SetOf(m.I)
m.L = op.SetOf(m.J)
m.x = op.Var(m.I,m.J, domain=op.Binary)
objs = {0: sum(a[(i,j,k,l)]*m.x[i,j]*m.x[k,l] for i,j,k,l in it.product(m.I,m.J,m.K,m.L))}
cons = {0: {j: (sum(m.x[i,j] for i in m.I) == 1) for j in m.J},
1: {i: (sum(m.x[i,j] for j in m.J) == 1) for i in m.I}}
m.OBJ = op.Objective(expr=objs[0],sense=op.minimize)
m.constraint = op.ConstraintList()
for keys1 in cons:
for keys2 in cons[keys1]: m.constraint.add(expr=cons[keys1][keys2])
if dispmodel=="y":
print("Model --- \n",m)
if solve == "y":
os.environ['NEOS_EMAIL'] = 'myemail@email.com'
solver_manager = op.SolverManagerFactory('neos')
results = solver_manager.solve(m, solver = "bonmin")
if dispresult == "y":
print(results)
op.display(m)
return m
Notavelmente, eu uso o solucionador bonmin fornecido online pelo servidor NEOS, uma plataforma de nuvem gratuita para resolver problemas de otimização desafiadores. Portanto, para ver os resultados
da implementação, certifique-se de ter uma conexão de internet confiável. O servidor exige que você insira seu endereço de e-mail. Para implementar o modelo codificado, em primeiro lugar, precisamos de dados, que são fornecidos da seguinte forma:
w = [[0,3,0,2],
[3,0,0,1], #Matriz de fluxo (entre responsáveis)
[0,0,0,4],
[2,1,4,0]]
d = [[0,22,53,53],
[22,0,40,62], #Matriz de distância (entre tarefas)
[53,40,0,55],
[53,62,55,0]]
I = range(len(w)) #Conjunto de cessionários
K = I
J = range(len(w[0])) #Conjunto de tarefas
L = J
a ={(i,j,k,l): w[i][k]*d[j][l] for i,j,k,l in it.product(I,J,K,L)} #Relative cost matrix
Então, eu modelo e resolvo o QAP da seguinte forma:
m = model(I,J,a) #Modele e resolva o problema
Felizmente, o status é ótimo e obtenho os seguintes resultados:
Model QuadraticAssignmentProblem
Variables:
x : Size=16, Index=x_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
(0, 0) : 0 : 0.0 : 1 : False : False : Binary
(0, 1) : 0 : 0.0 : 1 : False : False : Binary
(0, 2) : 0 : 1.0 : 1 : False : False : Binary
(0, 3) : 0 : 0.0 : 1 : False : False : Binary
(1, 0) : 0 : 0.0 : 1 : False : False : Binary
(1, 1) : 0 : 0.0 : 1 : False : False : Binary
(1, 2) : 0 : 0.0 : 1 : False : False : Binary
(1, 3) : 0 : 1.0 : 1 : False : False : Binary
(2, 0) : 0 : 1.0 : 1 : False : False : Binary
(2, 1) : 0 : 0.0 : 1 : False : False : Binary
(2, 2) : 0 : 0.0 : 1 : False : False : Binary
(2, 3) : 0 : 0.0 : 1 : False : False : Binary
(3, 0) : 0 : 0.0 : 1 : False : False : Binary
(3, 1) : 0 : 1.0 : 1 : False : False : Binary
(3, 2) : 0 : 0.0 : 1 : False : False : Binary
(3, 3) : 0 : 0.0 : 1 : False : False : Binary
Objectives:
OBJ : Size=1, Index=None, Active=True
Key : Active : Value
None : True : 790.0
Constraints:
constraint : Size=8
Key : Lower : Body : Upper
1 : 1.0 : 1.0 : 1.0
2 : 1.0 : 1.0 : 1.0
3 : 1.0 : 1.0 : 1.0
4 : 1.0 : 1.0 : 1.0
5 : 1.0 : 1.0 : 1.0
6 : 1.0 : 1.0 : 1.0
7 : 1.0 : 1.0 : 1.0
8 : 1.0 : 1.0 : 1.0
Os resultados mostram que deve-se atribuir as facilidades 1,2,3 e 4 às posições 3,4,1 e 2, respectivamente.
Observações finais
Neste artigo, resolvi um problema simples de atribuição quadrática (QAP) via Pyomo, uma interface para otimização em Python, usando um solver chamado BONMIN através do servidor NEOS. A resolução de tais problemas de otimização requer o uso de algoritmos de otimização robustos e rápidos. Os leitores interessados podem consultar os artigos anteriores para saber mais sobre solucionadores e interfaces.
Além disso, visitando os artigos anteriores, você pode descobrir que outros problemas de otimização, como programação e precificação de máquina única e flow shop, podem ser resolvidos de maneira semelhante aos problemas de atribuição quadrática em Python. Por fim, uma implementação do QAP proposto com o conjunto de dados utilizado é fornecida pelo NEOS, que pode ser acessada neste link.
Se este artigo for usado em pesquisa ou outros métodos de publicação, você pode citá-lo como Tafakkori (2022) (no texto) e se referir a ele da seguinte forma: Tafakkori, K. (2022). Problema de atribuição quadrática com Pyomo em Python. Análise de Dados da Cadeia de Suprimentos. URL:
https://www.supplychaindataanalytics.com/quadratic-assignment-problem-with-pyomo-in-python/
Engenheiro industrial com foco no aproveitamento de métodos de otimização e tecnologias de inteligência artificial usando várias linguagens de programação para capacitar uma empresa a atingir seus objetivos!
Leave a Reply