Adaptive Solution Prediction via Machine Learning for Large-Scale Combinatorial Optimization

Speaker: Prof Xiaodong Li (RMIT University)
Summary:
In the big data era, we frequently encounter combinatorial optimization problems of very high dimensionalities. The number of decision variables often exceed thousands or even millions. This poses significant challenges to standard solution techniques such as exact methods (e.g., CPLEX and Gurobi) and meta-heuristics (e.g., evolutionary algorithms), which are usually ill-equipped to cope with the sheer size of such large-scale problems. Meanwhile, machine learning has become increasingly popular as a viable technique to learn and discover problem structure, thereby paving a way to harness such knowledge for problem decomposition or reduction. The core idea is that if we can decompose a large-scale problem or reduce its size, then it may become plausible again to apply these existing methods. In this talk, I will present our work on “solution prediction via machine learning” for problem reduction, using machine learning models to learn from previously solved problem instances. Furthermore, we use what is learnt from our trained machine learning model to predict whether a decision variable belongs to an optimal solution on unseen and much larger problem instances. Our “solution prediction via machine learning” approach can be used as a generic pre-processing step to substantially prune the search space of a large-scale combinatorial optimization problem. Once the problem is reduced in size, we can then apply standard solution techniques, which tend to become effective again. We have demonstrated the efficacy of our method for problem reduction over several classic combinatorial optimization problems such as Maximum Weight Clique Problems (MWCP), Travelling Salesman Problems (TSP), and Graph Colouring Problems (GCP). Our recent efforts have been to make such solution prediction methods more adaptive, to allow continuous refinement on the accuracy of the statistical features involved. As a result, the quality of prediction of our off-line trained machine learning model can be further improved.
Biography:
Xiaodong Li is a Professor in Artificial Intelligence with the School of Computing Technologies, RMIT University, Melbourne, Australia. He holds a PhD in Artificial Intelligence (University of Otago, New Zealand). His research interests include machine learning, evolutionary computation, data mining/analytics, multiobjective optimization, multimodal optimization, large-scale optimization, combinatorial optimization, deep learning, math-heuristic methods, and swarm intelligence. He is the recipient of 2013 ACM “SIGEVO Impact Award” and 2017 IEEE CIS “IEEE Transactions on Evolutionary Computation Outstanding Paper Award”. His h-index is 62, with a total number of citations 17000+ (according to Google Scholar). He is an IEEE Fellow, and an IEEE CIS Distinguished Lecturer (2024 - 2026). He also serves as a member of ARC (Australian Research Council) College of Experts (2023 - 2025). In the past few years, he has dedicated most of his research effort in developing innovative Machine Learning techniques for solving large-scale combinatorial optimization problems.