An Integer Programming Approach to Optimal Derivative Accumulation

摘要: In automatic differentiation, vertex elimination is one of the many methods for Jacobian accumulation and in general it can be much more efficient than forward mode or reverse (Forth et al. ACM Trans Math Softw 30(3):266–299, 2004; Griewank Walther, Evaluating derivatives: principles techniques algorithmic SIAM, Philadelphia, 2008). However, finding optimal sequence a computational graph hard combinatorial optimization problem. this paper, we propose to tackle problem with an integer programming (IP) technique, develop IP formulation it. This enables us use standard solver find strategy. addition, have developed several bound-tightening symmetry-breaking constraints strengthen basic formulation. We demonstrate effectiveness these enhancements through experiments.