JMSS Cover
Frequency: Continuous
ISSN: 1549-3644 (Print)
ISSN: 1558-6359 (Online)
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

Open AccessCopyright: © 2010 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.

  • 4,420 Views
  • 4,548 Downloads
  • 0 Citations

Download

Keywords

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