A GRASP for the biquadratic assignment problem

T. Mavridou, P.M. Pardalos, P.S. Pitsoulis, and M. G. C. Resende

European Journal of Operational Research, vol. 105, pp. 613-621, 1998.


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

Go back

Mauricio G.C. Resende's Home Page

Last modified: 22 November 1995

Copyright Notice