Learning for Optimization with Virtual Savant
DOI:
https://doi.org/10.36561/ING.22.4Keywords:
Machine learning, Optimization, Next release problem, Heterogeneous computing scheduling problem, Bus synchronization problemAbstract
Optimization problems arising in multiple fields of study demand efficient algorithms that can exploit modern parallel computing platforms. The remarkable development of machine learning offers an opportunity to incorporate learning into optimization algorithms to efficiently solve large and complex problems. This article explores Virtual Savant, a paradigm that combines machine learning and parallel computing to solve optimization problems. Virtual Savant is inspired in the Savant Syndrome, a mental condition where patients excel at a specific ability far above the average. In analogy to the Savant Syndrome, Virtual Savant extracts patterns from previously-solved instances to learn how to solve a given problem in a massively-parallel fashion. In this article, Virtual Savant is applied to three optimization problems related to software engineering, task scheduling, and public transportation. The efficacy of Virtual Savant is evaluated in different computing platforms and the experimental results are compared against exact and approximate solutions for both synthetic and realistic instances of the studied problems. Results show that Virtual Savant can find accurate solutions, effectively scale in the problem dimension, and take advantage of the availability of multiple computing resources.
Downloads
References
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti, A., and Protasi, M. (2012). Complexityand approximation: Combinatorial optimization problems and their approximability properties. Springer Science & Business Media.
Golub, G. H. and Ortega, J. M. (2014). Scientific computing: an introduction with parallel computing.Elsevier.
Darte, A., Robert, Y., and Vivien, F. (2012). Scheduling and automatic parallelization. Springer Science& Business Media.
Golub, G. H. and Ortega, J. M. (2014). Scientific computing: an introduction with parallel computing. Elsevier.
Vlastelica, M., Paulus, A., Musil, V., Martius, G., and Rolıń ek, M. (2020). Differentiation of blackboxcombinatorial solvers. In International Conference on Learning Representations.
Vinyals, O., Fortunato, M., and Jaitly, N. (2015). Pointer Networks. In Advances in Neural InformationProcessing Systems 28, pages 2692–2700.
Pinel, F., Dorronsoro, B., Bouvry, P., and Khan, S. (2013). Savant: Automatic parallelization of ascheduling heuristic with machine learning. In World Congress on Nature and Biologically Inspired Computing, pages 52–57.
Treffert, D. (2006). Extraordinary People: Understanding Savant Syndrome. Iuniverse.
Pring, L. (2005). Savant talent. Developmental medicine and child neurology, 47(7):500–503.
Heaton, P. and Wallace, G. L. (2004). Annotation: The savant syndrome. Journal of child psychologyand psychiatry, 45(5):899–911.
Bagnall, A., Rayward, V., and Whittley, I. (2001). The next release problem. Information and SoftwareTechnology, 43(14):883–890.
Kellerer, H., Pferschy, U., and Pisinger, D. (2004). Springer.
Nemhauser, G. L. and Ullmann, Z. (1969). Discrete Dynamic Programming and Capital Allocation.Management Science, 15(9):494–505.
Harman, M., Krinke, J., Medina-Bulo, I., Palomo, F., Ren, J., and Yoo, S. (2014). Exact scalablesensitivity analysis for the next release problem. ACM Transactions on Software Engineering and Methodology, 23(2):1–31.
Massobrio, R., Nesmachnow, S., Palomo-Lozano, F., and Dorronsoro, B. (2021). Virtual savant as ageneric learning approach applied to the basic independent next release problem. Applied Soft Computing, 108:107374.
Massobrio, R., Nesmachnow, S., and Dorronsoro, B. (2018c). Support Vector Machine Acceleration forIntel Xeon Phi Manycore Processors. In High Performance Computing Latin America Conference, pages 277–290.
Luo, P., Lü, K., and Shi, Z. (2007). A revisit of fast greedy heuristics for mapping a class of independenttasks onto heterogeneous computing systems. Journal of Parallel and Distributed Computing, 67(6):695–714.
de la Torre, J. C., Massobrio, R., Ruiz, P., Nesmachnow, S., and Dorronsoro, B. (2020). Parallel virtualsavant for the heterogeneous computing scheduling problem. Journal of Computational Science, 39:101048.
International Transport Forum (2014). Valuing Convenience in Public Transport. OECD Publishing.
Nesmachnow, S., Muraña, J., Goñi, G., Massobrio, R., and Tchernykh, A. (2020). EvolutionaryApproach for Bus Synchronization. In High Performance Computing Latin America Conference, pages 320–336.
Massobrio, R., Nesmachnow, S., Muraña, J., and Dorronsoro, B. (2022). Learning to optimize timetables for efficient transfers in public transportation systems. Applied Soft Computing, 119:108616.
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Renzo Massobrio
This work is licensed under a Creative Commons Attribution 4.0 International License.
