摘要
The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite convergence is developed forsolving the semi-Lagrangian dual problem associated to the QAP.We perform computational experiments on 30 moderately difficultQAP instances by using the mixed integer programming solvers,Cplex, and SLR＋Cplex, respectively. The numerical results notonly further illustrate that the SLR and the developed dual ascentalgorithm can be used to solve the QAP reasonably, but also disclosean interesting fact： comparing with solving the unreducedproblem, the reduced oracle problem cannot be always effectivelysolved by using Cplex in terms of the CPU time.
The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite convergence is developed forsolving the semi-Lagrangian dual problem associated to the QAP.We perform computational experiments on 30 moderately difficultQAP instances by using the mixed integer programming solvers,Cplex, and SLR＋Cplex, respectively. The numerical results notonly further illustrate that the SLR and the developed dual ascentalgorithm can be used to solve the QAP reasonably, but also disclosean interesting fact： comparing with solving the unreducedproblem, the reduced oracle problem cannot be always effectivelysolved by using Cplex in terms of the CPU time.
作者
huizhen zhang
cesar beltran-royo
bo wang
liang ma
ziying zhang
Huizhen Zhang Cesar Beltran-Royo Bo Wang Liang Ma Ziying Zhang(School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China Department of Statistics and Operations Research, Rey Juan Carlos University, Mostoles （Madrid） 28933, Spain School of Materials Engineering, Shanghai University of Engineering Science, Shanghai 201620, China)
基金
supported by the National Natural Science Foundation of China(71401106)
the Innovation Program of Shanghai Municipal Education Commission(14YZ090)
the Shanghai Natural Science Foundation(14ZR1418700)
the Shanghai First-class Academic Discipline Project(S1201YLXK)
the Hujiang Foundation of China(A14006)
the grant S2009/esp-1594 from the Comunidad de Madrid(Spain)
the grant MTM2012-36163-C06-06 from the Spanish government
