Deepak Ajwani - Learning-to-Prune

Описание: Part of Discrete Optimization Talks: https://talks.discreteopt.com

Deepak Ajwani - University College Dublin

Learning-to-Prune: A Lightweight Supervised Learning Technique for Solving Combinatorial Optimization Problems

Speaker webpage: https://people.ucd.ie/deepak.ajwani

Abstract: I will present a lightweight supervised learning technique for solving combinatorial optimization problems that we refer to as learning-to-prune. In contrast to the end-to-end machine learning techniques that attempt to solve optimization problems completely, the goal of the learning-to-prune is merely to predict values for a subset of variables with high confidence. The remaining problem is then solved using the classical optimization techniques. Thus, learning-to-prune speeds-up the solution of the optimization problems. The key advantages of the learning-to-prune framework are that (i) it requires very little training data, (ii) it is easier to integrate algorithmic insights into the learning and (iii) even simple (more interpretable) classification models are quite effective in this framework. We show that this simple approach performs surprisingly well in practice. We consider a range of classical combinatorial optimization problems -- k-median, set cover, max coverage, uncapacitated facility location, Steiner tree problem on graphs, and nurse rostering problems -- and show that this framework provides near-optimal solutions considerably faster than commercial ILP solvers and approximation algorithms on benchmark instances. We also demonstrate a bootstrapping approach to further boost the performance of this technique for large problem instances.
Bio: Dr. Deepak Ajwani is an Assistant Professor at the School of Computer Science, University College Dublin. His research interests include algorithm engineering, combinatorial optimisation and machine learning. He is a funded investigator with the Science Foundation Ireland Centre for Research Training in Machine Learning (ML-Labs). His Postdoctoral research (2010-2012) was supported by a funding award from the Irish Research Council for Science, Engineering and Technology and IBM Research. He has more than 50 peer-reviewed top-tier conference and journal publications. He is on the editorial board of Machine Learning journal (Springer) and regularly serves as a senior programme committee member/programme committee member of top conferences (WWW, IJCAI, AAAI, ECML-PKDD, ALENEX and CP) in the areas of machine learning, algorithm engineering and optimisation.