Title: Computing with Expression Graphs (2009 CSRI Summer Lecture Series)

Speaker: David M. Gay, Sandia National Laboratories

Date/Time: Wednesday, June 17, 2009, 3-4pm (MST)     

Location: CSRI Building, Room 90 (Sandia NM), 915/S145 (CA)

Brief Abstract: An expression graph represents a function in a way that can be manipulated to reveal various kinds of information about the function, such as its value or partial derivatives at specified arguments and bounds on the function in specified regions.  Sometimes, e.g., for nonlinear programming, there are advantages to representing problems as collections of expression graphs.  "Presolve" deductions can simplify the problem, e.g., by reducing the domains of some variables and proving that some inequality constraints are never or always active.  To find global solutions, it is helpful sometimes to solve relaxed problems (e.g., allowing some "integer" variables to vary continuously or introducing convex or concave relaxations of some constraints or objectives), and to introduce "cuts" that exclude some relaxed variable values.  There are various ways to compute bounds on an expression within a specified region or to compute relaxed expressions from expression graphs.  This talk will sketch some of them.  As new information becomes available in the course of an algorithm, some expression-graph manipulations and presolve deductions can be revisited and tightened, so keeping expression graphs around during the solution process can be helpful.  Algebraic problem representations are a convenient source of expression graphs.  The AMPL modeling language (which I will discuss briefly) can be a convenient source of expression graphs.  Operator overloading (e.g., in C++) is another source.

CSRI POC: Zhaofang Wen (505) 284-0206