Two Reformulations for the Dynamic Quadratic Assignment Problem
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.
DOI: https://doi.org/10.3844/jmssp.2010.449.453
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.
- 4,122 Views
- 4,389 Downloads
- 0 Citations
Download
Keywords
- DQAP
- linearized model
- logic-based model
- Benders
- decomposition
- dynamic programming
- constraint logic programming