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 probl em also for BiQAP, a reasonable effort to cope with the problem is try ing to derive heuristics which solve it suboptimally and which, possib ly, yield a good trade off between the solution quality and the time a nd memory requirements, In this paper we describe several heuristics f or BiQAPs, in particular pair exchange algorithms (improvement methods ) and variants of simulated annealing and taboo search. We implement t hese heuristics as C codes and analyze their performances.