Speaker: Laurent Michel
Day:  Wednesday, 11/15/2006
Room: ITEB 201
Time: 2:30pm

Title: Automatic Differentiation in Constraint-Based Local Search

Abstract:
Invariants that incrementally maintain the value of expressions under assignments to their variables are a natural abstraction to build high-level local search algorithms. But their functionalities are not sufficient to allow arbitrary expressions as constraints or objective functions as in constraint programming. Differentiable invariants bridge this expressiveness gap. A differentiable invariant maintains the value of an expression and its variable gradients, it supports differentiation to evaluate the effect of local moves.  The talk will introduce invariants, the computational model for their analysis and the  mechanism needed to support automatic differentiation of complex, and possibly reified, expressions to deliver combinatorial optimization models that are essentially similar to their CP counterparts.