An Integer Programming Approach to Optimal Derivative Accumulation

TitleAn Integer Programming Approach to Optimal Derivative Accumulation
Publication TypeConference Paper
Year of Publication2012
AuthorsChen, J, Hovland, PD, Munson, TS, Utke, J
Conference NameRecent Advances in Algorithmic Differentiation, Lecture Notes in Computational Science and Engineering
Date Published01/2012
PublisherSpringer
Other NumbersANL/MCS-P1994-0112
Abstract

In automatic differentiation, vertex elimination is one of the many methods for Jacobian accumulation. However, finding the optimal vertex elimination sequence of a computational graph is a hard combinatorial optimization problem. In this paper, we propose an integer programming (IP) technique to tackle this problem, and we develop an IP formulation for it. This enables us to use a standard integer optimization solver to find an optimal vertex elimination strategy. We hope to use the optimization formulation to evaluate the effectiveness of heuristics and find an optimal strategy for certain key computational kernels. In addition, we have developed several lower bound and symmetry-breaking constraints to strengthen the basic IP formulation. We demonstrate the effectiveness of these enhancements through computational experiments. We also consider the scarcity of a graph in the context of vertex elimination. A basic IP formulation for the scarcity problem and some preliminary computational results are presented.

PDFhttp://www.mcs.anl.gov/papers/1994-0112.pdf