Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms

Vladyslav Sokol (), Ante Ćustić (), Abraham P. Punnen () and Binay Bhattacharya ()
Additional contact information
Vladyslav Sokol: School of Computing Science, Simon Fraser University, Surrey, British Columbia V3T 0A3, Canada
Ante Ćustić: Department of Mathematics, Simon Fraser University, Surrey, British Columbia V3T 0A3, Canada
Abraham P. Punnen: School of Management, Northwestern Polytechnical University, 710072 Xi’an, China; Department of Mathematics, Simon Fraser University, Surrey, British Columbia V3T 0A3, Canada
Binay Bhattacharya: School of Computing Science, Simon Fraser University, Surrey, British Columbia V3T 0A3, Canada

INFORMS Journal on Computing, 2020, vol. 32, issue 3, 730-746

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

Keywords: nonlinear assignment problems; average solution value; domination analysis; heuristics; local search; exponential neighborhoods; variable neighborhood search (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0893 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:3:i:2020:p:730-746

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().