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
Browse Econ Literature
- Working papers
- Software components
- Book chapters
- JEL classification
More features
- Subscribe to new research
RePEc Biblio
Author registration.
- Economics Virtual Seminar Calendar NEW!
Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search
- Author & abstract
- 32 References
- 2 Citations
- Most related
- Related works & more
Corrections
- Silva, Allyson
- Coelho, Leandro C.
- Darvish, Maryam
Suggested Citation
Download full text from publisher, references listed on ideas.
Follow serials, authors, keywords & more
Public profiles for Economics researchers
Various research rankings in Economics
RePEc Genealogy
Who was a student of whom, using RePEc
Curated articles & papers on economics topics
Upload your paper to be listed on RePEc and IDEAS
New papers by email
Subscribe to new additions to RePEc
EconAcademics
Blog aggregator for economics research
Cases of plagiarism in Economics
About RePEc
Initiative for open bibliographies in Economics
News about RePEc
Questions about IDEAS and RePEc
RePEc volunteers
Participating archives
Publishers indexing in RePEc
Privacy statement
Found an error or omission?
Opportunities to help RePEc
Get papers listed
Have your research listed on RePEc
Open a RePEc archive
Have your institution's/publisher's output listed on RePEc
Get RePEc data
Use data assembled by RePEc
Tabu Search Techniques for the Quadratic Semi-Assignment Problem
- Conference paper
- Cite this conference paper
- Wolfgang Domschke 4 ,
- Peter Forst 4 &
- Stefan Voß 4
192 Accesses
20 Citations
Assigning items to sets such that a quadratic function is minimized may be referred to as the quadratic semi-assignment problem. This problem indeed is a relaxed version of the well known quadratic assignment problem. Applications may be found in floor layout planning, in certain median problems with mutual communication, and in the problem of schedule synchronization in public transit networks. The same problem also arises in certain scheduling problems where the deviation from due dates is penalized by a quadratic function.
In this paper we compare different improvement procedures for the quadratic semi-assignment problem. The main contribution will be to explore detailed tabu search techniques with respect to this specific problem and, in addition, to compare them with simulated annealing.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
- Available as PDF
- Read on any device
- Instant download
- Own it forever
- Compact, lightweight edition
- Dispatched in 3 to 5 business days
- Free shipping worldwide - see info
Tax calculation will be finalised at checkout
Purchases are for personal use only
Institutional subscriptions
Unable to display preview. Download preview PDF.
Chhajed, D. and T.J. Lowe (1990). M-median and m-center problems with mutual communication: solvable special cases. Working paper, University of Illinois Urbana-Champaign.
Google Scholar
Dammeyer, F., P. Forst and S. Voß (1991). On the cancellation sequence method of tabu search. ORSA Journal on Commuting 3, 262–265.
Article Google Scholar
Domschke, W. (1989). Schedule synchronization for public transit networks. OR Spektrum 11, 17–24.
Dutta, A., G. Koehler and A. Whinston (1982). On optimal allocation in a distributed processing environment. Management Science 28, 839–853.
Glover, F. (1989). Tabu search — part I. ORSA Journal on Computing 1, 190–206.
Glover, F. (1990a). Tabu search — part II. ORSA Journal on Computing 2, 4–32.
Glover, F. (1990b). Tabu search: a tutorial. Interfaces 20, 74–94.
Moretti Tomasin, E., P. Pianca and A. Sorato (1988). Heuristic algorithms for the quadratic semi-assignment problem. Ricerca Operativa 18, 65–89.
Simeone, B. (1986). An asymptotically exact algorithm for equipartition problems. Discrete Applied Mathematics 14, 283–293.
Skorin-Kapov, J. (1990). Tabu search applied to the quadratic assignment problem. ORSA Journal on Computing 2, 33–45.
Voß, S. (1990). Network design formulations in schedule synchronization. Paper presented at the 5th Workshop on Computer-Aided Scheduling of Public Transport, Montreal.
Download references
Author information
Authors and affiliations.
FB 1 / FG Operations Research, Technische Hochschule Darmstadt, Hochschulstraße 1, D - 6100, Darmstadt, Germany
Wolfgang Domschke, Peter Forst & Stefan Voß
You can also search for this author in PubMed Google Scholar
Editor information
Editors and affiliations.
Institute of Production Management, Fernuniversität Hagen, D-5800, Hagen 1, Germany
Günter Fandel
The Institute of Public Policy, George Mason University, Fairfax, VA, 22030-444, USA
Thomas Gulledge
NIST B 124 Metrology, AMFR, Gaithersburg, MD, 20899, USA
Albert Jones
Rights and permissions
Reprints and permissions
Copyright information
© 1992 Springer-Verlag Berlin · Heidelberg
About this paper
Cite this paper.
Domschke, W., Forst, P., Voß, S. (1992). Tabu Search Techniques for the Quadratic Semi-Assignment Problem. In: Fandel, G., Gulledge, T., Jones, A. (eds) New Directions for Operations Research in Manufacturing. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-77537-6_23
Download citation
DOI : https://doi.org/10.1007/978-3-642-77537-6_23
Publisher Name : Springer, Berlin, Heidelberg
Print ISBN : 978-3-642-77539-0
Online ISBN : 978-3-642-77537-6
eBook Packages : Springer Book Archive
Share this paper
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
- Publish with us
Policies and ethics
- Find a journal
- Track your research
IMAGES
VIDEO
COMMENTS
Comparing the above formulation with that of the quadratic assignment problem (cf. Quadratic assignment problem), we can see that the QSAP is a relaxed version of the QAP, where instead of assignment constraints we have semi-assignment constraints.SQAP unifies some interesting combinatorial optimization problems like clustering and m-coloring.
The Quadratic Semi-Assignment Problem (QSAP) (Greenberg, 1969) relaxes the constraints that all sites have to be assigned to exactly one facility, allowing the number of potential sites to be different than the number of facilities. A relatively new problem is the Generalized QAP (GQAP) (Lee & Ma, 2004), which considers that multiple facilities ...
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 ...
Abstract: The Quadratic Semi-Assignment Problem (QSAP) models a large variety of practical applications. In the present note we will consider a particular class of QSAP that can be solved by determining the maximum cost flow on a network. This class of problems arises in schedule synchronization and in transportation.
The Quadratic Semi-Assignment Problem (QSAP) plays an important role in modeling many practical applications, e.g. clustering and partitioning problems (Hansen and Lih 1989), assigning professors to departments (Gallo and Simeone 1991), and some scheduling problems (Chretienne
Keywords: Quadratic Semi-Assignment Problem, Graph Theory, Lower Bounds, Branch and Bound. 1. Introduction In this paper we will study some new solution approaches to the Quadratic Semi-Assignment Problem (QSAP). In particular we will discuss a class of problems that can be solved in polynomial time and how these results can be exploited to provide
A wide range of QAP theoretical studies involve several related quadratic problems, such as the quadratic bottleneck assignment problem, the biquadratic assignment problem, the 3-dimensional QAP, the quadratic semi-assignment problem and the multiobjective QAP. Almost all of these problems were reported in Burkard (2002). 2.2.1.
The quadratic assignment problem (QAP) was introduced by Koopmans and Beckmann in 1957 as a mathematical model for the location of indivisible economical activities [].Consider the problem of allocating n facilities to n locations, with the cost being a function of the distance and flow between the facilities plus costs associated with placing a facility at a certain location.
The Quadratic Assignment Problem (QAP), discovered by Koopmans and Beckmann in 1957, 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 ...
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
Downloadable (with restrictions)! In the Quadratic Assignment Problem (QAP), facilities are assigned to sites in order to minimize interactions between pairs of facilities. Although easy to define, it is among the hardest problems in combinatorial optimization, due to its non-linear nature. After decades of research on the QAP, many variants of this problem arose to deal with different ...
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 distributed computing, and combinatorial data analysis. ... positive semi-definite programming, discrete and combinatorial mathematics, graph and group theory ...
Such problems without this particular constraint are called semi-assignment problems, of which the most widely studied is the quadratic semi-assignment problem (QSAP) [35]. Practical applications ...
6.2.3 The Quadratic Semi-Assignment Problem (QSAP) This is a special case used to model clustering and partitioning problems by Hansen and Lih . This problem belongs to the class of the NP-hard problems some task-assignment problems in distributed systems can be easily formulated as quadratic semi-assignment problems.
Abstract In this paper, we show that the quadratic assignment problem (QAP) can be reformulated to an equivalent rank constrained doubly nonnegative (DNN) problem. Under the framework of the di erence of convex functions (DC) approach, a semi-proximal DC algorithm (DCA) is proposed for solving the relaxation of the
The quadratic semi-assignment problem holds a central position in combinatorial optimization, with diverse applications in manufacturing and service management. This paper introduces a specialized variant, motivated by the need for efficient collaborative team formation in university classrooms, and shows its NP-completeness.
Quadratic Assignment Problem (opens in a new tab) Quadratic Semi-assignment Problem (opens in a new tab) Local Optima (opens in a new tab) Combinatorial Optimization (opens in a new tab) Biquadratic Assignment Problem (opens in a new tab) Crossover Operators (opens in a new tab) Tabu Search (opens in a new tab)
Comparing the above formulation with that of the quadratic assignment problem (cf. Quadratic assignment problem ), we can see that the QSAP is a relaxed version of the QAP, where instead of assignment constraints we have semi-assignment constraints. SQAP unifies some interesting combinatorial optimization problems like clustering and m -coloring.
We consider the quadratic semi-assignment problem in which we minimize a quadratic pseudo-Boolean function F subject to the semi-assignment constraints. We propose in this paper a linear programming method to obtain the best reduction of this problem, i.e. to compute the greatest constant c such that F is equal to c plus F′ for all feasible solutions, F′ being a quadratic pseudo-Boolean ...
A polytope arising from the quadratic semi-assignment problems with symmetric distances is investigated, and some basic polyhedral properties, the dimension, the affine hull, and certain facets are obtained through an isomorphic projection. Expand
Assigning items to sets such that a quadratic function is minimized may be referred to as the quadratic semi-assignment problem. This problem indeed is a relaxed version of the well known quadratic assignment problem. Applications may be found in floor layout...
For P-complete problems such as traveling salesperson, cycle covers, 0-1 integer programming, multicommodity network flows, quadratic assignment, etc., it is shown that the approximation problem is …
The transit network timetabling problem can be represented through a quadratic semi-assignment problem (QSAP) (Klemt and Stemme, 1988, Bookbinder and Désilets, 1992, Daduna and Voss, 1995) and through a mixed integer non-linear program (MINLP) combining binary variables with real ones corresponding to departure and arrival times (Chakroborty ...