Exact And Approximate Sequential Methods In Solving The Quadratic Assignment Problem
Abstract
This article provides a description of the most common methods in solving the quadratic assignment problem with extensive reference material. This problem is a difficult combinatorial problem whose solution (for any instance) is even impossible to establish within a given radius unless the class of problems P coincide with the class of problems NP. The QAP is considered one of the most complex combinatorial optimization problems and is the model for many real life problems such as facility layout, campus planning, backboard wiring, scheduling, computer manufacturing, turbine balancing and process communications among other applications.
Another reason that highlights the structure and complexity of QAP is that many others significant NP-Complete combinatorial optimization problems result in particular cases of QAP, some of them are: The Traveling Salesman Problem (TSP): How an agent should visit a set of cities returning to the starting city in such a way that each city is just visited once and the cost of the tour is the minimum?. Maximum Clique Problem (MCP): Given a graph with , this problem consists in finding the maximum number such that there exists a subset with vertices which induces a clique in
Keywords
Full Text:
PDFReferences
Aarts, E., & Lenstra J. (1997). Local search in combinatorial optimization, Wiley, Chishester.
Adams, W., & Sherali H. (1986). A tight linearization and an algorithm for zero-one quadratic programming problems, Management Science 32, 1274-1290.
Balas E., & Mazzola J. (1984). Nonlinear programming: I. linearization techniques, Math. Program 30, 1-21.
Battiti R., & Tecchiolli G. (1994) . The reactive tabu search, ORSA Journal on Computing 6 126-140.
Bazaraa M., & Kirka O. (1980). Branch and bound based heuristic for solving quadratic assignment problem, Naval Res. Logist 30, 29-41.
Bazaraa M., & Sherali H. (1980) Benders' partitioning scheme applied to a new formulation of the quadratic assignment problem, Naval Research Logistics Quarterly 27, 29-41.
Brixius N., & Anstreicher K. (2001). Solving quadratic assignment problem using convex quadratic programming relaxations, Optimization Methods and Software 16, 49-68.
Burkard R., Cela E., Pardalos P. & Pitsoulis P., (1998). The quadratic assignment problem, 2, 241-338.
Burkard R., & Rendl F. (1984). A thermodynamically motivated simulation procedure for combinatorial optimization problems, European Journal of Operational Research 17, no. 2, 169-174.
Burkard R. (2013). The quadratic assignment problem., Pardalos P.M. Handbook of Combinatorial Optimization.
Colorni A., & Maniezzo M. (1999). The ant system applied to the quadratic assignment problem, IEEE T. Knowl. Dta En 11, 769-778.
Frieze A., & Yadegar J. (1983). On the quadratic assignment problem, Discrete Applied Mathematics 5, 89-98.
Gambardella L., Taillard E. & Dorigo M. (1999). Ant colonies for the qap, Oper Res. Soc 50, 167-176.
Gilmore P. (1962). Optimal and suboptimal algorithms for the quadratic assignment problem, SIAMJ Appl Math 10, 305-313.
Gomory R. (1958). Outline of an algorithm for integer solutions to linear programs, Bull AMS 64, 275-278.
James T., Rengo C., & Glover F. (2009). Multistart tabu serach and diversication strategies for the quedratic assignment problem, IEEE Trans Syst. Man Cybern, Part A Syst. Hum 39, 579-596.
Koopmans T. & Beckman M. (1957). Assignment problems and the location of economics activities, Assigment problemsand the locatin of economic activitics, 53-73.
Lawler E. (1963). The quadratic assignment problem, Management Science 9, 586-599.
Li Y., Pardalos M. & Resende M. (1994). A greedy randomized adaptive search procedure for the quadratic assignment problem, in quadratic assignment and related problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16, 237-261.
Lim M., Yuan Y. & Omatu S. (2002). Extensive testing of a hybird genetic algorithm for solving qudratic assignment problem, Comput. Optim. Appl 23, 47-64.
Liu H., Abraham A. & Zhang J. (2007). A particle swarm approach to quadratic assignment problems, Soft Computing in Industrial Applications. Springer Berlin Heidelberg 39, 213-222.
Muller-Merbach H. (1970). Optimale reihenfolgen, Springer-Verlag.
Murthy K., Pardalos P. & Li Y. (1992). A local search algorithm for the quadratic assignment problem, Informatica 3, 524-538.
Onwubolu G. & Sharma A. (2004). Particle swarm optimization for the assignment of facilities to locations, New Optimization Techniques in Engineering. Springer, 567-584.
Padberg M. & Rijal M. (1996). Location, scheduling, design and integer programming, Kluwer Academic, Boston.
Poveda R., Cárdenas E. & Garcia O. (2002). Hybrid of cellular parallel genetic algorithm and greedy 2-opt local search to solve quadratic assignment problem using cuda, Journal of Engineering Science and Technology Vol. 15, No. 5, 3082 – 3095.
Rodríguez J., MacPhee F., Bonham D. & Bhavsar V. (2006). Solving the quadratic assignment and dynamic plant layout problems using a new hybrid meta-heuristic approach, Int. J. High Perform. Comput. Netw 4, 286-294.
Sahni S. & Gonzalez T. (1976). P-complete approximation problems, Journal of the Association, 555-565.
Szwed P., Chmiel W. & Kad Luczka P. (2015). Opencl implementation of pso algorithm for the quadratic assignment problem, Artifcial Intelligence and Soft Computing - 14th International Conference, ICAISC.
Taillard E. (1991). Robust tabu search for the quadratic assignment problem, Parallel Computing 17, 443-455.
Talbi E. (2013). Combining metaheuristics with mathematical programming, constraint programming and machine learning, Springer-Verlag Berlin Heidelberg.
Tseng L. & Liang S. (2006). A hibrid metaheuristic for the quadratic assignment problem, Compt. Optim. Appl 34, 85-113.
Tsutsui S. & Fujimoto N. (2013). An analytical study of parallel ga with independent runs on gpus, Massively Parallel Evolutionary Computation on GPGPUs, Natural Computing Series Springer-Verlag Berlin Heidelberg, 105-120.
Tsutsui S. (2008). Parallel and colony optimization for the quadratic assignment problem with symmetric multi-processing, in ANTS Springer Berlin 5217, 363-370.
Wilhelm M. & Ward T (1987). Solving quadratic assignment problems by simulated annealing, IE Transaction 19, no. 1, 107-119.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
ISSN 1305-578X (Online)
Copyright © 2005-2022 by Journal of Language and Linguistic Studies