Graph Representation Learning for Solving Combinatorial Optimization Problems

Ya Song

PhD student at Eindhoven University of Technology

Abstract: In the research field of solving combinatorial optimization problems, many studies have considered combining machine learning with optimization algorithms and proposed so-called learning-based optimization algorithms. Compared to traditional handcrafted algorithms, these methods can automatically extract relevant knowledge from training data and require less domain knowledge. In recent years, Graph Neural Networks (GNN) have attracted significant attention in learning-based optimization. The main reason is that some well-known routing problems, such as Traveling Salesperson Problem (TSP), naturally have a graph structure, and other problems like the set covering problem also can be modelled on graphs.  Currently, several standard GNNs have been applied to capture graph representations that can help to enhance heuristic search or solve problems directly. As the critical graph information varies for different combinatorial optimization problems, such standard GNNs might not be the best choice. However, few works study designing GNNs by taking into account the characteristics of the optimization tasks at hand. In this project, we seek to design customized GNNs to learn a better graph representation in solving combinatorial optimization problems.

Keywords: Combinatorial Optimization, Graph Representation Learning, Graph Neural Network, Routing Problem
Scientific area: Data & digital transformation, Energy & transport

Ya Song is a PhD student in Industrial Engineering & Innovation Sciences at the Eindhoven University of Technology. His research focuses on learning graph representations for combinatorial problems to facilitate problem-solving.