Date of Award

12-2017

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Chemical Engineering

Committee Chair

Carl D. Laird

Committee Member 1

Gintaras V. Reklaitis

Committee Member 2

Joseph F. Pekny

Committee Member 3

Marcial Gonzalez

Abstract

Many practical applications involving large complex systems are naturally formulated as mixed-integer nonlinear programming (MINLP) problems. These optimization problems are inherently large-scale and non-convex, and can be extremely difficult to solve. Efficient algorithms, especially global solution strategies, for MINLP problems play important roles in many real-world applications. Although a number of optimization tools have been developed for general MINLP problems, their performance may vary significantly on different problem instances. Moreover, computational experience has suggested that for MINLP problems with certain particular properties, customized algorithms can significantly outperform general MINLP solvers. In this thesis, we focus on developing and applying problem-specific global algorithms for large-scale MINLP problems. Inspired by the multi-tree methods, particularly the outer approximation (OA) approach, all our tailored algorithms rely on solving a sequence of mixed-integer programming (MIP) master problems and nonlinear programming (NLP) subproblems. The MIP master problem is a convex relaxation of the original MINLP problem, whose solution provides a lower bound of the objective function value in a minimization problem. The NLP subproblem, which, on the other hand, leads to an upper bound, is generated by fixing all discrete variables in the original MINLP problem. By iteratively solving the master problem and the subproblem, the gap between the upper and lower bounds will gradually decrease, and algorithm converges when the gap is below a given tolerance. To further improve the convergence of our algorithm, sophisticated techniques, such as bound tightening and piecewise outer approximation, are also integrated with the classic multi-tree framework. To demonstrate the benefits from using multi-tree algorithms, we consider optimization problems arising from three different research areas, including parameter estimation of infectious disease models, optimization in power systems, and optimal placement of imperfect sensors. These applications are significantly different, however, they are formulated as large-scale MINLP problems and can be efficiently solved using tailored multi-tree algorithms. For each application, candidate mathematical formulations of the optimization problems are carefully studied and compared in order to identify the most appropriate one for the proposed multi-tree framework. The master problem formulations and refinement strategies are designed based on the problem-specific properties and structures for each instance. All proposed algorithms are implemented in Pyomo, a Python-based optimization modeling language. Numerical results indicate that our tailed multi-tree algorithms outperform the off-the-shelf solvers designed for general MINLP problems across all applications under investigation.

Download

Share

COinS