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/
Industrial engineer focusing on leveraging optimization methods and artificial intelligence technologies using multiple programming languages to empower a business to achieve its goals!
Leave a Reply