Convex Relaxations for Mixed-Integer Nonlinear Programs (English shop)

Preview

Extract, PDF (120 KB)
Table of Contents, PDF (49 KB)

This thesis deals with new techniques to construct a strong convex relaxation for a mixed-integer nonlinear program (MINLP). While local optimization software can quickly identify promising operating points of MINLPs, the solution of the convex relaxation provides a global bound on the optimal value of the MINLP that can be used to evaluate the quality of the local solution. Certainly, the efficiency of this evaluation is strongly dependent on the quality of the convex relaxation.

Convex relaxations of general MINLPs can be constructed by replacing each nonlinear function occurring in the model description by convex underestimating and concave overestimating functions. In this setting, it is desired to use the best possible convex underestimator and concave overestimator of a given function over an underlying domain — the so-called convex and concave envelope, respectively. However, the computation of these envelopes can be extremely difficult so that analytical expressions for envelopes are only available for some classes of well-structured functions.

Another factor influencing the strength of the estimators is the size of the underlying domain: The smaller the domain, the better the quality of the estimators. In many applications the initial domains of the variables are chosen rather conservatively while tighter bounds are implicitly given by the constraint set of the MINLP. Thus, bound tightening techniques, which exploit the information of the constraint set, are an essential ingredient to improve the estimators and to accelerate global optimization algorithms.

The focus of this thesis lies on the development and computational analysis of new convex relaxations for MINLPs, especially for two applications from chemical engineering. In detail, we derive a new bound tightening technique for a general structure used for modeling chemical processes and provide different approaches to generate strong convex relaxations for various nonlinear functions.

Initially, we aim at the optimal design of hybrid distillation/melt-crystallization processes, a novel process configuration to separate a m ixture into its component. A crucial part in the formal representation of this process as well as other separation processes is to model the mass conservation within the process. We exploit the analytical properties of the corresponding equation system to reduce the domains of the involved variables. Using the proposed technique, we can accelerate the computations for hybrid distillation/melt-crystallization processes significantly compared to standard software.

Then, we concentrate on the generation of convex relaxations for nonlinear functions. First, we exploit the existing theory for two interesting classes of bivariate functions. On the one hand, we elaborate, implement, and illustrate the strength of a cut-generation algorithm for bivariate functions which are convex or concave in each variable and for which the sign of the Hessian is the same over the entire domain. On the other hand, relaxation strategies for advanced equilibrium functions in chromatographic separation processes are analyzed and finally applied to completely describe the feasible separation regions of these processes.

Second, we suggest to derive the envelopes in an extended space to overcome the combinatorial difficulties involved in the computation of the convex envelope in the original space. In particular, we consider a class of functions accounting for a large amount of all nonlinearities in common benchmark libraries. These functions are component-wise concave in one part of the variables and convex in the other part of the variables. For this general class of functions the convex envelopes in the original variable space have not been discovered so far. We provide closed-form expressions for the extended formulation of their convex envelopes based on the simultaneous convexification with multilinear monomials. By construction, this approach does not only yield an extended formulation for the convex envelope of a function, but also a strong simultaneous relaxation of the function and the involved multilinear monomials. Several examples show that this simultaneous relaxation can be orders of magnitude better than the individual relaxation of the functions.

Finally, inspired by the strength and the computational impact of the simultaneous relaxation of a function and multilinear monomials, we further focus on the simultaneous convexification of several functions. In such an approach the relaxation of a MINLP involving several functions in the same variables is much tighter because the interdependence between the different functions is taken into account. We study the simultaneous convex hull of several functions for which we derive theoretical results concerning their inner and outer description by means of the rich theory of convex envelopes. Moreover, we apply these results to provide formulas for tight convex relaxations of several univariate convex functions.

Implementations of all convexification techniques are available as plugins for the open-source MINLP solver scip. The computational results of several case studies reveal the benefit of the proposed techniques compared to state-of-the-art methods.