(216a) Mindtpy: The Mixed-Integer Nonlinear Decomposition Toolbox in Pyomo

In process system engineering, Mixed-Integer Nonlinear Programming (MINLP) has a widespread application ranging from optimal process design and synthesis, process planning, scheduling, control, and molecular design [1]. However, the versatile modeling ability of continuous and discrete decisions and linear and nonlinear constraints also increases the computational complexity of finding its optimal solution. Over the last two decades, the algorithms for solving MINLPs have received growing attention, and significant progress has been made on both the theoretical and computational sides. Generally, the algorithms for MINLPs fall into two major categories, branch and bound-based method, and MILP decomposition-based method. Correspondingly, solvers can be classified using these categories. BARON [2], ANTIGONE [3], and SCIP [4] can be seen as branch-and-bound-based solvers, and solvers such as DICOPT [5],, BONMIN [6], SHOT [7], and Pajarito [8] being considered MILP decomposition-based.

This work presents the Mixed-Integer Nonlinear Decomposition Toolbox in Pyomo [9] (MindtPy), which is open-source and the first Python code to solve MINLPs. MindtPy supports different decomposition algorithms to solve both convex and nonconvex Mixed-Integer Nonlinear Programs(MINLP). For convex MINLP problems, MindtPy provides the Extended Cutting Plane (ECP) method, Outer-Approximation (OA) method, and a novel Regularized Outer-Approximation (ROA) method [10]. As a novel technique in MindtPy, the Regularized Outer-Approximation method solves an extra projection problem for finding new integer combinations to be used within the Outer-Approximation (OA) method. A set of regularization functions based on distance metrics and Lagrangean approximations are supported. This approach has been shown to be efficient for highly nonlinear convex MINLP problems. Besides that, the Feasibility Pump (FP) method has also been implemented in MindtPy as an initialization strategy to find feasible solutions and a standalone strategy to find optimal solutions. For nonconvex MINLPs, MindtPy provides both a local and a global Outer-Approximation method. The local Outer-Approximation method is based on two heuristic methods similar to those implemented in DICOPT, i.e., equality relaxation and augmented penalty. In the global Outer-Approximation method, the validity of the Mixed-integer Linear Programming relaxation of the original problem is guaranteed via Generalized McCormick envelopes, computed using the package MC++. Besides iteratively solving the MIP problem and the fixed NLP problem, MindtPy also supports the so-called single-tree implementation of decompositions algorithms, i.e. (global/regularized) LP/NLP based branch and bound algorithm. The MIP problem must be solved only once, and cuts are added through lazy constraints callback in the MIP solver. More importantly, MindtPy also integrates the above algorithms with advanced techniques such as solution pool, tabu-list, and Auto-Persistent Pyomo Solver Interfaces to perform better.

We perform a computational experiment considering convex and nonconvex MINLP problems in the benchmark library MINLPLib. The computational results demonstrate the competitive and promising performance of MindtPy to both open-source and commercial solvers.

A further advantage of MindtPy is that it is entirely based on Pyomo [9], making it easy to integrate with other Pyomo-based packages such as SUSPECT [11], Coramin, etc. Moreover, MindtPy follows the object-oriented programming paradigm designed to allow easy extension and modification of the core algorithm by users and developers. Therefore, MindtPy is also a good base version for new decomposition algorithm development and problem-specific decompositions method development.

References

[1] Grossmann, I. E. (2012). Advances in mathematical programming models for enterprise-wide optimization. Computers & Chemical Engineering, 47, 2-18.

[2] Ryoo, H. S., & Sahinidis, N. V. (1996). A branch-and-reduce approach to global optimization. Journal of global optimization, 8, 107-138.

[3] Misener, R., & Floudas, C. A. (2014). ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations. Journal of Global Optimization, 59(2-3), 503-526.

[4] Bestuzheva, K., Besançon, M., Chen, W. K., Chmiela, A., Donkiewicz, T., van Doornmalen, J., ... & Witzig, J. (2021). The SCIP optimization suite 8.0. arXiv preprint arXiv:2112.08872.

[5] Viswanathan, J., & Grossmann, I. E. (1990). A combined penalty function and outer-approximation method for MINLP optimization. Computers & Chemical Engineering, 14(7), 769-782.

[6] Bonami, P., Biegler, L. T., Conn, A. R., Cornuéjols, G., Grossmann, I. E., Laird, C. D., ... & Wächter, A. (2008). An algorithmic framework for convex mixed integer nonlinear programs. Discrete optimization, 5(2), 186-204.

[7] Lundell, A., Kronqvist, J., & Westerlund, T. (2022). The supporting hyperplane optimization toolkit for convex MINLP. Journal of Global Optimization, 84(1), 1-41.

[8] Coey, C., Lubin, M., & Vielma, J. P. (2020). Outer approximation with conic certificates for mixed-integer convex problems. Mathematical Programming Computation, 12(2), 249-293.

[9] Hart, W. E., Laird, C. D., Watson, J. P., Woodruff, D. L., Hackebeil, G. A., Nicholson, B. L., & Siirola, J. D. (2017). Pyomo-optimization modeling in python (Vol. 67, p. 277). Berlin: Springer.

[10] Bernal, D. E., Peng, Z., Kronqvist, J., & Grossmann, I. E. (2022). Alternative regularizations for Outer-Approximation algorithms for convex MINLP. Journal of Global Optimization, 84(4), 807-842.

[11] Ceccon, F., Siirola, J. D., & Misener, R. (2020). SUSPECT: MINLP special structure detector for pyomo. Optimization Letters, 14, 801-814.