Informatica logo


Login Register

  1. Home
  2. Issues
  3. Volume 3, Issue 4 (1992)
  4. A local search algorithm for the quadrat ...

Informatica

Information Submit your article For Referees Help ATTENTION!
  • Article info
  • Related articles
  • More
    Article info Related articles

A local search algorithm for the quadratic assignment problem
Volume 3, Issue 4 (1992), pp. 524–538
Kowtha A. Murthy   Yong Li   Panos M. Pardalos  

Authors

 
Placeholder
https://doi.org/10.3233/INF-1992-3405
Pub. online: 1 January 1992      Type: Research Article     

Published
1 January 1992

Abstract

In this paper, we present a new local search algorithm for solving the Quadratic Assignment Problem based on the Kernighan-Lin heuristic for the Graph Partitioning Problem. We also prove that finding a local optimum for the Quadratic Assignment Problem, with the neighborhood structure defined in the algorithm, is PLS-complete. The greatest advantages of the algorithm are its simplicity and speed in generating high quality solutions. The algorithm has been implemented and tested on an IBM 3090 computer with a variety of test problems of dimensions up to 100, including many test problems available in the literature and a new set of test problems with known optimal permutations.

Related articles PDF XML
Related articles PDF XML

Copyright
No copyright data available.

Keywords
analysis of algorithms: computational complexity suboptimal algorithms facilities/equipment planning: discrete location combinatorial optimization graph partitioning polynomial-time local search

Metrics
since January 2020
641

Article info
views

0

Full article
views

647

PDF
downloads

191

XML
downloads

Export citation

Copy and paste formatted citation
Placeholder

Download citation in file


Share


RSS

INFORMATICA

  • Online ISSN: 1822-8844
  • Print ISSN: 0868-4952
  • Copyright © 2023 Vilnius University

About

  • About journal

For contributors

  • OA Policy
  • Submit your article
  • Instructions for Referees
    •  

    •  

Contact us

  • Institute of Data Science and Digital Technologies
  • Vilnius University

    Akademijos St. 4

    08412 Vilnius, Lithuania

    Phone: (+370 5) 2109 338

    E-mail: informatica@mii.vu.lt

    https://informatica.vu.lt/journal/INFORMATICA
Powered by PubliMill  •  Privacy policy