  The bilinear assignment problem (BAP) is a generalization of the well-known
quadratic assignment problem (QAP). In this paper, we study the problem from
the computational analysis point of view. Several classes of neigborhood
structures are introduced for the problem along with some theoretical analysis.
These neighborhoods are then explored within a local search and a variable
neighborhood search frameworks with multistart to generate robust heuristic
algorithms. Results of systematic experimental analysis have been presented
which divulge the effectiveness of our algorithms. In addition, we present
several very fast construction heuristics. Our experimental results disclosed
some interesting properties of the BAP model, different from those of
comparable models. This is the first thorough experimental analysis of
algorithms on BAP. We have also introduced benchmark test instances that can be
used for future experiments on exact and heuristic algorithms for the problem.
