Research Article Open Access

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

  • Sirirat Muenvanichakul
  • Peerayuth Charnsethikul

Journal of Computer Science
Volume 5 No. 1, 2009, 64-70
DOI: 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.

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

Download

Keywords

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