Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2019-001 (January 23, 2019)

A Mixed Integer Linear Programming Formulation to Artificial Neural Networks
by Tatsuya Akutsu and Hiroshi Nagamochi

pdf File


Let a system S=(G=(V,E),w,F) consist of a digraph G (not necessarily acyclic) with a set V of vertices and a set E of edges, a weight function w from the union V and E to the set of reals and a set F of functions fv from the set of reals to the set of reals for each vertex v in V, where w(u,v) denotes the weight of an edge (u,v) from a vertex u in V and a vertex v in V. A solution to system S is defined to be a set of reals y_v, v in V such that y_v= fv(x), where x is w(v) plus +w(u,v)y_u over all edges (u,v) in E. Finding solutions to a given system has an important application in Artificial Neural Network (ANN). In this paper, we show that when each function fv is a continuous piece-wise linear function, the problem of finding a solution to a system S can be formulated as a Mixed Integer Linear Programming Problem (MILP) with O(|V| +n') variables and constraints, where n' denotes the total number of break points over all functions fv, v in V. Based on this, we can solve the inverse problem to an ANN N as an MILP after approximating the activation function in N as a piece-wise linear function.