Journal of Mathematics and Statistics

Two Reformulations for the Dynamic Quadratic Assignment Problem

Sirirat Muenvanichakul and Peerayuth Charnsethikul

DOI : 10.3844/jmssp.2010.449.453

Journal of Mathematics and Statistics

Volume 6, Issue 4

Pages 449-453

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.

Copyright

© 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.