  Understanding the great empirical success of artificial neural networks (NNs)
from a theoretical point of view is currently one of the hottest research
topics in computer science. In this paper we study the expressive power of NNs
with rectified linear units from a combinatorial optimization perspective. In
particular, we show that, given a directed graph with $n$ nodes and $m$ arcs,
there exists an NN of polynomial size that computes a maximum flow from any
possible real-valued arc capacities as input. To prove this, we develop the
pseudo-code language Max-Affine Arithmetic Programs (MAAPs) and show
equivalence between MAAPs and NNs concerning natural complexity measures. We
then design a MAAP to exactly solve the Maximum Flow Problem, which translates
to an NN of size $\mathcal{O}(m^2 n^2)$.
