Using expression graphs in optimization algorithms
Presenter
November 19, 2008
Keywords:
- Graph algorithms
MSC:
- 05C85
Abstract
An expression graph, informally speaking, represents a function in a
way that cam be manipulated to reveal various kinds of information
about the function, such as its value or partial derivatives at
specified arguments and bounds thereon in specified regions. (Various
representations are possible, and all are equivalent in complexity, in
that one can be converted to another in time linear in the
expression's size.) For mathematical programming problems, including
the mixed-integer nonlinear programming problems that are the subject
of this workshop, there are various advantages to representing
problems as collections of expression graphs. "Presolve" deductions
(to be discussed in more detail by Todd Munson) 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 a branch-and-bound (or
-cut) 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.
One of my reasons for interest in the AMPL modeling language is that
it delivers expression graphs to solvers.