Novel Global Optimization Methods: Theoretical and Computational Studies on Pooling Problems with Environmental Constraints

Abstract

Allocating limited resources in process synthesis and operations is a major industrial challenge that is best approached using recent theoretical advances in global optimization. Relevant high-throughput applications include: petroleum refining; wastewater treatment; supply-chain operations; oil well production. This dissertation begins by addressing the pooling problem, an optimization challenge of maximizing profit subject to product availability, storage capacity, demand, product specifications, and environmental standards.

Pooling problems are particularly difficult instantiations of mixed-integer nonlinear programs (MINLP); this dissertation therefore expands to more broadly address two important classes of MINLP: mixed-integer quadratically constrained quadratic programs (MIQCQP) and mixed-integer signomial optimization problems (MISO). To solve both pooling problems and the more general classes, this dissertation incorporates three main strands:

Effective modeling: This thesis formulates an extended pooling problem with the Environmental Protection Agency (EPA) Title 40 Code of Federal Regulations Part 80.45: Complex Emissions Model as an MINLP. We model an industrially-relevant pooling problem with mutable network topology as an MIQCQP.

Novel global optimization methodology and techniques: Solving these medium- and large-scale problems necessitated the development of theoretical and algorithmic strategies, including: a variety of multivariable and multiterm convex underestimators for MIQCQP and MISO, automatic reformulations for MIQCQP and MISO, low-dimensional aggregation of multivariable terms, a necessary and sufficient condition for the existence of quadratic cutting planes, and algorithmic development for the aforementioned techniques.

Software implementation of a computational framework: The work documented in this dissertation has been made publicly available via two avenues. The freely-available, web-based computational tool APOGEE (Algorithms for Pooling-problem global Optimization in GEneral and Extended classes) globally optimizes standard, generalized, and extended pooling problems. The MIQCQP solver GloMIQO (Global Mixed-Integer Quadratic Optimizer) is commercially available through the General Algebraic Modeling System (GAMS). This thesis describes the implementation of both APOGEE and GloMIQO.

To test and validate the three strands, this thesis includes a variety of computational studies indicating the efficacy of the modeling strategies, algorithmic components, and software implementation. Effectively, the arc of this dissertation is to begin with modeling and globally optimizing pooling problems and expand into an optimization framework that broadly addresses MIQCQP and MISO.