Mathematical Formulations for the Quadratic Assignment Problem with Rectilinear Distances

摘要

This study compares four mathematical formulations for the Rectilinear-Quadratic Assignment Problem (R-QAP), including the two existing R-QAP formulations, one new R-QAP formulations, and one of the best performing general QAP formulations. Although the R-QAP is a well-known NP-Complete problem, new insights for solving the problem might result from studying the mathematical formulations. The four formulations are compared with respect to their runtimes using AIMMS 3.12, which uses CPLEX 12.4 as a solver. The data used in the experiments includes some rectilinear instances from the QAPLIB, as well as several internally generated instances. It is concluded that the proposed formulation is a good compromise if only one model is to be selected.