×

Using expression graphs in optimization algorithms. (English) Zbl 1242.90131

Lee, Jon (ed.) et al., Mixed integer nonlinear programming. Selected papers based on the presentations at the IMA workshop mixed-integer nonlinear optimization: Algorithmic advances and applications, Minneapolis, MN, USA, November 17–21, 2008. New York, NY: Springer (ISBN 978-1-4614-1926-6/hbk; 978-1-4614-1927-3/ebook). The IMA Volumes in Mathematics and its Applications 154, 247-262 (2012).
Summary: An expression graph, informally speaking, 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 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 were the subject of the IMA workshop that led to this paper, there are various 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 paper sketches 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.
For the entire collection see [Zbl 1230.90005].

MSC:

90C11 Mixed integer programming
68R10 Graph theory (including graph drawing) in computer science
68U01 General topics in computing methodologies
68N20 Theory of compilers and interpreters
68W30 Symbolic computation and algebraic computation
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI Link