  This paper introduces scalable, sampling-based algorithms that optimize
trained neural networks with ReLU activations. We first propose an iterative
algorithm that takes advantage of the piecewise linear structure of ReLU neural
networks and reduces the initial mixed-integer optimization problem (MIP) into
multiple easy-to-solve linear optimization problems (LPs) through sampling.
Subsequently, we extend this approach by searching around the neighborhood of
the LP solution computed at each iteration. This scheme allows us to devise a
second, enhanced algorithm that reduces the initial MIP problem into smaller,
easier-to-solve MIPs. We analytically show the convergence of the methods and
we provide a sample complexity guarantee. We also validate the performance of
our algorithms by comparing them against state-of-the-art MIP-based methods.
Finally, we show computationally how the sampling algorithms can be used
effectively to warm-start MIP-based methods.
