(253e) On Piecewise Under- and over-Estimators of Fractional Terms

Fractional terms are encountered in a wide variety of applications including heat exchange networks, multicomponent distillation sequences, etc. The nonconvexity of fractional terms poses a challenge for local solvers, which can get trapped in a local optimal solution. In contrast, global solvers implement spatial branch-and-bound, which finds the global optimum by iteratively refining the search domain. In this process, the global solvers use bounds on the optimum, which are derived by replacing the fractional terms with a convex outer-approximation. The standard relaxation process involves replacing each fractional term with an auxiliary variable, which is then overestimated by its concave envelope [1 – 4] and underestimated by either an outer-linearization of the bilinear term [4], a quadratic/linear underestimator [1,3], and/or its convex envelope [3]. However, empirical computational evidence suggests that, for many practical models that involve fractional terms, particularly if they also involve combinatorial choices, the state-of-the-art solvers may either fail to converge or do so rather slowly. In contrast, MI(L/SOC)P solvers have improved drastically, over the last two decades, and can now handle reasonably large instances. Here, we explore ways to use the MI(L/SOC)P solvers to solve hard (MI)NLP instances involving fractional terms to near optimality, which is not possible with current global solvers.

We consider various ways of constructing piecewise under- and over-estimators of fractional terms. These estimators are obtained using outer-linearization of bilinear terms [1 – 4], quadratic/linear underestimator [1,3], and outer-approximation followed by outer-linearization, an approach recently proposed in [5]. Since these relaxations rely heavily on bounds, we introduce binary variables, and use the incremental cost formulation [6] along with the reformulation-linearization technique [7] to develop piece-wise relaxations. This step differs from the standard approach of constructing IP relaxations via piecewise relaxations of bilinear terms obtained after cross-multiplying the fractional term. We show that using the proposed IP relaxations we are able to solve, for the first time, to near optimality, an MINLP that identifies optimal multicomponent distillation sequences. The fractional terms in this formulation arise from Underwood equations and the combinatorial choices model the structural specification of the distillation configuration. We present computational results, in the context of this application, comparing the efficacy of various estimators for the fractional terms.

1. Zamora, J. M., & Grossmann, I. E. (1998). A global MINLP optimization algorithm for the synthesis of heat exchanger networks with no stream splits. Computers & Chemical Engineering, 22(3), 367-384.
2. Zamora, J. M., & Grossmann, I. E. (1999). A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms. Journal of Global Optimization, 14(3), 217-249.
3. Tawarmalani, M., & Sahinidis, N. V. (2001). Semidefinite relaxations of fractional programs via novel convexification techniques. Journal of Global Optimization, 20(2), 133-154.
4. Tawarmalani, M., & Sahinidis, N. V. (2002). Convexification and global optimization in continuous and mixed-integer nonlinear programming: theory, algorithms, software, and applications (Vol. 65). Springer Science & Business Media.
5. He, T., & Tawarmalani, M. On relaxing composite functions exploiting inner function structure: polynomially equivalent formulations. Working paper.
6. Dantzig, G. B. (1960). On the significance of solving linear programming problems with some integer variables. Econometrica, Journal of the Econometric Society, 30-44.