Johanna Sommer

Combinatorial problems are at the heart of countless tasks, from Sudoku and everyday computing tasks to billion-dollar operations. Challenges such as routing deliveries, scheduling access in a network and circuit design can all be boiled down to the same set of concepts. What is special about this class of problems, also referred to as combinatorial problems, is their high computational cost. While there are solvers available, they often rely on handcrafted, application-specific heuristics. Hence, there have been proposed multiple approaches using (geometric) deep learning to learn problem characteristics across disciplines and solve such problems.

This trans-disciplinary problem solving sounds promising, as it would allow us to e.g. train a graph neural network on street map data and then infer solutions for other areas such as boolean circuits. However, the strategy with which such training data is constructed is central to the practicality of the resulting model. If a neural combinatorial solver is trained and evaluated on a set of problems from the same domain, we can not conclude how well it can solve problems from other domains.

As a part of my doctoral studies, I investigate to what extent current approaches can in fact generalise across disciplines. By, for example, using methodology from the area of adversarial robustness, I can identify specific problem instances that are hard for the model to solve. The knowledge of such ‘blind spots’ can then guide the construction of better neural combinatorial solvers.