On the biquadratic assignment problem
Rainer E. Burkard, Eranda Çela, Bettina Klinz · DIMACS series in discrete mathematics and theoretical computer science · 1994
Motivated by a problem arising in VLSI synthesis we introduce the biquadratic assignment problem (BQAP) which generalizes the wellknown quadratic assignment problem (QAP). The BQAP is to minimize a weighted sum of products of four variables subject to assignment constraints on the variables. We give two integer programming formulations for the problem and design lower bounds for the optimal solution value. These lower bounds are tested computationally on BQAP instances with known objective function value. Finally the asymptotic behaviour of BQAPs is analyzed. It turns out that the ratio between the best and the worst objective function values tends in probability to one when the size of the problem tends to infinity.