Organized by the IEEE Computational Intelligence Society Shenzhen Chapter.

Activity Aim & Talk

In this virtual activity, Professor Xiaodong Li will talk about solution prediction via machine learning for combinatorial optimization. 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 pre-processing 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), 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 and maximum weight clique problems. 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); ii) to better guide the branching decision in B&B (Branch & Bound); and iii) to use as a more efficient pricing heuristic in CG (Column Generation)

Meet the Speaker

Professor 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 59, with a total number of citations 14000+ (according to Google Scholar).