Quadratic assignment problem
Author: Thomas Kueny, Eric Miller, Natasha Rice, Joseph Szczerba, David Wittmann (SysEn 5800 Fall 2020)
- 1 Introduction
- 2.1 Koopmans-Beckman Mathematical Formulation
- 2.2.1 Parameters
- 2.3.1 Optimization Problem
- 2.4 Computational Complexity
- 2.5 Algorithmic Discussions
- 2.6 Branch and Bound Procedures
- 2.7 Linearizations
- 3.1 QAP with 3 Facilities
- 4.1 Inter-plant Transportation Problem
- 4.2 The Backboard Wiring Problem
- 4.3 Hospital Layout
- 4.4 Exam Scheduling System
- 5 Conclusion
- 6 References
Introduction
The Quadratic Assignment Problem (QAP), discovered by Koopmans and Beckmann in 1957 [1] , is a mathematical optimization module created to describe the location of invisible economic activities. An NP-Complete problem, this model can be applied to many other optimization problems outside of the field of economics. It has been used to optimize backboards, inter-plant transportation, hospital transportation, exam scheduling, along with many other applications not described within this page.
Theory, Methodology, and/or Algorithmic Discussions
Koopmans-beckman mathematical formulation.
Economists Koopmans and Beckman began their investigation of the QAP to ascertain the optimal method of locating important economic resources in a given area. The Koopmans-Beckman formulation of the QAP aims to achieve the objective of assigning facilities to locations in order to minimize the overall cost. Below is the Koopmans-Beckman formulation of the QAP as described by neos-guide.org.
Quadratic Assignment Problem Formulation
Inner Product
Note: The true objective cost function only requires summing entries above the diagonal in the matrix comprised of elements
Since this matrix is symmetric with zeroes on the diagonal, dividing by 2 removes the double count of each element to give the correct cost value. See the Numerical Example section for an example of this note.
Optimization Problem
With all of this information, the QAP can be summarized as:
Computational Complexity
QAP belongs to the classification of problems known as NP-complete, thus being a computationally complex problem. QAP’s NP-completeness was proven by Sahni and Gonzalez in 1976, who states that of all combinatorial optimization problems, QAP is the “hardest of the hard”. [2]
Algorithmic Discussions
While an algorithm that can solve QAP in polynomial time is unlikely to exist, there are three primary methods for acquiring the optimal solution to a QAP problem:
- Dynamic Program
- Cutting Plane
Branch and Bound Procedures
The third method has been proven to be the most effective in solving QAP, although when n > 15, QAP begins to become virtually unsolvable.
The Branch and Bound method was first proposed by Ailsa Land and Alison Doig in 1960 and is the most commonly used tool for solving NP-hard optimization problems.
A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before one lists all of the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and the branch is eliminated if it cannot produce a better solution than the best one found so far by the algorithm.
Linearizations
The first attempts to solve the QAP eliminated the quadratic term in the objective function of
in order to transform the problem into a (mixed) 0-1 linear program. The objective function is usually linearized by introducing new variables and new linear (and binary) constraints. Then existing methods for (mixed) linear integer programming (MILP) can be applied. The very large number of new variables and constraints, however, usually poses an obstacle for efficiently solving the resulting linear integer programs. MILP formulations provide LP relaxations of the problem which can be used to compute lower bounds.
Numerical Example
Qap with 3 facilities.
Applications
Inter-plant transportation problem.
The QAP was first introduced by Koopmans and Beckmann to address how economic decisions could be made to optimize the transportation costs of goods between both manufacturing plants and locations. [1] Factoring in the location of each of the manufacturing plants as well as the volume of goods between locations to maximize revenue is what distinguishes this from other linear programming assignment problems like the Knapsack Problem.
The Backboard Wiring Problem
As the QAP is focused on minimizing the cost of traveling from one location to another, it is an ideal approach to determining the placement of components in many modern electronics. Leon Steinberg proposed a QAP solution to optimize the layout of elements on a blackboard by minimizing the total amount of wiring required. [4]
When defining the problem Steinberg states that we have a set of n elements
as well as a set of r points
In his paper he derives the below formula:
In his paper Steinberg a backboard with a 9 by 4 array, allowing for 36 potential positions for the 34 components that needed to be placed on the backboard. For the calculation, he selected a random initial placement of s1 and chose a random family of 25 unconnected sets.
The initial placement of components is shown below:
After the initial placement of elements, it took an additional 35 iterations to get us to our final optimized backboard layout. Leading to a total of 59 iterations and a final wire length of 4,969.440.
Hospital Layout
Building new hospitals was a common event in 1977 when Alealid N Elshafei wrote his paper on "Hospital Layouts as a Quadratic Assignment Problem". [5] With the high initial cost to construct the hospital and to staff it, it is important to ensure that it is operating as efficiently as possible. Elshafei's paper was commissioned to create an optimization formula to locate clinics within a building in such a way that minimizes the total distance that a patient travels within the hospital throughout the year. When doing a study of a major hospital in Cairo he determined that the Outpatient ward was acting as a bottleneck in the hospital and focused his efforts on optimizing the 17 departments there.
Elshafei identified the following QAP to determine where clinics should be placed:
For the Cairo hospital with 17 clinics, and one receiving and recording room bringing us to a total of 18 facilities. By running the above optimization Elshafei was able to get the total distance per year down to 11,281,887 from a distance of 13,973,298 based on the original hospital layout.
Exam Scheduling System
The scheduling system uses matrices for Exams, Time Slots, and Rooms with the goal of reducing the rate of schedule conflicts. To accomplish this goal, the “examination with the highest cross faculty student is been prioritized in the schedule after which the examination with the highest number of cross-program is considered and finally with the highest number of repeating student, at each stage group with the highest number of student are prioritized.” [6]
- ↑ 1.0 1.1 1.2 Koopmans, T., & Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 25(1), 53-76. doi:10.2307/1907742
- ↑ 2.0 2.1 Quadratic Assignment Problem. (2020). Retrieved December 14, 2020, from https://neos-guide.org/content/quadratic-assignment-problem
- ↑ 3.0 3.1 3.2 Burkard, R. E., Çela, E., Pardalos, P. M., & Pitsoulis, L. S. (2013). The Quadratic Assignment Problem. https://www.opt.math.tugraz.at/~cela/papers/qap_bericht.pdf .
- ↑ 4.0 4.1 Leon Steinberg. The Backboard Wiring Problem: A Placement Algorithm. SIAM Review . 1961;3(1):37.
- ↑ 5.0 5.1 Alwalid N. Elshafei. Hospital Layout as a Quadratic Assignment Problem. Operational Research Quarterly (1970-1977) . 1977;28(1):167. doi:10.2307/300878
- ↑ 6.0 6.1 Muktar, D., & Ahmad, Z.M. (2014). Examination Scheduling System Based On Quadratic Assignment.
Navigation menu
A Fuzzy Particle Swarm Approach to Multiobjective Quadratic Assignment Problems
Ieee account.
- Change Username/Password
- Update Address
Purchase Details
- Payment Options
- Order History
- View Purchased Documents
Profile Information
- Communications Preferences
- Profession and Education
- Technical Interests
- US & Canada: +1 800 678 4333
- Worldwide: +1 732 981 0060
- Contact & Support
- About IEEE Xplore
- Accessibility
- Terms of Use
- Nondiscrimination Policy
- Privacy & Opting Out of Cookies
A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.
- 90% Refund @Courses
- Data Structure
- Analysis of Algorithms
- Backtracking
- Dynamic Programming
- Divide and Conquer
- Geometric Algorithms
- Mathematical Algorithms
- Pattern Searching
- Bitwise Algorithms
- Branch & Bound
- Randomized Algorithms
- Solve Coding Problems
- Introduction to Exact Cover Problem and Algorithm X
- Implementation of Exact Cover Problem and Algorithm X using DLX
- Introduction to Grover's Algorithm
- Art Gallery Problem
- Preemptive Priority CPU Scheduling Algorithm
- Transform and Conquer Technique
- Representation Change in Transform and Conquer Technique
- What Does Big O(N^2) Complexity Mean?
- Algorithm definition and meaning
- How to write a Pseudo Code?
- How to develop an Algorithm from Scratch | Develop Algorithmic Thinking
- Approximation Algorithms
- Accounting Method | Amortized Analysis
- Genetic Algorithms
- Difference between average case and amortized analysis
- Polynomial Time Approximation Scheme
- Josephus Problem when k is 2
- Minimum number of items to be delivered
- How to store the data for multiple objectives in Shortest path search Algorithms ?
Quadratic Assignment Problem (QAP)
The Quadratic Assignment Problem (QAP) is an optimization problem that deals with assigning a set of facilities to a set of locations, considering the pairwise distances and flows between them.
The problem is to find the assignment that minimizes the total cost or distance, taking into account both the distances and the flows.
The distance matrix and flow matrix, as well as restrictions to ensure each facility is assigned to exactly one location and each location is assigned to exactly one facility, can be used to formulate the QAP as a quadratic objective function.
The QAP is a well-known example of an NP-hard problem , which means that for larger cases, computing the best solution might be difficult. As a result, many algorithms and heuristics have been created to quickly identify approximations of answers.
There are various types of algorithms for different problem structures, such as:
- Precise algorithms
- Approximation algorithms
- Metaheuristics like genetic algorithms and simulated annealing
- Specialized algorithms
Example: Given four facilities (F1, F2, F3, F4) and four locations (L1, L2, L3, L4). We have a cost matrix that represents the pairwise distances or costs between facilities. Additionally, we have a flow matrix that represents the interaction or flow between locations. Find the assignment that minimizes the total cost based on the interactions between facilities and locations. Each facility must be assigned to exactly one location, and each location can only accommodate one facility.
Facilities cost matrix:
Flow matrix:
To solve the QAP, various optimization techniques can be used, such as mathematical programming, heuristics, or metaheuristics. These techniques aim to explore the search space and find the optimal or near-optimal solution.
The solution to the QAP will provide an assignment of facilities to locations that minimizes the overall cost.
The solution generates all possible permutations of the assignment and calculates the total cost for each assignment. The optimal assignment is the one that results in the minimum total cost.
To calculate the total cost, we look at each pair of facilities in (i, j) and their respective locations (location1, location2). We then multiply the cost of assigning facility1 to facility2 (facilities[facility1][facility2]) with the flow from location1 to location2 (locations[location1][location2]). This process is done for all pairs of facilities in the assignment, and the costs are summed up.
Overall, the output tells us that assigning facilities to locations as F1->L1, F3->L2, F2->L3, and F4->L4 results in the minimum total cost of 44. This means that Facility 1 is assigned to Location 1, Facility 3 is assigned to Location 2, Facility 2 is assigned to Location 3, and Facility 4 is assigned to Location 4, yielding the lowest cost based on the given cost and flow matrices.This example demonstrates the process of finding the optimal assignment by considering the costs and flows associated with each facility and location. The objective is to find the assignment that minimizes the total cost, taking into account the interactions between facilities and locations.
Applications of the QAP include facility location, logistics, scheduling, and network architecture, all of which require effective resource allocation and arrangement.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule. Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!
- DSA in Java
- DSA in Python
- DSA in JavaScript
Please Login to comment...
- nikhilgarg527
- kake_karthik
- Flask Mega-Tutorial 2024: A Complete Update for Python Enthusiasts
- Google Maps on Android: Now Featuring Current Weather Information
- Apple's 2024 iPad Pro: Bigger OLED Screen, M3 Chip, and a Better Magic Keyboard
- Microsoft to Train 2 Mn in AI by 2025: A Game-Changer for Employment and Skill Development
- 30 OOPs Interview Questions and Answers (2024)
Improve your Coding Skills with Practice
Optimization of fuzzy bi-objective fractional assignment problem
- Application Article
- Published: 13 March 2019
- Volume 56 , pages 1091–1102, ( 2019 )
Cite this article
- Neha Gupta 1
229 Accesses
5 Citations
Explore all metrics
A Correction to this article was published on 03 June 2019
This article has been updated
Theory and applications of fractional programming have been significantly developed in the few last decades and assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization. Generally, in real world problems, the possible values of coefficients of a linear fractional programming problem are often only imprecisely or ambiguously known to the decision maker, therefore, it would be certainly more appropriate to interpret the coefficients as fuzzy numerical data. In this article, a fuzzy bi-objective fractional assignment problem has been formulated. Here the parameters are represented by triangular fuzzy numbers and the fuzzy problem is transformed into standard crisp problem through \(\alpha \) -cut and then the compromise solution is derived by fuzzy programming.
This is a preview of subscription content, log in via an institution to check access.
Access this article
Price includes VAT (Russian Federation)
Instant access to the full article PDF.
Rent this article via DeepDyve
Institutional subscriptions
Change history
03 june 2019.
In the original published article the “Conclusion and future scope” paragraph has been incorrectly published.
Triangular Fuzzy number (TFN) A fuzzy number \({\tilde{A}}=(p,q,r)\) is said to be a triangular fuzzy number if its membership function is given by
Akkapeddi, S.M.: Fuzzy programming with quadratic membership functions for multi-objective transportation problem. Pak. J. Stat. Oper. Res. 11 (2), 231–240 (2015)
Article Google Scholar
Bellman, R.E., Zadeh, L.A.: Decision-making in a fuzzy environment. Manag. Sci. 17 (4), B-141 (1970)
Charnes, A., Cooper, W.W.: Programming with linear fractional functionals. Naval Res. Logist. Q. 9 (3–4), 181–186 (1962)
De, P.K., Yadav, B.: A general approach for solving assignment problems involving with fuzzy cost coefficients. Mod. Appl. Sci. 6 (3), 2 (2012)
Dinkelbach, W.: On nonlinear fractional programming. Manag. Sci. 13 , 492–498 (1967)
Gupta, R.: Decomposition method and transportation type problems with a fractional objective function. ZAMM-J. Appl. Math. Mech. (Zeitschrift fr Angewandte Mathematik und Mechanik) 57 (2), 81–88 (1977)
Kar, S., Basu, K., Mukherjee, S.: Solution of generalized fuzzy assignment problem with restriction on costs under fuzzy environment. Int. J. Fuzzy Math. Syst. 4 , 169–180 (2014)
Google Scholar
Kumar, A., Gupta, A., Kaur, A.: Method for solving fully fuzzy assignment problems using triangular fuzzy numbers. World Acad. Sci. Eng. Technol. Int. J. Comput. Electr. Autom. Control Inf. Eng. 3 (7), 1889–1892 (2009)
Kumar, P.S., Hussain, R.J.: A method for solving balanced intuitionistic fuzzy assignment problem. Int. J. Eng. Res. Appl. 4 (3), 897–903 (2014)
Lin, C.J.: A simplex-based labelling algorithm for the linear fractional assignment problem. Optimization 64 (4), 929–939 (2015)
Lin, C.J., Wen, U.P.: A labeling algorithm for the fuzzy assignment problem. Fuzzy Sets Syst. 142 (3), 373–391 (2004)
Pandian, P., Kavitha, K.: A new method for solving fuzzy assignment problems. Ann. Pure Appl. Math. 1 , 69–83 (2012)
Sadia, S., Gupta, N., Ali, Q.M.: Multiobjective capacitated fractional transportation problem with mixed constraints. Math. Sci. Lett. 5 (3), 235–242 (2016)
Sakawa, M., Nishizaki, I., Uemura, Y.: Interactive fuzzy programming for two-level linear and linear fractional production and assignment problems: a case study. Eur. J. Oper. Res. 135 (1), 142–157 (2001)
Saruwatari, Y., Shigeno, M., Matsui, T.: An algorithm for fractional assignment problems. Discrete Appl. Math. 56 (2), 333–343 (1995)
Swarup, K.: Transportation technique in linear fractional functional programming. J. R. Naval Sci. Serv. 21 (5), 256–260 (1966)
Download references
Acknowledgements
The author express their sincere thanks to editor and referees for their valuable suggestions and comments, which improved the quality of the paper.
Author information
Authors and affiliations.
Faculty of Management Sciences, Amity University, Noida, India
You can also search for this author in PubMed Google Scholar
Corresponding author
Correspondence to Neha Gupta .
Additional information
Publisher's note.
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Reprints and permissions
About this article
Gupta, N. Optimization of fuzzy bi-objective fractional assignment problem. OPSEARCH 56 , 1091–1102 (2019). https://doi.org/10.1007/s12597-019-00367-2
Download citation
Accepted : 03 March 2019
Published : 13 March 2019
Issue Date : September 2019
DOI : https://doi.org/10.1007/s12597-019-00367-2
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Assignment problem
- Fractional programming problem
- Fuzzy numbers
- Fuzzy programming
- Find a journal
- Publish with us
- Track your research
IMAGES
VIDEO
COMMENTS
1. Introduction The assignment problem (AP), which has been widely applied in both manufacturing and service systems, is to find the total costs optimal jobs assignment schedule where n jobs are allocated to n workers (or machines), and each worker receives exactly just one job. The AP is a special type of linear 0-1 programming.
The Quadratic Assignment Problem (QAP), discovered by Koopmans and Beckmann in 1957 [1], is a mathematical optimization module created to describe the location of invisible economic activities. An NP-Complete problem, this model can be applied to many other optimization problems outside of the field of economics.
also considers problems related to the QAP, e.g. the biquadratic assignment problem, and discusses the relationship between the QAP and other well known combinatorial optimization problems, e.g. the traveling salesman problem, the graph partitioning problem, etc. The paper will appear in the Handbook of Combinatorial Optimization to be published
The quadratic assignment problem (QAP) has considered one of the most significant combinatorial optimization problems due to its variant and significant applications in real life such as scheduling, production, computer manufacture, chemistry, facility location, communication, and other fields. QAP is NP-hard problem that is impossible to be solved in polynomial time when the problem size ...
Based on fuzzy structural characteristics, we propose the concept of level effect function. It can be used to establish an IL -metric method to measure all aspects of fuzzy information. This algorithm in systems perspectives can be widely used in many assignment problems. Introduction
This paper introduces a fuzzy particle swarm algorithm to handle the Multiobjective Quadratic Assignment Problem (mQAP). In the fuzzy scheme, the representations of the position and velocity of the particles in the conventional PSO is extended from the real vectors to fuzzy matrices.
The fuzzy quadratic assignment problem with penalty: New models and genetic algorithm @article{Liu2006TheFQ, title={The fuzzy quadratic assignment problem with penalty: New models and genetic algorithm}, author={Linzhong Liu and Yinzhen Li}, journal={Appl. Math. Comput.}, year={2006}, volume={174}, pages={1229-1244}, url={https://api ...
The fuzzy quadratic assignment problem with penalty: New models and genetic algorithm. Applied Mathematics and Computation 174 (2), 1229-1244 DOI: Authors: Linzhong Liu Tsinghua...
A fuzzy particle swarm algorithm to handle the Multiobjective Quadratic Assignment Problem (mQAP) is introduced, in the fuzzy scheme, the representations of the position and velocity of the particles in the conventional PSO is extended from the real vectors to fuzzy matrices. The multiobjective Quadratic Assignment Problem (mQAP) is considered as one of the hardest optimization problems but ...
The quadratic assignment problem (QAP), one of the most difficult problems in the NP-hard class, models many real-life problems in several areas such as facilities location, parallel and ...
In this paper a particle swarm optimization algorithm is presented to solve the Quadratic Assignment Problem, which is a NP-Complete problem and is one of the most interesting and challenging combinatorial optimization problems in existence.
In this paper, the fuzzy quadratic assignment problem with penalty is formulated as expected value model, chance-constrained programming and dependent-chance programming according to various decision criteria, and the crisp equivalents are given. Furthermore, hybrid genetic algorithm is designed for solving the proposed fuzzy programming models.
The Quadratic Assignment Problem (QAP) is an optimization problem that deals with assigning a set of facilities to a set of locations, considering the pairwise distances and flows between them. The problem is to find the assignment that minimizes the total cost or distance, taking into account both the distances and the flows.
The formal definition of the quadratic assignment problem is as follows: Given two sets, P ("facilities") and L ("locations"), of equal size, together with a weight function w : P × P → R and a distance function d : L × L → R. Find the bijection f : P → L ("assignment") such that the cost function: is minimized.
A fuzzy particle swarm approach to multiobjective quadratic assignment problems 2008 • Ajith Abraham Abstract The multiobjective Quadratic Assignment Problem (mQAP) is considered as one of the hardest optimization problems but with many real-world applications.
The fuzzy assignment problem (FAP) is more realistic than the assignment problem (AP) because most real environments are uncertain. Sakawa et al. [ 14 ] applies interactive fuzzy programming for two level linear and linear fractional assignment problem and derive satisfactory solution to the problem based on production and work force assignment ...
In this paper, the fuzzy quadratic assignment problem with penalty is formulated as expected value model, chance-constrained programming and dependent-chance programming according to various decision criteria, and the crisp equivalents are given. Furthermore, hybrid genetic algorithm is designed for solving the proposed fuzzy programming models.
Abstract and Figures. We solve a fully fuzzy assignment problem (FAP) where the costs are triangular fuzzy numbers. The FAP has gained its importance in the recent years. We have represented the ...
the classical assignment problems are proposed e.g. bottleneck assignment problem, generalized assignment problem, quadratic assignment problem etc. In recent years, fuzzy transportation and fuzzy assignment problems have received much concentration. Lin and Wen [8] proposed an efficient algorithm based on
This paper describes a fuzzy set theory based heuristic for the quadratic assignment formulation of the facility layout problem with single/multiple objectives.
Liu and Li [21] studied the fuzzy quadratic assignment problem with penalty as expected value model, chance-constrained programming and dependent-chance programming. Tanaka and Ishibuchi [33] considered quadratic membership functions to propose an identification method of interactive fuzzy parameters in possibilistic linear systems. Tang and ...
The assignment problem (AP) is a special type of linear programming problem in which our objective is to assign various number of jobs to an equal number of persons at a minimum cost. All the algorithms developed to find the optimal solution of Transportation problem are applicable to assignment problem.
It is shown that the Lagrangian dual based on relaxing the constraints XXT=I and the seemingly redundant constraints XT X=I has a zero duality gap, which has natural applications to quadratic assignment and graph partitioning problems, as well as the problem of minimizing the weighted sum of the largest eigenvalues of a matrix.
Ant colony optimisation algorithms have been applied to a wide range of combinatorial optimisation problems, from quadratic assignment to protein folding or routing vehicles. ... Ant colony optimisation algorithm (HFACO) and hybrid fuzzy logic were used in the construction of the routing protocol. Numerous derived techniques have been adapted ...