Problema de atribuição quadrática com Pyomo em Python

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/

Leave a Reply

Deixe um comentário

O seu endereço de e-mail não será publicado.

Esse site utiliza o Akismet para reduzir spam. Aprenda como seus dados de comentários são processados.

Close

Meta