Research Article Open Access

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

Sirirat Muenvanichakul1 and Peerayuth Charnsethikul1
  • 1 ,
Journal of Computer Science
Volume 5 No. 1, 2009, 64-70

DOI: https://doi.org/10.3844/jcssp.2009.64.70

Submitted On: 3 March 2009 Published On: 31 January 2009

How to Cite: Muenvanichakul, S. & Charnsethikul, P. (2009). Benders' Decomposition Based Heuristics for Large-Scale Dynamic Quadratic Assignment Problems . Journal of Computer Science, 5(1), 64-70. https://doi.org/10.3844/jcssp.2009.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.

  • 1,497 Views
  • 1,658 Downloads
  • 2 Citations

Download

Keywords

  • Dynamic quadratic assignment
  • benders decomposition
  • dynamic programming
  • trust region method