The Webinar given by Prof Xiaodong Li from RMIT University, Australia.
Organiser: IEEE Taskforce on Evolutionary Scheduling and Combinatorial Optimisation (https://homepages.ecs.vuw.ac.nz/~yimei/ieee-tf-esco/)
Abstract
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].
