Publication: An Integer Programming Approach to Optimal Derivative Accumulation
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

An Integer Programming Approach to Optimal Derivative Accumulation

- incollection -
 

Author(s)
Jieqiu Chen , Paul Hovland , Todd Munson , Jean Utke

Published in
Recent Advances in Algorithmic Differentiation

Editor(s)
Shaun Forth, Paul Hovland, Eric Phipps, Jean Utke, Andrea Walther

Year
2012

Publisher
Springer

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

Cross-References
Forth2012RAi

AD Theory and Techniques
Computational Graph

BibTeX
@INCOLLECTION{
         Chen2012AIP,
       title = "An Integer Programming Approach to Optimal Derivative Accumulation",
       doi = "10.1007/978-3-642-30023-3_20",
       author = "Jieqiu Chen and Paul Hovland and Todd Munson and Jean Utke",
       abstract = "In automatic differentiation, vertex elimination is one of the many methods for
         Jacobian accumulation and in general it can be much more efficient than the forward mode or reverse
         mode (Forth et al. ACM Trans Math Softw 30(3):266–299, 2004; Griewank and Walther,
         Evaluating derivatives: principles and techniques of algorithmic differentiation, SIAM,
         Philadelphia, 2008). However, finding the optimal vertex elimination sequence of a computational
         graph is a hard combinatorial optimization problem. In this paper, we propose to tackle this problem
         with an integer programming (IP) technique, 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. In
         addition, we have developed several bound-tightening and symmetry-breaking constraints to strengthen
         the basic IP formulation. We demonstrate the effectiveness of these enhancements through
         computational experiments.",
       pages = "221--231",
       crossref = "Forth2012RAi",
       booktitle = "Recent Advances in Algorithmic Differentiation",
       series = "Lecture Notes in Computational Science and Engineering",
       publisher = "Springer",
       address = "Berlin",
       volume = "87",
       editor = "Shaun Forth and Paul Hovland and Eric Phipps and Jean Utke and Andrea Walther",
       isbn = "978-3-540-68935-5",
       issn = "1439-7358",
       year = "2012",
       ad_theotech = "Computational Graph"
}


back
  

Contact:
Username:
Password:
(lost password)