We apologize for the inconvenience...
To ensure we keep this website safe, please can you confirm you are a human by ticking the box below.
If you are unable to complete the above request please contact us using the below link, providing a screenshot of your experience.
https://ioppublishing.org/contacts/
Please solve this CAPTCHA to request unblock to the website
Academia.edu no longer supports Internet Explorer.
To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to upgrade your browser .
Enter the email address you signed up with and we'll email you a reset link.
- We're Hiring!
- Help Center
The quadratic assignment problem: A survey and recent developments
Quadratic Assignment Problems model many applications in diverse areas such as operations research, parallel and distributed computing, and combinatorial data analysis. In this paper we survey some of the most important techniques, applications, and methods regarding the quadratic assignment problem. We focus our attention on recent developments. 1991 Mathematics Subject Classi cation. Primary 90B80, 90C20, 90C35, 90C27; Secondary 65H20, 65K05.
Related Papers
Güneş Erdoğan
The Quadratic Assignment Problem (QAP) is one of the hardest combinatorial optimization problems known. Exact solution attempts proposed for instances of size larger than 15 have been generally unsuccessful even though successful implementations have been reported on some test problems from the QAPLIB up to size 36. In this dissertation, we analyze the binary structure of the QAP and present new IP formulations. We focus on “flow-based” formulations, strengthen the formulations with valid inequalities, and report computational experience with a branch-and-cut algorithm. Next, we present new classes of instances of the QAP that can be completely or partially reduced to the Linear Assignment Problem and give procedures to check whether or not an instance is an element of one of these classes. We also identify classes of instances of the Koopmans-Beckmann form of the QAP that are solvable in polynomial time. Lastly, we present a strong lower bound based on Bender’s decomposition.
Applied Mathematical Sciences
Shahin Gelareh
New ideas in optimization
Marco Dorigo
Álvaro M. Valdebenito B.
The quadratic assignment problem (QAP) is one of the hardest combinatorial optimization problems known. Exact solution attempts proposed for instances of size larger than 15 have been generally unsuccessful even though successful implementations have been reported on some test problems from the QAPLIB up to size 36. In this study, we focus on the Koopmans–Beckmann formulation and exploit the structure of the flow and distance matrices based on a flow-based linearization technique that we propose.
The quadratic assignment problem (QAP) is an important problem in theory and practice. It was, which was introduced by Koopmans and Beckmann in 1957 [28] and is a model for many practical problems like backboard wiring [53], campus and hospital layout [15, 17], typewriter keyboard design [9], scheduling [23] and many others [16, 29] can be formulated as QAPs.
Panos M Pardalos
Abstract In the NP-complete quadratic assignment problem (QAP), n facilities are to be assigned to n sites at minimum cost. The contribution of assigning facility i to site k and facility j to site l to the total cost is f ij d kl, where f ij is the flow between facilities i and j, and d kl is the distance between sites k and l. Only very small (n≤ 20) instances of the QAP have been solved exactly, and heuristics are therefore used to produce approximate solutions.
Analysis of random instances of optimization problems provides valuable insights into the behavior and properties of problem's solutions, feasible region, and optimal values, especially in large-scale cases. A class of problems that have been studied extensively in the literature using the methods of probabilistic analysis is represented by the assignment problems, and many important problems in operations research and computer science can be formulated as assignment problems.
Abstract This paper aims at describing the state of the art on quadratic assignment problems (QAPs). It discusses the most important developments in all aspects of the QAP such as linearizations, QAP polyhedra, algorithms to solve the problem to optimality, heuristics, polynomially solvable special cases, and asymptotic behavior.
Seventy optimizers from a variety of disciplines met at the University of Waterloo, April 26-28, 2001, for a special workshop on the latest novel techniques for handling hard discrete optimization problems. Each of the three days started with an early breakfast at 7: 15AM; talks began at 8: 30AM and ended at 6PM; lunch was also provided on site to facilitate interaction and collaboration.
Loading Preview
Sorry, preview is currently unavailable. You can download the paper by clicking the button above.
RELATED PAPERS
Pesquisa Operacional
Paulo Boaventura Netto
Eugene Stanley
Computers & Operations Research
Ricardo P M Ferreira
Discrete Applied Mathematics
catherine roucairol
Ashish Tiwari
Physica D-nonlinear Phenomena
Katsuyoshi Tsujita
Cesar Beltran-Royo
Paulo Boaventura-Netto , Tania Querido
Encyclopedia of Optimization
Panos Pardalos
Journal of Combinatorial Optimization
Madalina Drugan
Journal of Global Optimization
Franz Rendl
Mathematics of Operations Research
Ali Safari Mamaghani
Mathematical Programming
Eranda Çela
Combinatorial Optimization
Eranda Çela , Eduardo Pasiliao
INFORMS Journal on Computing
Vittorio Maniezzo
Dennis Heffley
ACM Transactions on Mathematical Software
Wajeb Gharibi
Tansel Dökeroğlu
European Journal of Operational Research
George P Karatzas
Ieee Transactions on Information Theory
David Malah
International Series in Operations Research & Management Science
Renata Sotirov
faiz ahyaningsih
Computational Optimization and Applications
Zvi Drezner
Operations Research
Journal of Applied Mathematics and Decision Sciences
Discrete Optimization
Handbook of Combinatorial Optimization
Sigeru Omatu
krishna jha
surya singh
RELATED TOPICS
- We're Hiring!
- Help Center
- Find new research papers in:
- Health Sciences
- Earth Sciences
- Cognitive Science
- Mathematics
- Computer Science
- Academia ©2023
IMAGES
VIDEO
COMMENTS
This paper aims at describing the state of the art on quadratic assignment problems. (QAPs). It discusses the most important developments in all aspects of
The Quadratic Assignment Problem (QAP) is one of the hardest combinatorial optimization problems known. Exact solution attempts proposed.
The Quadratic Assignment Problem (QAP) has remained one of the great challenges in combinatorial optimization. It is still considered a computationally
The Quadratic assignment problem (QAP) is one of the fundamental, interesting and challenging combinatorial optimization problems from.
Combinatorial optimization, quadratic assignment problem, graph partitioning, survey, exact algorithms, heuristics, algorithms, test problems, bibliography. c
PDF | On Feb 1, 1972, Dennis R. Heffley published The Quadratic Assignment Problem: A Note | Find, read and cite all the research you need on ResearchGate.
PDF | The quadratic assignment problem (QAP) was introduced by Koopmans and Beckmann in 1957 as a mathematical model for the location of a set of.
IOP Conference Series: Materials Science and Engineering. PAPER • OPEN ACCESS. Solving Quadratic Assignment Problem with Fixed. Assignment (QAPFA) using
Lastly, we present a strong lower bound based on Bender's decomposition. Download Free PDF View PDF. New ideas in optimization. ACO algorithms for
Only very small (n≤ 20) instances of the QAP have been solved exactly, and heuristics are therefore used to produce approximate solutions. Download Free PDF