- Optimization
Pyomo for quadratic assignment problem
- Keivan Tafakkori M.Sc.
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.
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:
Then, I model and solve QAP as follows:
Fortunately, the status is optimal and I obtain the following results:
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!
You May Also Like
Service facility allocation – an optimization
Warehouse receiving process simulation
Visualization of SimPy parking lot simulation results
Leave a reply.
- Default Comments
- Facebook Comments
Leave a Reply Cancel reply
Your email address will not be published. Required fields are marked *
This site uses Akismet to reduce spam. Learn how your comment data is processed .
- Entries feed
- Comments feed
- WordPress.org
Privacy Overview
IMAGES
VIDEO