Strong mixed-integer programming formulations for trained neural networks

摘要: We present strong mixed-integer programming (MIP) formulations for high-dimensional piecewise linear functions that correspond to trained neural networks. These can be used a number of important tasks, such as verifying an image classification network is robust adversarial inputs, or solving decision problems where the objective function machine learning model. generic framework, which may independent interest, provides way construct sharp ideal maximum d affine over arbitrary polyhedral input domains. apply this result derive MIP most popular nonlinear operations (e.g. ReLU and max pooling) are strictly stronger than other approaches from literature. corroborate computationally, showing our able offer substantial improvements in solve time on verification tasks