Pyomo for quadratic assignment problem

No matter if it is the assignment of departments to empty rooms in a building, machines to manufacturing cells, factories to geographical regions, products to racks in a warehouse, sensors to devices, edge computers inside the internet of things network, public transport stations to different zones in a city, you may need to model and solve a quadratic assignment problem (also known as QAP). The term Quadratic comes from the fact that the assignment variables are multiplied together (in the objective function) to consider the simultaneous effect of assigning two facilities to two different positions. The objective is to provide efficient mutual interactions between facilities inside a system. This article presents and analyzes a simple QAP model with Pyomo in Python.

Modeling and solving quadratic assignment problem in Python

Herein, I code the decision problem according to the following assumptions:

The facilities (assignees):

  • Are static.
  • Need to communicate (interact) with each other.
  • Can be assigned to only a single room, manufacturing cell, geographical region, etc. (in general, a position).
  • Have a specific interaction volume between each other.

The positions (assignments):

  • Are occupied by one facility
  • Have a specific distance (similarity) from each other.

The assignee-assignment relations:

  • Are one-to-one.

In summary, the objective is to make facilities with higher interaction positioned closer to each other.

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

Notably, I use the bonmin solver provided online by the NEOS server, a free cloud platform for solving challenging optimization problems. Therefore, to see the implementation results, ensure you have a reliable internet connection. The server requires you to enter your email address. To implement the coded model, at first, we need data, which is given as follows:

w = [[0,3,0,2], 
     [3,0,0,1], #Flow matrix (between assignees)
     [0,0,0,4],
     [2,1,4,0]]

d = [[0,22,53,53],
     [22,0,40,62], #Distance matrix (between assignments)
     [53,40,0,55],
     [53,62,55,0]]

I = range(len(w)) #Set of assignees
K = I

J = range(len(w[0])) #Set of assignments
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

Then, I model and solve QAP as follows:

m = model(I,J,a) #Model and sovle the problem

Fortunately, the status is optimal and I obtain the following results:

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

The results show that one should assign facilities 1,2,3 and 4 to positions 3,4,1, and 2, respectively.

Concluding remarks

In this article, I solved a simple quadratic assignment problem (QAP) via Pyomo, an interface for optimization in Python, using a solver called BONMIN through the NEOS server. Solving such optimization problems necessitates using robust and fast optimization algorithms. The interested readers can refer to previous articles to know more about solvers and interfaces. Besides, by visiting previous articles, you can find that other optimization problems such as single machine and flow shop scheduling and pricing can be solved similar to quadratic assignment problems in Python. Finally, an implementation of the proposed QAP with the used dataset is provided by NEOS, which can be accessed using this link.

If this article is going to be used in research or other publishing methods, you can cite it as Tafakkori (2022) (in text) and refer to it as follows: Tafakkori, K. (2022). Quadratic assignment problem with Pyomo in Python. Supply Chain Data Analytics. url: https://www.supplychaindataanalytics.com/quadratic-assignment-problem-with-pyomo-in-python/

Leave a Reply

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Close

Meta