A New Branch-and-Bound Solver for the Quadratic Assignment Problem Based on the Level-3 Reformulation-Linearization Technique.
Rattachement africain : us. Niveau de preuve : code pays fourni par la source.
Le résumé fourni par la source
We report on the implementation of a level-3 reformulation linearization technique (RLT-3)-based bound calculation in a branch-and-bound algorithm. The RLT-3-based bound calculation method is not guaranteed to calculate the RLT-3 lower bound exactly, but approximates it very closely and reaches it in some instances. We tested the new branch-andbound solver on six Nugent instances, 15, 18, 20, 22, 24 and 25. The computational results indicate that the new technique should be effective in solving problem sizes larger than had been possible to date. Solving QAP problems sizes larger than size 25 with this new exact solution technique still presents a challenge due to the large memory needed to implement the RLT-3 formulation. We discuss our plans to improve the implementation of the algorithm.
Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.
Le contrôle bibliographique ouvert
Où se fait cette recherche
-
California University of Pennsylvania pays non établi dans la noticeUniversité ou école supérieure
-
University of Pennsylvania pays non établi dans la noticeUniversité ou école supérieure
-
Clemson University pays non établi dans la noticeUniversité ou école supérieure
California University of Pennsylvania, University of Pennsylvania et Clemson University.
Une affiliation ne permet pas de déduire la nationalité d’un auteur.