(348e) A Homotopy Continuation-Based Branch and Bound Algorithm for Strongly Nonconvex Mixed Integer Nonlinear Programming Problems in Process Synthesis

Energy crisis, global competition and expectation for sustainability are driving chemical engineers to design more efficient and sustainable chemical processes1. In process synthesis and design problems, there are many structural, design and operating variables that need to be determined. In addition, rigorous unit operation models should be used to accurately predict the process performance in order to guarantee the reliability of the design results. This often leads to a large-scale strongly nonlinear and nonconvex mixed-integer nonlinear programming (MINLP) problem.

The well-known global optimiser such as BARON2 and ANTIGONE3 can be used to solve the problem to global optimality, but they usually cannot converge or even find a feasible solution within acceptable computational time. The outer approximation (OA)4 and branch and bound (B&B) algorithms5 can often used to solve the problem to local optimality within reasonable computational time although they cannot guarantee the global solution is found. However, for strongly nonlinear and nonconvex MINLP problems, they are vulnerable to failing due to divergence in solving the NLP subproblem at some nodes or iterations, which is the issue to be tackled in the current work.

In this work, we employ the homotopy continuation (HC) method6 to improve the convergence of solving NLP subproblems in B&B algorithm. At each node, the generalized reduced gradient (GRG) algorithm7 is employed to find an optimal solution for the NLP subproblem using the solution from its parent node as the initial point. If it fails, the branch binary variable is selected as the homotopy variable, and then we approach its required value (i.e., the value at the current node) gradually from the initial value (i.e., the value in its parent node) through changing a homotopy parameter t from 0 to 1. During the homotopy, the parameter t increases when a converged solution is generated. Otherwise, it decreases. The homotopy iterations continue until an optimal solution is found at t = 1 or the maximum number of homotopy steps reaches. The former indicates we get the optimal solution of the current node successfully, while the latter indicates the NLP problem is infeasible.

The synthesis and design of four chemical processes from literature8, 9 are used to validate the capability of the proposed HC-based B&B algorithm (HCBB). It is shown that the proposed algorithm is able to converge to the best local optimum for all the case studies from different initial points, whilst BARON and ANTIGONE fails to find a feasible solution in 1 h. On the other hand, the SBB/GAMS solver10 and DICOPT/GAMS solver4 can only solve some of the problems. More importantly, they can provide a worse local optimum from some initial points.

References
1. Recker, S.; Skiborowski, M.; Redepenning, C.; Marquardt, W., Systematic and Optimization-Based Design of Integrated Reaction-Separation Processes. In Computer Aided Chemical Engineering, Eden, M. R.; Siirola, J. D.; Towler, G. P., Eds. Elsevier: 2014; Vol. 34, pp 417-422.
2. Tawarmalani, M.; Sahinidis, N. V., A polyhedral branch-and-cut approach to global optimization. Mathematical Programming 2005, 103, (2), 225-249.
3. Misener, R.; Floudas, C. A., ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations. Journal of Global Optimization 2014, 59, (2), 503-526.
4. Duran, M. A.; Grossmann, I. E., An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Mathematical Programming 1986, 36, (3), 307-339.
5. Land, A. H.; Doig, A. G., An Automatic Method of Solving Discrete Programming Problems. Econometrica 1960, 28, (3), 497-520.
6. Allgower, E. L. A. G., Kurt, Introduction to Numerical Continuation Methods.
7. Drud, A., CONOPT: A GRG code for large sparse dynamic nonlinear optimization problems. Mathematical Programming 1985, 31, (2), 153-191.
8. Zhang, X.; Song, Z.; Zhou, T., Rigorous design of reaction-separation processes using disjunctive programming models. Computers & Chemical Engineering 2018, 111, 16-26.
9. Douglas, J. M., A hierarchical decision procedure for process synthesis. AIChE Journal 1985, 31, (3), 353-362.
10. Corporation, G. D. General Algebraic Modeling System (GAMS) Release 24.3, Fairfax, VA, USA, 2019.