Speaker: Xiaodong Li, Professor, RMIT University, Australia
Date: 26 October 2022
Time: 8:00 - 9:00pm (Australia Time, UTC+11)
Xiaodong Li received his B.Sc. degree from Xidian University, Xi'an, China, and Ph.D. degree in information science from University of Otago, Dunedin, New Zealand, respectively. He is a Professor in Artificial Intelligence currently with the School of Computing Technologies, RMIT University, Melbourne, Australia. His research interests include machine learning, evolutionary computation, data mining/analytics, multiobjective optimization, multimodal optimization, large-scale optimization, deep learning, math-heuristic methods, and swarm intelligence. He serves as an Associate Editor of journals including IEEE Transactions on Evolutionary Computation, Swarm Intelligence (Springer), and International Journal of Swarm Intelligence Research. He is a founding member of IEEE CIS Task Force on Swarm Intelligence, a former vice-chair of IEEE Task Force on Multi-modal Optimization, and a former chair of IEEE CIS Task Force on Large Scale Global Optimization. He is the recipient of 2013 ACM SIGEVO Impact Award and 2017 IEEE CIS "IEEE Transactions on Evolutionary Computation Outstanding Paper Award". He was elevated to IEEE Fellow in 2020 (“for contributions to large-scale and particle swarm optimization"). His h-index is 58, with a total number of citations 14000+ (according to Google Scholar).
Combinatorial optimization problems are ubiquitous across many disciplinary areas such as science and engineering. In the big data era, the dimensionality of a combinatorial optimization problem is usually very large, which poses a significant challenge to existing solution methods. A logical way to tackle large-scale combinatorial optimization problems is through problem reduction, i.e., to reduce the size of an original problem by removing decision variables that are irrelevant to the optimal solution. Indeed, the optimal solution to a combinatorial optimization problem is often determined by a relatively small number of decision variables. This problem reduction can be seen as a preprocessing step to prune the search space of the original problem, since once the pruning is done the reduced problem can be then solved by a standard solution method, e.g., exact solver or meta-heuristic. In this talk, I will present our recent works on such an approach using Machine Learning for Problem Reduction (i.e., MLPR) [1], to learn and predict whether decision variables belong to an optimal solution or not. As a result, we can achieve problem reduction by eliminating those variables that do not belong to an optimal solution. We have demonstrated the efficacy of MLPR on the classic traveling salesman problems [2] and maximum weight clique problems [1]. In addition to problem reduction, we have also shown that such a solution prediction technique is generally applicable to a variety of situations facing combinatorial optimization: i) to warm-start the pheromone matrix in ACO (Ant Colony Optimization) [4]; ii) to better guide the branching decision in B&B (Branch & Bound) [5]; and iii) to use as a more efficient pricing heuristic in CG (Column Generation) [3].
[1] Sun, Y., Li, X., Ernst, A. (2021), "Using Statistical Measures and Machine Learning for Graph Reduction to Solve Maximum Weight Clique Problems", IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(5): 1746 - 1760, May 2021.
[2] Sun, Y., Ernst, A.T., Li, X. and Weiner, J. (2021), "Generalization of Machine Learning for Problem Reduction: a Case Study on Travelling Salesman Problems", OR Spectrum, 43:607-633, 2021.
[3] Shen, Y., Sun, Y., Eberhard, A. and Li, X., and Ernst, A. (2022), "Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring", Proceedings of Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22).
[4] Sun, Y. Wang, S., Shen, Y., Li, X., Ernst, A.T., and Kirley, M. (2022), "Boosting Ant Colony Optimization via Solution Prediction and Machine Learning", Computers and Operations Research, Vol.143, July 2022, 105769.
[5] Shen, Y., Sun, Y., Eberhard, A. and Li, X. (2021) "Learning Primal Heuristics for Mixed Integer Programs", in Proceedings of 2021 International Joint Conference on Neural Networks (IJCNN), IEEE.
The Webinar went very successful, with 180+ participants.
The recorded video can be accessed at YouTube and Bilibili.com.
Back to the Webinar Series