(398c) Globally Optimizing Mixed-Integer Signomial Programs

We develop a computational framework for addressing mixed-integer signomial optimization problems (MISO) to epsilon-global optimality. Chemical engineering applications of MISO include heat exchanger network design, chemical reactor design, optimal condenser design, oxygen production, membrane separation process design, optimal design of cooling towers, chemical equilibrium problems, optimal control, batch plant modeling, and optimal location of hydrogen supply centers [13].

This work encompasses and extends previous development of the Global Mixed-Integer Quadratic Optimizer, GloMIQO [18, 19]. As in GloMIQO, our approach is based on (1) reformulating user input, (2) detecting special mathematical structure, and (3) branch-and-bound global optimization. All our solution strategies for quadratic programs are integrated into this work; this presentation highlights new components for signomial functions.

In the reformulation stage, we transform a factorable programming tree into a flattened expression tree. This automatic procedure effectively flattens nonconvex expressions from vertical, operator-based data structures (e.g., [8, 21]) to horizontal, term-based data structures (e.g., [1, 2, 12]).

In the detection stage, we elucidate special mathematical structure in the terms including convexity/concavity and edge-convexity/edge-concavity. The term-based data structures allow us easy access to specially developed tight convex underestimators for trilinear terms [15, 16], quadrilinear terms [6], odd-degree monomials [9], signomial terms [10, 11, 13], low-dimensional edge-concave terms [17, 22], products of convex functions [12], and general nonconvex terms [1, 2, 12]. In addition to discerning tight convex underestimators for individual terms, we interlink the terms using an implementation of the Reformulation-Linearization Technique that considers all possible combinations of products between variables, nonlinear terms, and equations [20].

In the global optimization stage, we use the special mathematical structure elucidated in the detection stage to: generate tight convex relaxations, dynamically add separating cuts, partition the search space, bound the variables, and find feasible solutions. Different underestimation strategies may have varying relative efficacy throughout the branch-and-bound tree [3, 8]; we generate candidate hyperplanes using an array of convexification strategies. Due to steep computational costs associated with generating the deepest possible cut, we temper our analysis of each cutting plane strategy with complexity analysis.

We extensively test and validate our work based on MINLPLib [5], GLOBALLib [7, 14], PerformanceLib, www.minlp.org, and the Bonmin test set [4].

References

[1] C. S. Adjiman, I. P. Androulakis, and C. A. Floudas. A global optimization method, aBB, for general twice differentiable NLPs-II. Implementation and computional results. Comput. Chem. Eng.,22:1159 – 1179, 1998b.

[2] C. S. Adjiman, S. Dallwig, C. A. Floudas, and A. Neumaier. A global optimization method, aBB, for general twice differentiable NLPs-I. Theoretical advances. Comput. Chem. Eng., 22:1137 – 1158, 1998a.

[3] A. Bompadre and A. Mitsos. Convergence rate of McCormick relaxations. J. Glob. Optim., 52(1):1–28, 2011.

[4] P. Bonami, L. T. Biegler, A. R. Conn, G. Cornuejols, I. E. Grossmann, C. D. Laird, J. Lee, A. Lodi, F. Margot, N. Sawaya, and A.Waechter. An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optimization, 5(2):186 – 204, 2008.

[5] M. R. Bussieck, A. S. Drud, and A. Meeraus. MINLPLib - a collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput, 15(1), 2003.

[6] S. Cafieri, J. Lee, and L. Liberti. On convex relaxations of quadrilinear terms. Journal of Global Optimization, 47:661–685, 2010.

[7] C. A. Floudas, P. M. Pardalos, C. S. Adjiman, W. R. Esposito, Z. H. Gumus, S. T. Harding, J. L. Klepeis, C. A. Meyer, and C. A. Schweiger. Handbook of Test Problems in Local and Global Optimization.  Kluwer Academic Publishers, 1999.

[8] E. P. Gatzke, J. E. Tolsma, and P. I. Barton. Construction of convex relaxations using automated code generation techniques. Optim. Eng., 3:305–326, 2002.

[9] L. Liberti and C. C. Pantelides. Convex envelopes of monomials of odd degree. J. Glob. Optim., 25:157–168, 2003.

[10] A. Lundell, J. Westerlund, and T. Westerlund. Some transformation techniques with applications in global optimization. J. Glob. Optim., 43:391–405, 2009.

[11] A. Lundell and T. Westerlund. Convex underestimation strategies for signomial functions. Optim. Methods Software, 24(4-5):505–522, 2009.

[12] C. D. Maranas and C. A. Floudas. Finding all solutions of nonlinearly constrained systems of equations. J. Glob. Optim., 7(2):143–182, 1995.

[13] C. D. Maranas and C. A. Floudas. Global optimization in generalized geometric programming. Comput. Chem. Eng., 21(4):351 – 369, 1997.

[14] A. Meeraus. GLOBALLib. http://www.gamsworld.org/global/globallib.htm.

[15] C. A. Meyer and C. A. Floudas. Trilinear monomials with positive or negative domains: Facets of the convex and concave envelopes. In C. A. Floudas and P. M. Pardalos, editors, Frontiers in Global Optimization, pages 327–352. Kluwer Academic Publishers, 2003.

[16] C. A. Meyer and C. A. Floudas. Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes. J. Glob. Optim.,29(2):125–155, 2004.

[17] C. A. Meyer and C. A. Floudas. Convex envelopes for edge-concave functions. Math. Program.,103(2):207–224, 2005.

[18] R. Misener and C. A. Floudas. Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations. Math. Program. B. Accepted for Publication; http://www.optimization-online.org/DB_HTML/2011/11/3240.html.

[19] R. Misener and C. A. Floudas. GloMIQO: Global Mixed-Integer Quadratic Optimizer. J. Glob. Optim. Accepted for Publication (DOI: 10.1007/s10898-012-9874-7).

[20] H. D. Sherali and W. P. Adams. A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht, Netherlands, 1999.

[21] E. M. B. Smith and C. C. Pantelides. A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Computers & Chemical Engineering, 23(4 - 5):457– 478, 1999.

[22] F. Tardella. Existence and sum decomposition of vertex polyhedral convex envelopes. Optim. Lett., 2:363–375, 2008.