ReLU Neural Networks for Exact Maximum Flow Computation

In the last couple of years machine learning, and in particular deep neural networks (NNs), achieved astonishing results in various application domains like computer vision, natural language processing, automatic translation, autonomous driving, and many more [25]. Also in the field of combinatorial optimization (CO) promising approaches to utilize NNs for problem solving or improving classical solution methods have been introduced [6]. While there is a huge body of research publications certifying the empirical success of NNs, understanding these observations from a theoretical point of view seems to be a major challenge. One of the most important theoretical questions in the context of NNs is concerned with their expressivity: which functions can be represented by a neural network of a certain size?