Redinv-SA: la simulated annealing for the quadratic assignment problem

¹ OPPE/UFRJ, CP 68.507, 21.945-970 Rio de Janeiro, RJ, Brazil.
² CEFET/RJ, Av. Maracana n 229, 20.271-110 Rio de Janeiro, RJ, Brazil.

Received: January 1996

Abstract

An algebraic and combinatorial approach to the study of the Quadratic Assignment Problem produced theoretical results that can be applied to (meta) heuristics to give them information about the problem structure, allowing the construction of algorithms. In this paper those results were applied to inform a Simulated Annealing-type heuristic (which we called RedInv-SA). Some results from tests with known literature instances are presented.

Résumé

Une étude algébrique et combinatoire du Problème d'Affectation Quadratique a produit des résultats théoriques qui peuvent être appliqués à des (meta)-heuristiques. Donnant des informations sur la structure du problème, ils conduisent de cette facon à la formulation d'algorithmes. Dans cet article, ces resultats ont été appliqués à l'information d'une heuristique de type Recuit Simule, appelée RedInv-SA. Des résultats de l'application de l'algorithme à des problèmes classiques de la litterature sont présentes à la fin de l'article.