Journal of Computer Science

Benders' Decomposition Based Heuristics for Large-Scale Dynamic Quadratic Assignment Problems

Sirirat Muenvanichakul and Peerayuth Charnsethikul

DOI : 10.3844/jcssp.2009.64.70

Journal of Computer Science

Volume 5, Issue 1

Pages 64-70

Abstract

Problem statement: Dynamic Quadratic Assignment Problem (DQAP) is NP hard problem. Benders decomposition based heuristics method is applied to the equivalent mixed-integer linear programming problem of the original DQAP. Approach: Approximate Benders Decomposition (ABD) generates the ensemble of a subset of feasible layout for Approximate Dynamic Programming (ADP) to determine the sub-optimal optimal solution. A Trust-Region Constraint (TRC) for the master problem in ABD and a Successive Adaptation Procedure (SAP) were implemented to accelerate the convergence rate of the method. Results: The sub-optimal solutions of large-scales DQAPs from the method and its variants were compared well with other metaheuristic methods. Conclusion: Overall performance of the method is comparable to other metaheuristic methods for large-scale DQAPs.

Copyright

© 2009 Sirirat Muenvanichakul and Peerayuth Charnsethikul. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.