Quadratic Assignment Problem
- PDF / 669,293 Bytes
- 52 Pages / 547.087 x 737.008 pts Page_size
- 8 Downloads / 198 Views
QC
Quadratic Assignment Problem
Quality control; quality circles
Alla Kammerdiner1, Theodoros Gevezes2, Eduardo Pasiliao3, Leonidas Pitsoulis2 and Panos M. Pardalos4 1 New Mexico State University, Las Cruces, NM, USA 2 Aristotle University of Thessaloniki, Thessaloniki, Greece 3 Air Force Research Laboratory (AFRL) Munitions Directorate, Eglin Air Force Base, FL, USA 4 University of Florida, Gainesville, FL, USA
See ▶ Quality Control
Q-Gert
Introduction
Queue graphical evaluation and review technique.
The quadratic assignment problem (QAP) is one of the most computationally challenging and well-known problems in the area of combinatorial and integer optimization. In general terms, also known as in the Lawler form (Lawler 1963), the QAP can be be stated as
See ▶ GERT ▶ Network Planning ▶ Project Management ▶ Research and Development
QP ▶ Quadratic Programming
min
p2Pn
n X n X
cijpðiÞpðjÞ
(1)
i¼1 j¼1
where Pn denotes the set of all possible permutations of n elements. In its original introduction due to Koopmans and Beckmann (1957), the statement of the QAP assumes that the cost coefficients cijpq have the following simple structure: ( fij dpq if i 6¼ j or p 6¼ q; cijpq ¼ (2) fii dkk þ aik otherwise:
S.I. Gass, M.C. Fu (eds.), Encyclopedia of Operations Research and Management Science, DOI 10.1007/978-1-4419-1153-7, # Springer Science+Business Media New York 2013
Q
1194
This less general version of the problem is known as the QAP in the Koopmans-Beckmann form. In economic practice, the QAP arises naturally as a class of facility location and layout problems in the following way. Given • two sets of the same cardinality n, namely, a set of objects (e.g., facilities) and a set of positions (e.g., locations), • an n n matrix D ¼ dpq of distances between two positions, • an n n matrix F ¼ fij of flows from one object to another (e.g., amount of goods transferred from location i to location j),and • an n n matrix A ¼ aip of costs of placing a specific object at a given location, find a bijective assignment of the objects to the respective positions such that the total cost is minimized. In this context, it is commonly assumed that F and D are symmetric matrices with all zeros in the diagonal and nonnegative elements and that matrix A is also nonnegative. In addition to the aforementioned area, the QAP has applications in various other fields as diverse as ergonomics, electronics and computer manufacturing, telecommunications, sports, archeology, and organic chemistry. In particular, the QAP can be used to place interconnected control and display devices on the backboard panel in such a manner that minimizes the total wire length; to design an ergonomic typewriter keyboard; to create an efficient layout for a hospital; to rank teams in a relay race; to analyze chemical reactions between various organic compounds; and to study archeological data. Other QAP applications include discriminative word alignment used in statistical machine translation systems, and symbol mapping diversity des
Data Loading...
