Loading...
Please wait, while we are loading the content...
Similar Documents
Solving the Quadratic Assignment Problem Using Semi-Lagrangian Relaxation
| Content Provider | Semantic Scholar |
|---|---|
| Author | Zhang, Huizhen Beltran-Royo, Cesar Wang, Bo Ma, Liang Zhang, Ziying |
| Copyright Year | 2016 |
| 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 have performed 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://grafo.etsii.urjc.es/~cbeltran/16SLR_QAP.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
