434930 A Transformation-Centric Approach to Analyzing and Solving Structured Optimization Problems

Monday, November 9, 2015: 12:30 PM
Salon F (Salt Lake Marriott Downtown at City Creek)
John Siirola, William E. Hart and Jean-Paul Watson, Discrete Math & Optimization, Sandia National Laboratories, Albuquerque, NM

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 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 Pyomo optimization project.

Extended Abstract: File Not Uploaded