T. Mavridou, P.M. Pardalos, P.S. Pitsoulis, and M. G. C. Resende
European Journal of Operational Research, vol. 105, pp. 613-621, 1998.
ABSTRACT
The biquadratic assignment problem (BiQAP) is a
generalization of the quadratic assignment problem (QAP). It is a
nonlinear integer programming problem where the objective function is a
fourth degree multivariable polynomial and the feasible domain is the
assignment polytope. BiQAP problems appear in VLSI
synthesis. Due to the difficulty of this problem, only heuristic
solution approaches have been proposed. In this paper, we propose
a new heuristic for the BiQAP, a greedy randomized adaptive search
procedure (GRASP). Computational results on instances described in the
literature indicate that this procedure consistently finds better
solutions than previously described algorithms.
PostScript file of full paper