Iterated Local Search: Quadratic Assignment Problem
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.

Iterated Local Search: Quadratic Assignment Problem

Shalin Shah

Implementation of iterative local search for the quadratic assignment problem (C++). The QAP is a strongly NP-hard problem, and solving instances with more than 20 variables is considered intractable. The implementation uses a population of individuals and performs local improvement on them. Local improvement accepts worse solutions with a probability of 0.0. The parameters of the algorithm can be adjusted by changing the global variables. The algorithm can be used to find approximate solutions for large QAP instances for which exact methods are not suitable. (The code finds optimal solutions to all nugXX instances in a few seconds)

Instances are available at QAPLIB. (The code includes a parser for the QAPLIB format).

Cite this code:

Shalin Shah, 2012, "Implementation of iterative local search (ILS) for the quadratic assignment problem"

Cited By:

  • Kanduc, T. “Optimisation of factory floor layout in a complex manufacturing process.” (2014).
  • Kanduc, T., and B. Rodic. "Optimisation of machine layout using a force generated graph algorithm and simulated annealing." International Journal of Simulation Modelling 15.2 (2016): 275-287.
  • Rodic, B., and T. Kanduc. "Optimisation of a complex manufacturing process using discrete event simulation and a novel heuristic algorithm." International Journal of Mathematical Models and Methods in Applied Sciences 9 (2015): 320-329.
  • Truetsch, Uwe. A semidefinite programming based branch-and-bound framework for the quadratic assignment problem. CentER, Tilburg University, 2014.
  • Manufacturing processes optimisation in a furniture factory (ITIS 2014)