Journal of Systems Engineering and Electronics

• SYSTEMS ENGINEERING • Previous Articles     Next Articles

Solution to the quadratic assignment problem using semi-Lagrangian relaxation

Huizhen Zhang1,*, Cesar Beltran-Royo2, Bo Wang1, Liang Ma1, and Ziying Zhang3   

  1. 1. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China;
    2. Department of Statistics and Operations Research, Rey Juan Carlos University, Mostoles (Madrid) 28933, Spain;
    3. School of Materials Engineering, Shanghai University of Engineering Science, Shanghai 201620, China

  • Online:2016-10-25 Published:2010-01-03

Abstract:

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.