Research Article Open Access

Two Reformulations for the Dynamic Quadratic Assignment Problem

Sirirat Muenvanichakul and Peerayuth Charnsethikul

Abstract

Problem statement: The Dynamic Quadratic Assignment Problem (DQAP), an NP-hard problem, is outlined and reformulated in two alternative models: Linearized model and logic-based model. Approach: The solution methods for both models based on combinatorial methods (Benders’ Decomposition and Approximate Dynamic Programming) and constraint logic programming, respectively, are proposed. Results: Proofs of model equivalence and solution methodology are presented. Conclusion: Both proposed models are more simplified leading to possible hybrid adaptations of existing techniques for more practical approaches.

Journal of Mathematics and Statistics
Volume 6 No. 4, 2010, 449-453

DOI: https://doi.org/10.3844/jmssp.2010.449.453

Submitted On: 28 July 2010 Published On: 31 December 2010

How to Cite: Muenvanichakul, S. & Charnsethikul, P. (2010). Two Reformulations for the Dynamic Quadratic Assignment Problem. Journal of Mathematics and Statistics, 6(4), 449-453. https://doi.org/10.3844/jmssp.2010.449.453

  • 3,584 Views
  • 4,190 Downloads
  • 0 Citations

Download

Keywords

  • DQAP
  • linearized model
  • logic-based model
  • Benders
  • decomposition
  • dynamic programming
  • constraint logic programming