Evolutionary Computation meets Machine Learning for Combinatorial Optimisation
Description
Combinatorial optimisation is an important research area with many real-world applications such as scheduling, vehicle routing, cloud resource allocation, supply chain management, logistics and transport. Most combinatorial optimisation problems are NP-hard, making it challenging to design effective algorithms to solve them to optimality. In practice, in particular (meta-)heuristic methods including evolutionary approaches are therefore widely used to address such problems. Unfortunately, designing an effective and efficient (meta-)heuristic typically requires extensive domain expertise and a lot of trial and error for each different problem variant encountered in the real world.
In recent years, machine learning has emerged to also be a promising ingredient for better and/or easier solving combinatorial optimisation problems. First, machine learning can design combinatorial optimisation algorithms automatically by searching for algorithms/heuristics rather than solutions, and the learned algorithms/heuristics can be generalised to future unseen problem variants to obtain high-quality solutions. This can greatly reduce the dependence on human expertise and time to manually design effective algorithms. Second, machine learning can learn decision-making policies for dynamic combinatorial optimisation problems (e.g., dispatching rules for dynamic scheduling), which can achieve both effectiveness and efficiency simultaneously. Third, machine learning may discover new design patterns and knowledge that can further improve the algorithm design for solving complex combinatorial optimisation problems.
The aim of this tutorial is two-fold. On the one hand, we will give an overview on how classical metaheuristics may profit from the usage of machine learning and provide a few advanced examples. On the other hand, we will introduce how (evolutionary) machine learning, specifically, can be used for solving combinatorial optimisation problems, including basic design issues and some case studies.
The outline of the tutorial is as follows.
1. Introduction and Background
2. Evolutionary Computation to Learn Combinatorial Optimisation Heuristics
3. Machine Learning to Learn Metaheuristics
4. Challenges and Future Directions
Organizers
Dr. Yi Mei is an Associate Professor at Victoria University of Wellington, New Zealand. His research interests include evolutionary computation for combinatorial optimisation, genetic programming, automatic algorithm design, explainable AI, multi-objective optimisation, transfer/multitask learning and optimisation, and their real-world applications. He has published on top journals in EC and Operations Research (OR) such as IEEE TEVC, IEEE TCYB, EJOR, IEEE Transactions on Services Computing, and ACM Transactions on Mathematical Software. He won an IEEE Transactions on Evolutionary Computation Outstanding Paper Award 2017, GECCO Best Paper Awards in 2022, 2023 and 2024, and the EuroGP Best Paper Award 2022.
He was a GECCO ECOM Track Chair for 2023-2024. He is an Associate Editor of IEEE Transactions on Evolutionary Computation, Computational Intelligence Magazine, IEEE Transactions on Artificial Intelligence, Journal of Scheduling, and an Editorial Board Member/Associate Editor of four other international journals. He is the Chair of the IEEE Taskforce on Evolutionary Scheduling and Combinatorial Optimisation. He is a Fellow of Engineering New Zealand and an IEEE Senior Member.
Günther Raidl is Professor at the Institute of Logic and Computation, TU Wien, Austria, and member of the Algorithms and Complexity Group. He received his PhD in 1994 and completed his habilitation in Practical Computer Science in 2003 at TU Wien. In 2005 he received a professorship position for combinatorial optimization at TU Wien.
His research interests include algorithms and data structures in general and combinatorial optimization in particular, with a specific focus on metaheuristics, mathematical programming, intelligent search methods, and hybrid optimization approaches. His research work typically combines theory and practice for application areas such as scheduling, network design, transport optimization, logistics, and cutting and packing.
Günther Raidl is associate editor for the INFORMS Journal on Computing, the ACM Transactions on Evolutionary Learning and Optimization and at the editorial board of several journals including Algorithms, Engineering Applications of Artificial Intelligence, and Metaheuristics. He is co-founder and steering committee member of the annual European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP). Since 2016 he is also founding faculty member of the Vienna Graduate School on Computational Optimization.
Günther Raidl has co-authored a text book on hybrid metaheuristics and over 190 reviewed articles in scientific journals, books, and conference proceedings. Moreover, he has co-edited 13 books and co-authored one book on hybrid metaheuristics. More information can be found at http://www.ac.tuwien.ac.at/raidl.