(598h) Quadratic Cut Decomposition Method for Convex Mixed-Integer Nonlinear Programs

David E. Bernal*, Lijie Su**, Lixin Tang**, Ignacio E. Grossmann*

*Chemical Engineering Department, Carnegie Mellon University, Pittsburgh PA.

** Institute of Industrial and Systems Engineering, Northeastern University, Shenyang, P. R. China

In this work, we address the incorporation of 2^nd order derivative information to the Outer-Approximation (OA) method to solve convex mixed-integer nonlinear programming (MINLP) problems. An MINLP problem arises when we represent an optimization problem using nonlinear algebraic equations involving continuous and discrete variables. A method to solve this problem is OA [1], [2], where the original problem is decomposed into two subproblems. The first subproblem, a master problem, considers the discrete nature of the integer-constrained variables and approximates the nonlinear functions with linear equations through a Mixed-Integer Linear Program (MILP). The second subproblem optimizes the nonlinear objective and constraints for fixed discrete variables giving rise to a Nonlinear Program (NLP). The linearization point of the first subproblem is provided by the solution of the second one, while the values for the discrete variables fixed in the second subproblem are provided by the solution of the first one. The solution of the master problem yields a lower bound (minimization) while the NLP subproblem provides an upper bound for the objective of the original MINLP. Solving these problems iteratively results in the reduction in the difference between these bounds. The difference between the bound given by the linear approximated subproblem and the optimal solution of the MINLP relies heavily on how well the linearizations approximate the nonlinear equations of the original problem.

Several previous contributions have proposed using quadratic approximations for MINLP decomposition methods. Grossmann[3] and Fletcher and Leyffer[2] discussed including 2^nd order derivative information in the master problem of the OA method. Specifically, considering the Hessian of the Lagrange function in the objective of the master problem gives rise to an Mixed –Integer Quadratic Problem (MIQP) problem. Also, Ding-Mei and Sargent[4] showed that the quadratic approximation helps to define NLP subproblems that have better initial guesses of the continuous variables from the MILP.

In this work, we propose a new approach for using quadratic accurately. In particular, we propose to use a scaled quadratic approximation of the nonlinear functions instead of a linear approximation and incorporate it into the OA method. This scaled quadratic approximation uses 2^nd order derivative information and therefore approximates the nonlinear functions more accurately than the linearization, yielding stronger lower bounds while ensuring the validity of the relaxation. The scaled quadratic cut is proved to be a stricter and tighter underestimation for convex nonlinear functions than classical supporting hyperplanes, which results in the improvement of the OA solution method. The resulting master problem becomes a Mixed-Integer Quadratically Constrained Program (MIQCP).

Having a quadratic approximation of the nonlinear constraints allows the master problem to provide a closer approximation of the continuous feasible region, and therefore, improve the lower bound provided by the relaxation[3]. Recently, MILP solvers like CPLEX[5] and Gurobi[6] have expanded their capabilities to efficiently solve MIQCP problems[7]. The crucial factor of MIQCP solvability is the Hessian matrix, the second-order partial derivatives matrix. Convex MIQCP problems, which have a positive semi-definite Hessian matrix, can be solved to optimality as one special convex MINLP with state-of-the-art MILP solvers. These developments allow us to consider quadratic objectives and constraints in the master problem. The Hessian of the nonlinear functions is available thanks to the NLP solvers, and therefore can be included in the problem efficiently.

The implementation of this method in the Mixed-Integer Nonlinear Decomposition Toolbox in Pyomo MindtPy is presented together with numerical results of benchmark MINLP problems demonstrate the effectiveness of the proposed MINLP solution methods with scaled quadratic cuts compared to the traditional OA method.

[1] M. A. Duran and I. E. Grossmann, “An outer-approximation algorithm for a class of mixed-integer nonlinear programs,” Math. Program., vol. 36, no. 3, pp. 307–339, 1986.

[2] R. Fletcher and S. Leyffer, “Solving mixed integer nonlinear programs by outer approximation,” Math. Program., vol. 66, no. 1–3, pp. 327–349, 1994.

[3] I. E. Grossmann, “Review of nonlinear mixed-integer and disjunctive programming techniques,” Optim. Eng., vol. 3, no. 3, pp. 227–252, 2002.

[4] Ding-Mei and R. W. H. Sargent, “A combined SQP and branch and bound algorithm for MINLP optimization,” London, 1992.

[5] IBM Corp. and IBM, “V12.6: User’s Manual for CPLEX,” Int. Bus. Mach. Corp., vol. 12, no. 1, p. 481, 2009.

[6] I. Gurobi Optimization, “Gurobi Optimizer Reference Manual,” Www.Gurobi.Com, p. 572, 2016.

[7] C. Bliek, P. Bonami, and A. Lodi, “Solving Mixed-Integer Quadratic Programming problems with IBM-CPLEX : a progress report,” Proc. Twenty-Sixth RAMP Symp., no. M, pp. 171–180, 2014.