Virtual Savant for the Knapsack Problem: learning for automatic resource allocation
https://doi.org/10.15514/ISPRAS-2019-31(2)-2
Abstract
This article presents the application of Virtual Savant to solve resource allocation problems, a widely-studied area with several real-world applications. Virtual Savant is a novel soft computing method that uses machine learning techniques to compute solutions to a given optimization problem. Virtual Savant aims at learning how to solve a given problem from the solutions computed by a reference algorithm, and its design allows taking advantage of modern parallel computing infrastructures. The proposed approach is evaluated to solve the Knapsack Problem, which models different variant of resource allocation problems, considering a set of instances with varying size and difficulty. The experimental analysis is performed on an Intel Xeon Phi many-core server. Results indicate that Virtual Savant is able to compute accurate solutions while showing good scalability properties when increasing the number of computing resources used.
Keywords
virtual savant,
machine learning,
parallel computing,
resource allocation,
knapsack problem,
many-core
Supporting agencies: The work of Renzo Massobrio and Sergio Nesmachnow is partly supported by ANII and PEDECIBA, Uruguay. The work of Renzo Massobrio is partly supported by Fundación Carolina, Spain. Bernabé Dorronsoro acknowledges the Spanish MINECO and ERDF for the support provided under contracts TIN2014-60844-R (the SAVANT project) and RYC-2013-13355
About the Authors
Renzo Massobrio
Universidad de la República
Uruguay
Teaching and research assistant at the Faculty of Engineering
Uruguay
Teaching and research assistant at the Faculty of Engineering
Bernabé Dorronsoro Díaz
University of Cadiz
Spain
Researcher assistant at the Computer Science Engineering Department
Spain
Researcher assistant at the Computer Science Engineering Department
Sergio Enrique Nesmachnow Cánovas
Universidad de la República
Uruguay
Aggregate Professor at the Numerical Center (CeCal) at Computer Science Institute, Engineering Faculty
Uruguay
Aggregate Professor at the Numerical Center (CeCal) at Computer Science Institute, Engineering Faculty
References
1. . Luss H. Equitable Resource Allocation. John Wiley & Sons, Inc., 2012.
2. . Vanderster D. C. Resource Allocation and Scheduling Strategies Using Utility and the Knapsack Problem on Computational Grids. PhD thesis, Victoria, B.C., Canada, 2008.
3. . Pinel F., Dorronsoro B., Bouvry, and Khan S. Savant: Automatic parallelization of a scheduling heuristic with machine learning. In Proc. of the World Congress on Nature and Biologically Inspired Computing, 2013, pp. 52–57.
4. . Treffert D. The savant syndrome: an extraordinary condition. A synopsis: past, present, future. Philosophical Transactions of the Royal Society B: Biological Sciences, vol. 364, no. 1522, 2009, pp.1351–1357.
5. . Treffert D. Extraordinary People: Understanding Savant Syndrome. iUniverse, 2006.
6. . Bouvet L., Donnadieu S., Valoptdois S., Caron C., Dawson M., and Mottron L. Veridical mapping in savant abilities, absolute pitch, and synesthesia: an autism case study. Frontiers in Psychology, vol. 5, no.106, 2014.
7. . Pinel F., Dorronsoro B., and Bouvry P. The virtual savant: Automatic generation of parallel solvers. Information Sciences, vol. 432, 2018, pp. 411–430.
8. . Massobrio R., Dorronsoro B., Palomo-Lozano F., Nesmachnow S., and Pinel F. Generación automática de programas: Savant Virtual para el problema de la mochila. In XI Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados, pages 1–10, 2016.
9. . Massobrio R., Dorronsoro B., Nesmachnow S., and Palomo-Lozano F. Automatic program generation: Virtual savant for the knapsack problem. In Proc. of the International Workshop on Optimization and Learning, 2018, pp. 1–2
10. . Kellerer H., Pferschy U., and Pisinger D. Knapsack Problems. Springer, 2004.
11. . Pinel F. and Dorronsoro B. Savant: Automatic Generation of a Parallel Scheduling Heuristic for Map-Reduce. International Journal of Hybrid Intelligent Systems, vol. 11, no. 4, 2014, pp. 287–302.
12. . Nemhauser G. L. and Ullmann Z. Discrete dynamic programming and capital allocation. Management Science, vol. 15, no. 9, 1969, pp. 494–505.
13. . Harman M., Krinke J., Medina-Bulo I., Palomo F., Ren J., and Yoo S.. Exact scalable sensitivity analysis for the next release problem. ACM Transactions on Software Engineering and Methodology, vol. 23, no. 2, 2014, pp. 1–31.
14. . Bagnall A., Rayward-Smith V., and Whittley I. The next release problem. Information and Software Technology, vol. 43, no. 14, 2001, pp. 883–890.
15. . Vinyals O., Fortunato M., and Jaitly N. Pointer networks. In Advances in Neural Information Processing Systems 28, pp. 2692–2700, 2015.
16. . Hu H., Zhang X., Yan X., Wang L., and Xu Y. Solving a new 3d bin packing problem with deep reinforcement learning method. CoRR, abs/1708.05930, 2017.
17. . Dorronsoro B. and Pinel F. Combining machine learning and genetic algorithms to solve the independent tasks scheduling problem. In Proc. of the 3rd IEEE International Conference on Cybernetics, 2017, pp. 1–8.
18. . Massobrio R., Dorronsoro B., and Nesmachnow S. Virtual savant for the heterogeneous computing scheduling problem. In Proc. of the International Conference on High Performance Computing & Simulation, 2018 , pp. 1–7.
19. . Chang C.-C. and Lin C.-J. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, vol. 2, no. 27, 2011, pp. 1–27.
20. . Massobrio R., Nesmachnow S., and Dorronsoro B. Support Vector Machine Acceleration for Intel Xeon Phi Manycore Processors. In Proc. of the Latin America High Performance Computing Conference, 2017, pp. 1–14.
21. . Jeffers J., Reinders J., and Sodani A. Intel Xeon Phi Processor High Performance Programming: Knights Landing Edition. Elsevier Science, 2016.
22. . Rodríguez, S., Parodi, F., and Nesmachnow, S. Parallel evolutionary approaches for game playing and verification using Intel Xeon Phi. Journal of Parallel and Distributed Computing, 2018. DOI: 10.1016/j.jpdc.2018.07.010
Review
For citations:
Massobrio R., Dorronsoro Díaz B., Nesmachnow Cánovas S. Virtual Savant for the Knapsack Problem: learning for automatic resource allocation. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2019;31(2):21-31. https://doi.org/10.15514/ISPRAS-2019-31(2)-2
Email this article 