Solution to the quadratic assignment problem using semi-lagrangian relaxation
School of Management, University of Shanghai for Science and Technology, Huizhen Zhang, C. Beltran‐Royo, Bo Wang, Ma Liang, Ziying Zhang, Department of Statistics and Operations Research, Rey Juan Carlos University, School of Materials Engineering, Shanghai University of Engineering Science · Journal of Systems Engineering and Electronics · 2016
The semi-Lagrangian relaxation (SLR), a new exact method for combinatorial optimization problems with equality constraints, is applied to the quadratic assignment problem (QAP). A dual ascent algorithm with finite convergence is developed for solving the semi-Lagrangian dual problem associated to the QAP. We perform computational experiments on 30 moderately difficult QAP instances by using the mixed integer programming solvers, Cplex, and SLR+Cplex, respectively. The numerical results not only further illustrate that the SLR and the developed dual ascent algorithm can be used to solve the QAP reasonably, but also disclose an interesting fact: comparing with solving the unreduced problem, the reduced oracle problem cannot be always effectively solved by using Cplex in terms of the CPU time.