Combinatorial instruments in the design of a heuristic for the quadratic assignment problem

This work discusses the use of a neighbouring structure in the design of specific heuristics for the Quadratic Assignment Problem (QAP). This structure is formed by the 4- and 6-cycles adjacent to a vertex in the Hasse diagram of the permutation lattice and it can be adequately partitioned in subsets of linear and quadratic cardinalities, a characteristic which frequently allows an economy in the processing time. We propose also a restart strategy and a mechanism for generating initial solutions which constitute, together with the neighbouring structure, a possible QAP-specific heuristic proposal. For the construction of these instruments we used the relaxed ordered set of QAP solutions.