HEURISTICS FOR BIQUADRATIC ASSIGNMENT PROBLEMS AND THEIR COMPUTATIONAL COMPARISON

The biquadratic assignment problem (BiQAP) is a generalization of the quadratic assignment problem (QAP). As for any hard optimization problem also for BiQAP, a reasonable effort to cope with the problem is trying to derive heuristics which solve it suboptimally and which, possibly, yield a good trade off between the solution quality and the time and memory requirements, In this paper we describe several heuristics for BiQAPs, in particular pair exchange algorithms (improvement methods) and variants of simulated annealing and taboo search. We implement these heuristics as C codes and analyze their performances.