IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v139y2005i1p65-9410.1007-s10479-005-3444-z.html
   My bibliography  Save this article

Recent Advances for the Quadratic Assignment Problem with Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods

Author

Listed:
  • Zvi Drezner
  • Peter Hahn
  • Éeric Taillard

Abstract

This paper reports heuristic and exact solution advances for the Quadratic Assignment Problem (QAP).QAPinstances most often discussed in the literature are relatively well solved by heuristic approaches. Indeed, solutions at a fraction of one percent from the best known solution values are rapidly found by most heuristic methods. Exact methods are not able to prove optimality for these instances as soon as the problem size approaches 30 to 40. This article presents new QAP instances that are ill conditioned for many metaheuristic-based methods. However, these new instances are shown to be solved relatively well by some exact methods, since problem instances up to a size of 75 have been exactly solved. Copyright Springer Science + Business Media, Inc. 2005

Suggested Citation

  • Zvi Drezner & Peter Hahn & Éeric Taillard, 2005. "Recent Advances for the Quadratic Assignment Problem with Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods," Annals of Operations Research, Springer, vol. 139(1), pages 65-94, October.
    • Handle: RePEc:spr:annopr:v:139:y:2005:i:1:p:65-94:10.1007/s10479-005-3444-z
    DOI: 10.1007/s10479-005-3444-z
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-005-3444-z
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-005-3444-z?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Taillard, Eric D. & Gambardella, Luca M. & Gendreau, Michel & Potvin, Jean-Yves, 2001. "Adaptive memory programming: A unified view of metaheuristics," European Journal of Operational Research, Elsevier, vol. 135(1), pages 1-16, November.
    2. S. W. Hadley & F. Rendl & H. Wolkowicz, 1992. "A New Lower Bound Via Projection for the Quadratic Assignment Problem," Mathematics of Operations Research, INFORMS, vol. 17(3), pages 727-739, August.
    3. Warren P. Adams & Hanif D. Sherali, 1990. "Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems," Operations Research, INFORMS, vol. 38(2), pages 217-226, April.
    4. Roberto Battiti & Giampietro Tecchiolli, 1994. "The Reactive Tabu Search," INFORMS Journal on Computing, INFORMS, vol. 6(2), pages 126-140, May.
    5. Christopher E. Nugent & Thomas E. Vollmann & John Ruml, 1968. "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research, INFORMS, vol. 16(1), pages 150-173, February.
    6. Hahn, Peter & Grant, Thomas & Hall, Nat, 1998. "A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method," European Journal of Operational Research, Elsevier, vol. 108(3), pages 629-640, August.
    7. Burkard, R. E. & Rendl, F., 1984. "A thermodynamically motivated simulation procedure for combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 17(2), pages 169-174, August.
    8. Hansen, Pierre & Mladenovic, Nenad, 2001. "Variable neighborhood search: Principles and applications," European Journal of Operational Research, Elsevier, vol. 130(3), pages 449-467, May.
    9. Warren P. Adams & Hanif D. Sherali, 1986. "A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems," Management Science, INFORMS, vol. 32(10), pages 1274-1290, October.
    10. Peter Hahn & Thomas Grant, 1998. "Lower Bounds for the Quadratic Assignment Problem Based upon a Dual Formulation," Operations Research, INFORMS, vol. 46(6), pages 912-922, December.
    11. Laporte, Gilbert & Mercure, Helene, 1988. "Balancing hydraulic turbine runners: A quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 35(3), pages 378-381, June.
    12. L M Gambardella & É D Taillard & M Dorigo, 1999. "Ant colonies for the quadratic assignment problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(2), pages 167-176, February.
    13. Jadranka Skorin-Kapov, 1990. "Tabu Search Applied to the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 2(1), pages 33-45, February.
    14. Connolly, David T., 1990. "An improved annealing scheme for the QAP," European Journal of Operational Research, Elsevier, vol. 46(1), pages 93-100, May.
    15. Zvi Drezner, 2003. "A New Genetic Algorithm for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 320-330, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Monique Guignard, 2020. "Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic 0–1 optimization problems with linear constraints," Annals of Operations Research, Springer, vol. 286(1), pages 173-200, March.
    2. Madalina M. Drugan, 2019. "Estimating the number of basins of attraction of multi-objective combinatorial problems," Journal of Combinatorial Optimization, Springer, vol. 37(4), pages 1367-1407, May.
    3. James, Tabitha & Rego, Cesar & Glover, Fred, 2009. "A cooperative parallel tabu search algorithm for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 195(3), pages 810-826, June.
    4. Paul, G., 2011. "An efficient implementation of the robust tabu search heuristic for sparse quadratic assignment problems," European Journal of Operational Research, Elsevier, vol. 209(3), pages 215-218, March.
    5. Krešimir Mihić & Kevin Ryan & Alan Wood, 2018. "Randomized Decomposition Solver with the Quadratic Assignment Problem as a Case Study," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 295-308, May.
    6. Mădălina M. Drugan, 2015. "Generating QAP instances with known optimum solution and additively decomposable cost function," Journal of Combinatorial Optimization, Springer, vol. 30(4), pages 1138-1172, November.
    7. Zvi Drezner & Alfonsas Misevičius & Gintaras Palubeckis, 2015. "Exact algorithms for the solution of the grey pattern quadratic assignment problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 82(1), pages 85-105, August.
    8. Eduardo G. Pardo & Mauricio Soto & Christopher Thraves, 2015. "Embedding signed graphs in the line," Journal of Combinatorial Optimization, Springer, vol. 29(2), pages 451-471, February.
    9. Zakir Hussain Ahmed, 2016. "Experimental analysis of crossover and mutation operators on the quadratic assignment problem," Annals of Operations Research, Springer, vol. 247(2), pages 833-851, December.
    10. Peter Hahn & J. MacGregor Smith & Yi-Rong Zhu, 2010. "The Multi-Story Space Assignment Problem," Annals of Operations Research, Springer, vol. 179(1), pages 77-103, September.
    11. Zvi Drezner, 2010. "On the unboundedness of facility layout problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 72(2), pages 205-216, October.
    12. Nyberg, Axel & Westerlund, Tapio, 2012. "A new exact discrete linear reformulation of the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 220(2), pages 314-319.
    13. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.
    14. Jingyang Zhou & Peter E.D. Love & Kok Lay Teo & Hanbin Luo, 2017. "An exact penalty function method for optimising QAP formulation in facility layout problem," International Journal of Production Research, Taylor & Francis Journals, vol. 55(10), pages 2913-2929, May.
    15. Zvi Drezner & Jack Brimberg & Nenad Mladenović & Said Salhi, 2015. "Solving the planar p-median problem by variable neighborhood and concentric searches," Journal of Global Optimization, Springer, vol. 63(3), pages 501-514, November.
    16. Zhuoxuan Jiang & Xinyuan Zhao & Chao Ding, 2021. "A proximal DC approach for quadratic assignment problem," Computational Optimization and Applications, Springer, vol. 78(3), pages 825-851, April.
    17. Huizhen Zhang & Cesar Beltran-Royo & Liang Ma, 2013. "Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers," Annals of Operations Research, Springer, vol. 207(1), pages 261-278, August.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Loiola, Eliane Maria & de Abreu, Nair Maria Maia & Boaventura-Netto, Paulo Oswaldo & Hahn, Peter & Querido, Tania, 2007. "A survey for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 176(2), pages 657-690, January.
    2. Zvi Drezner, 2003. "A New Genetic Algorithm for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 320-330, August.
    3. Mouhamadou A. M. T. Baldé & Serigne Gueye & Babacar M. Ndiaye, 2021. "A greedy evolutionary hybridization algorithm for the optimal network and quadratic assignment problem," Operational Research, Springer, vol. 21(3), pages 1663-1690, September.
    4. Vittorio Maniezzo, 1999. "Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 358-369, November.
    5. Stutzle, Thomas, 2006. "Iterated local search for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1519-1539, November.
    6. Hahn, Peter M. & Kim, Bum-Jin & Stutzle, Thomas & Kanthak, Sebastian & Hightower, William L. & Samra, Harvind & Ding, Zhi & Guignard, Monique, 2008. "The quadratic three-dimensional assignment problem: Exact and approximate solution methods," European Journal of Operational Research, Elsevier, vol. 184(2), pages 416-428, January.
    7. Michel Gendreau & Jean-Yves Potvin, 2005. "Metaheuristics in Combinatorial Optimization," Annals of Operations Research, Springer, vol. 140(1), pages 189-213, November.
    8. T. G. Pradeepmon & Vinay V. Panicker & R. Sridharan, 2021. "A variable neighbourhood search enhanced estimation of distribution algorithm for quadratic assignment problems," OPSEARCH, Springer;Operational Research Society of India, vol. 58(1), pages 203-233, March.
    9. Luca Maria Gambardella & Marco Dorigo, 2000. "An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 237-255, August.
    10. Hao Hu & Renata Sotirov, 2021. "The linearization problem of a binary quadratic problem and its applications," Annals of Operations Research, Springer, vol. 307(1), pages 229-249, December.
    11. Mario Inostroza-Ponta & Regina Berretta & Pablo Moscato, 2011. "QAPgrid: A Two Level QAP-Based Approach for Large-Scale Data Analysis and Visualization," PLOS ONE, Public Library of Science, vol. 6(1), pages 1-18, January.
    12. Peter Hahn & J. MacGregor Smith & Yi-Rong Zhu, 2010. "The Multi-Story Space Assignment Problem," Annals of Operations Research, Springer, vol. 179(1), pages 77-103, September.
    13. Warren Adams & Hanif Sherali, 2005. "A Hierarchy of Relaxations Leading to the Convex Hull Representation for General Discrete Optimization Problems," Annals of Operations Research, Springer, vol. 140(1), pages 21-47, November.
    14. Yuelin Shen, 2008. "Reactive Tabu Search in a Team-Learning Problem," INFORMS Journal on Computing, INFORMS, vol. 20(4), pages 500-509, November.
    15. Eduardo G. Pardo & Mauricio Soto & Christopher Thraves, 2015. "Embedding signed graphs in the line," Journal of Combinatorial Optimization, Springer, vol. 29(2), pages 451-471, February.
    16. Yichuan Ding & Henry Wolkowicz, 2009. "A Low-Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 1008-1022, November.
    17. Jean-François Cordeau & Manlio Gaudioso & Gilbert Laporte & Luigi Moccia, 2006. "A Memetic Heuristic for the Generalized Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 18(4), pages 433-443, November.
    18. Bolte, Andreas & Thonemann, Ulrich Wilhelm, 1996. "Optimizing simulated annealing schedules with genetic programming," European Journal of Operational Research, Elsevier, vol. 92(2), pages 402-416, July.
    19. Rostami, Borzou & Malucelli, Federico & Belotti, Pietro & Gualandi, Stefano, 2016. "Lower bounding procedure for the asymmetric quadratic traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 253(3), pages 584-592.
    20. Burkard, Rainer E. & Cela, Eranda, 1995. "Heuristics for biquadratic assignment problems and their computational comparison," European Journal of Operational Research, Elsevier, vol. 83(2), pages 283-300, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:139:y:2005:i:1:p:65-94:10.1007/s10479-005-3444-z. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.