Heuristic Approaches to Stochastic Quadratic Assignment Problem: VaR and CVar Cases
Abstract
The goal of this paper is to continue our investigation of the heuristic approaches of solving the
stochastic quadratic assignment problem (StoQAP) and provide additional insight into the behavior of di erent
formulations that arise through the stochastic nature of the problem. The deterministic Quadratic Assignment
Problem (QAP) belongs to a class of well-known hard combinatorial optimization problems. Working with several
real-world applications we have found that their QAP parameters can (and should) be considered as stochastic
ones. Thus, we review the StoQAP as a stochastic program and discuss its suitable deterministic reformulations.
The two formulations we are going to investigate include two of the most used risk measures - Value at Risk
(VaR) and Conditional Value at Risk (CVaR). The focus is on VaR and CVaR formulations and results of test
computations for various instances of StoQAP solved by a genetic algorithm, which are presented and discussed.
References
Bazaraa, M. S., Jarvis, J. J. and Sherali, H. D.: Linear programming and network flows, John Wiley and Sons, New York (1990)
Bazaraa, M.S., Sherali, H.D., and Shetty, C.M. : Nonlinear Programming: Theory and Apllications. John Wiley and Sons (1993)
Birge, J. R., Ho, J. K.: The Stochastic Dynamic Traffic Assignment Problem. Technical Report 87-16, Ann Arbor, University of Michigan, USA (1987)
Birge, J. R. and Louveaux, F.: Introduction to Stochastic Programming. 2nd ed. New York: Springer (2011) [5] Brent, R. P.: Note on Marsaglia’s Xorshift Random Number Generators. Journal of Statistical Software,
(5) (2004)
Cela, E.: The quadratic assignment problem: Theory and algorithms. In Combinatorial Optimization, Du D.Z. and Pardalos P. eds., Kluwer Academic Publishers, Dordrecht (1998)
Kall, P. and Wallace, S.W. Stochastic Programming. 1st ed., Wiley and Sons, New York (1994)
Koopmans, T.C. and Beckman, M.: Assignment problems and the location of economic activities. Econometric Vol. 25, 53-76 (1957)
L´anikov´a, I. et al.: Optimized design of concrete structures considering environmental aspects. Advances in Structural Engineering 17(4), 495–511 (2014)
Li, W.-J. and Smith, J. M.: Stochastic quadratic assignment problems. In Quadratic Assignment and Related Problems. Pardalos, P. M. and Wolkowicz, H. eds. DIMACS workshop, 221-236 (1993)
Li, Y., Pardalos, P. M., Resende, M. C. G.: A greedy randomized adaptive search procedure for the quadratic assignment problem. In Pardalos P. and Wolkowicz, H. eds., Quadratic assignment and related problems, vol. 16, 237-261 (1994)
Marsaglia, G.: Xorshift RNGs. Journal of Statistical Software 8(14) (2003)
Matousek R.: HC12: The Principle of CUDA Implementation. In Proceedings of the 16th International Conference on Soft Computing MENDEL 2010, Brno, 303-308 (2010)
Matousek R.: HC12: GAHC Improved Genetic Algorithm. In Nature Inspired Cooperative Strategies for Optimization (NICSO 2007), Springer Verlag (2007)
Matousek, R., and Zampachov´a, E.: Promising GAHC and HC12 algorithms in global optimization tasks. Optimization Methods & Software 26(3), 405–419 (2011)
Matousek, R., Popela, P.: Stochastic Quadratic Assignment problem: EV and EO reformulations solved by HC12. In Proceedings of the 20th International Conference on Soft Computing MENDEL 2014, pp. 13–20 (2014)
Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs. 3rd ed. New York: Springer (1996)
Mills, P.: Extensions to Guided Local Search. PhD Thesis, Department of Computer Science, University of Essex (2002)
Misevicius, A.: A modified simulated annealing algorithm for the quadratic assignment problem. Informatica, Vol. 14, 497-514 (2003)
Pardalos P.M., Rendl F. and Wolkowicz H.: The quadratic assignment problem: a survey of recent developments (1994)
P.M. Pardalos and H. Wolkowitz (eds.): Novel Approaches to Hard Discrete Optimization, AMS (2003)
Pavlas, M. et al.: Waste incineration with production of clean and reliable energy. Clean Technologies and Environmental Policy. Vol. 13, No. 4, 595-605 (2011)
Pflug, G.C. and Romisch, W.: Modeling, measuring and managing risk. Hackensack, N.J.: World Scientific (2007)
Pluhacek, M., Senkerik, R., and Zelinka, I.: ˇ Particle swarm optimization algorithm driven by multichaotic number generator. Soft Computing 18(4), 631–639 (2014)
Popela, P.: An Objected-Oriented Approach to Multistage Stochastic Programming. PhD Thesis, Prague: Charles University (1998)
Popela, P., Matousek, R. and Kudela, J.: Heuristic approaches to stochastic quadratic assignment problem: VO and MM cases. In Proceedings of the 22nd International Conference on Soft Computing MENDEL 2016, Brno, 117-122 (2016)
Resende, M.G.C., Ramakrishnan, K.G. and Drezner Z.: Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming. Operations Research Vol. 43, 781-791 (1995)
Rhee, W. T.: Stochastic Analysis of the Quadratic Assignment Problem. Mathematics of Operations Research, Vol. 16, No. 2, 223-239 (1991)
Ruszczy´nski, A., and Shapiro, A: Stochastic Programming (Handbooks in Operations Research and Management Science). Elsevier (2003)
Sahni, S. and Gonzalez, T.: P-complete Approximation Problems. Journal of the ACM 23, 1976, 555-565 (1976)
Smith, J. M., Li, W.-J.: Quadratic Assignment Problems and M/G/C/C/ State Dependent Network Flows. Journal of Combinatorial Optimization, Vol. 5, No. 4, 421-443 (2001)
Li, Wu-Ji J. and MacGregor Smith, J.: An algorithm for Quadratic Assignment Problems, EJOR, Vol. 81, 205-216 (1995)
Senkerik, R., Pluhacek, M., Davendra, D., Zelinka, I., and Janostik, J.: New adaptive approach for multichaotic differential evolution concept. Hybrid Artificial Intelligent Systems, 234–243, Springer International Publishing (2015)
Stetina, J. et al.: Final Structure Prediction of Continuously Cast Billets. Materiali in Tehnologije, Vol. 46, No. 2, 155-160 (2012)
Soustek, P., Matousek, R., Dvorak, J., and Bednar, J.: Canadian traveller problem: A solution using ant colony optimization. 19th International Conference on Soft Computing MENDEL 2013, 439–444. Brno, Czech Republic (2013)
Stepanek, P., Lanikov´a, I., Simunek, P., and Girgle, F.: Probability based optimized design of concrete structures. In Life-Cycle and Sustainability of Civil Infrastructure System. London, Taylor & Francis Group, 2345–2350 (2012)
Stetina, J., Klimes, L., Mauder, T., and Kavicka, F.: Final-structure prediction of continuously cast billets. Materiali in tehnologije 46(2), 155–160 (2012)
Sabartov´a, Z., and Popela, P.: ˇ Beam design optimization model with FEM based constraints. 18th International Conference on Soft Computing, MENDEL 2012; Brno; Czech Republic, (2012)
Yifei Zhao, Y. and Wallace, S. W. : Integrated facility layout design and flow assignment problem under uncertainty. INFORMS Journal on Computing manuscript JOC-2013-01-OA-014 (2014).
Yifei Zhao, Y. and Wallace, S. W. : A heuristic for the single-product capacitated facility layout problem with random demand. Published online 20 May, 2014 in EURO J Transp Logist (2014)
MENDEL open access articles are normally published under a Creative Commons Attribution-NonCommercial-ShareAlike (CC BY-NC-SA 4.0) https://creativecommons.org/licenses/by-nc-sa/4.0/ . Under the CC BY-NC-SA 4.0 license permitted 3rd party reuse is only applicable for non-commercial purposes. Articles posted under the CC BY-NC-SA 4.0 license allow users to share, copy, and redistribute the material in any medium of format, and adapt, remix, transform, and build upon the material for any purpose. Reusing under the CC BY-NC-SA 4.0 license requires that appropriate attribution to the source of the material must be included along with a link to the license, with any changes made to the original material indicated.
