Representatives of the Sandia sub-team of M2ACS gave three modeling-related talks at the recent APMOD Conference at the University of Warwick (International Conference on Applied Mathematical Optimization and Modeling), held 9-11 April 2014.
Analyzing Structured Optimization Models with Automatic Transformations
John Siirola and William Hart
Computational tools for modeling mathematical programs are widely used within both academia and industry. Available commercial and open-source modeling packages support generic modeling by separating modeling constructs from instance data through concepts like sets, parameters, and parameterized constraints. However, their model representations are limited to constructs that directly correspond to established solver inputs. In general, this implies that mathematical programs must be expressed as either linear or nonlinear algebraic models; that is, a list of variables, an algebraic objective expression, and a list of algebraic constraints. Modelers must then explicitly convert non-algebraic constructs like switching decisions in disjunctive programs into algebraic relaxations (e.g., relaxing constraints implied by the decision with Big-M terms). This approach can obfuscate or eliminate the original model structure and it forces the modeler to sacrifice abstraction by injecting decisions related to how to solve a model into the model representation. In this presentation, we demonstrate how high-level non-algebraic modeling constructs can be coupled with automated model transformations to improve model clarity and abstraction. This coupling provides a more flexible workflow where the modeler can explicitly apply transformations that link the structured model to a particular solver. Additionally, this modeling approach simplifies the model specification by eliminating explicit modeling of reformulation decisions. We will highlight two key non-algebraic constructs: disjunctive programming and complementarity constraints. We present transformations that rely on both direct transcription to the Big-M or convex hull relaxation, as well as heuristic procedures leverage both relaxations. Similarly, we show how to reformulate complementarity constraints as smooth nonlinear expressions or as a disjunctive expression that subsequently applies disjunctive transformations. These constructs and transformations are available in the open source Coopr optimization project, which includes the Pyomo modeling library.
Toward Supporting Bi-Level Programming in an Algebraic Modeling Language
Richard Chen, William Hart, and John Siirola
A bi-level program is a mathematical program in which a subset of decision variables is constrained to take values associated with an optimal solution of a distinct, “lower” level mathematical program. Bi-level programs are widespread in practice, and they arise in applications ranging from graph analysis to sensor and facility location. However, no algebraic modeling language (AML) natively supports bi-level programming, which forces users to directly implement intricate model transformations by hand. In this presentation, we describe recent developments to support bi-level programming in an AML, specifically in the context of the Pyomo AML and the Coopr open-source optimization project. We focus on the class of bi-level programs that features two sequential decision makers (upper-level and lower-level) and information transparency. The upper-level program is a mixed-integer linear program and the lower-level program is a linear program parameterized by a subset of the upper-level program’s binary variables. We describe modeling extensions that support the expression of bilevel programs in Pyomo, and transformations that automatically construct an equivalent single-level mixed-integer linear program. These transformations can be applied automatically to allow for direct solution by general solvers. The transformations are derived using duality and linearization/reformulation via disjunctive constraints. We demonstrate the use of these new constructs and tools using specific motivating problems from real-world application domains: shortest-path network interdiction and water sensor placement.
Specification and Automatic Discretization of ODE and DAE systems in an AML
John-Paul Watson, John Siirola, Victor Zavala and Bethany Nicholson
Dynamic optimization problems that include differential equations as constraints are typically solved by first discretizing the model and then solving the resulting nonlinear optimization problem. Several strategies exist for discretizing such dynamic systems, including multiple shooting and collocation over finite elements. However, implementing these discretization strategies is usually done by hand, which is both a time consuming and error prone process. We begin this talk by introducing new modeling constructs to support the specification of ODE and DAE systems with in the Pyomo algebraic modeling language. While simple, these constructs significantly expand the scope of optimization problem that can be addressed by typical AMLs, e.g., GAMS and AMPL. We then discuss mechanisms to perform automatic discretization of the resulting models, using flexible and configurable discretization transformations. Given these new capabilities, we examine two illustrative dynamic optimization problems. The first problem involves parameter estimation for an infectious disease propagation model. We use this example to demonstrate the relative cost of automatic versus manual discretization, and to demonstrate validity of the proposed approach. The second problem involves operation of a natural gas transportation network. We use this example to illustrate more advanced discretization schemes and challenges, and show how the availability of ODE/DAE constructs in an AML enables expression and solution of stochastic dynamic optimization problems, using the PySP library for stochastic programming.