A GRASP FOR THE BIQUADRATIC ASSIGNMENT PROBLEM

The biquadratic assignment problem (BiQAP) is a generalization of the quadratic assignment problem (QAP). It is a nonlinear integer programm ing problem where the objective function is a fourth degree multivaria ble polynomial and the feasible domain is the assignment polytope. BiQ AP problems appear in VLSI synthesis. Due to the difficulty of this pr oblem, only heuristic solution approaches have been proposed. In this paper, we propose a new heuristic for the BiQAP, a greedy randomized a daptive search procedure (GRASP). Computational results on instances d escribed in the literature indicate that this procedure consistently f inds better solutions than previously described algorithms. (C) 1998 E lsevier Science B.V.