(194b) Easily Solvable Convex Mixed-Integer Nonlinear Programs Derived from Generalized Disjunctive Programming Using Cones

Easily solvable convex mixed-integer nonlinear programs derived from generalized disjunctive programming using cones

David E. Bernal, Ignacio E. Grossmann

Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA, USA

Solving convex Mixed-Integer Nonlinear Programs (MINLP) problems is an active research topic [1]. These problems are particularly interesting given their versatility to represent physical problems with logical choices using nonlinear constraints and integer variables. A way to represent these mixed-integer problems is using logical relations, algebraic constraints, disjunctions, and Boolean variables [2]. A way of modeling this particular representation is Generalized Disjunctive Programming (GDP) [3], where each disjunction may have several terms (disjuncts) where at least one is true with a corresponding Boolean variable associated. By representing these problems through GDP, the formulation of the model becomes more intuitive and the underlying logic structure of the problem is explicitly modeled [4].

Although there are existing methods to solve GDPs directly [5], e.g. Logic-based OA, the main way to solve this kind of problems is by transforming them into MI(N)LPs and using the existing solvers developed for them, e.g. BARON, SCIP, CPLEX, and Gurobi. These reformulations use binary variables to represent the Boolean variables in GDP, and replace the logical propositions with linear inequalities involving the binary variables while satisfying the algebraic constraints in the disjunctions when the corresponding binary variable is equal to one. The two common reformulations of logic programs into MI(N)LP are the Big-M method, where large constants M are introduced in such a way that they can enforce or relax the algebraic constraints in each disjunct for all disjunctions, and the Hull relaxation [4], where continuous variables are disaggregated for each disjunct in each disjunction and the algebraic constraints are rewritten in terms of its corresponding copy of the continuous variables and binary variable [4].

A technical complicating factor in the Hull relaxation reformulation of GDPs requires the algebraic constraints to be rewritten in terms of the disaggregated continuous and binary variables using the perspective mapping of the constraint’s function [6]. The perspective mapping is a well-defined topological closure of sets, but implementing it practically is complicated. This is because for nonlinear functions it involves including the corresponding binary variable in the denominator, which is undefined whenever this variable is equal to zero. To avoid this issue, several ε -approximations have been proposed in the literature [7]. Motivated by recent work in mixed-integer convex representability [8], we propose for convex GDP an exact representation of the Hull relaxation. We consider a convex GDP as one where all the algebraic constraints not involved in disjunctions and the feasible region defined by each disjunct are convex.

The exact representation of the perspective mapping of convex programming is achieved through conic programming reformulations [9]. This representation, apart from being exact, allows us to use specialized solvers that exploit the conic structure, e.g. MOSEK, instead of general purpose MINLP solvers. Results involving second-order cone and exponential cones for the Hull reformulation of GDPs are obtained. These particular problems have applications in Chemical Engineering, Machine Learning, and Operation Research in general. The safety constrained layout problem [10] and a K-means clustering problem [11] are formulated as quadratic GDPs, where the second order-cone reformulation is used to solve them. Process superstructure problems [12] and multi-product chemical batch design processes [13] are formulated as nonlinear GDPs and then exponential cones appear in the MINLP formulation. In all of these cases, the results show that the exact Hull reformulation yield Mixed-integer Conic Programs that are more efficiently solved than with the ε-approximations of the perspective functions or with the Big-M method.

[1]	J. Kronqvist, D. E. Bernal, A. Lundell, and I. E. Grossmann, "A review and comparison of solvers for convex MINLP," Optimization and Engineering, pp. 1-59, 2018.
[2]	J. N. Hooker and M. A. Osorio, "Mixed logical-linear programming," Discrete Applied Mathematics, 1999.
[3]	I. E. Grossmann and S. Lee, "Generalized convex disjunctive programming: Nonlinear convex hull relaxation," Computational Optimization and Applications, pp. 83-100, 2003.
[4]	E. Balas, Disjunctive Programming, Springer International Publishing, 2018.
[5]	F. Trespalacios and I. E. Grossmann, "Review of mixed-integer nonlinear and generalized disjunctive programming methods," Chemie-Ingenieur-Technik, vol. 86, no. 7, 2014.
[6]	S. Ceria and J. Soares, "Convex programming for disjunctive convex optimization," Mathematical Programming, vol. 86, no. 3, pp. 595-614, 1999.
[7]	N. Sawaya, "Reformulations, relaxations and cutting planes for generalized disjunctive programming," Carnegie Mellon University, Pittsburgh, 2006.
[8]	M. Lubin, I. Zadik and J. P. Vielma, "Mixed-integer convex representability," arXiv, vol. 1706.05135, 2017.
[9]	Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Springer, 2004.
[10]	F. Penteado and A. Ciric, "An MINLP Approach for Safe Process Plant Layout," Industrial and Engineering Chemistry Research, vol. 34, no. 4, pp. 1354-1361, 1996.
[11]	S. Lloyd, "Least squares quantization in PCM," Information Theory, IEEE Transactions on, vol. 28, no. 2, pp. 129-137, 1982.
[12]	M. Turkai and I. Grossmann, "Logic-based MINLP algorithms for the optimal synthesis of Process Networks," Computer and Chemical Engineering, vol. 20, no. 8, pp. 959-978, 1996.
[13]	D. Straub and I. Grossmann, "Evaluation and Optimization of Flexibility in Multiproduct Batch Plants," Computer and Chemical Engineering, vol. 16, pp. 69-87, 1992.