En-Cheng Chang

Combinatorial optimization problems arise in many areas of computer science and other disciplines, such as business analytics, artificial intelligence and operations research. Prominent examples are tasks such as finding shortest or cheapest round trips in graphs, graph pattern matching, scheduling, time-tabling, resource allocation etc. These problems typically involve finding groupings, orderings or assignments of discrete, finite set of elements that satisfy certain conditions or constraints. A large number of optimization problems are NP-hard. As a result, applications typically rely on approximation algorithms, carefully designed heuristics for specific instance classes, or meta- heuristic frameworks to solve them efficiently. While the first two require significant human effort, the last set of techniques can be very far from optimal. Finding good optimization solutions efficiently has been a long-standing quest and such solutions are likely to have very high impact in a range of applications. In recent years, researchers are exploring if machine learning techniques can be used to learn the solutions directly from the input. The early results based on deep-learning techniques, that modelled these problems as sequence to sequence learning tasks, have shown that it is indeed viable to do so, as there are universal motifs present in graphs (across datasets and scales) that can be leveraged to learn effective models for optimization problems. However, these deep-learning based techniques do not seem to generalize well, require a lot of training data (which requires solving a large number of NP-hard problem instances) and are not interpretable. This PhD project will explore machine learning techniques to design novel heuristics that can achieve optimal (or close-to-optimal) solutions for combinatorial optimization problems. The goal will be to use simple interpretable models relying only on local features of elements, such that these heuristics can potentially be mathematically analyzed for optimality guarantees on specific input distributions. In terms of learning technique, we will use a learning-to-prune framework, reinforcement learning and graph neural networks for this purpose. The success of this project will greatly augment the human ability to design algorithms for combinatorial optimization problems in industry.