(184b) Globally Optimizing Mixed-Integer Quadratically-Constrained Quadratic Programs: Advances in Glomiqo

Major applications of mixed-integer quadratically-constrained quadratic optimization problems (MIQCQP) include quality blending in process networks, separating objects in computational geometry, and portfolio optimization in finance [10]. Specific instantiations of MIQCQP in process networks optimization problems include: pooling problems, distillation sequences, wastewater treatment and total water systems, hybrid energy systems, heat exchanger networks, reactor-separator-recycle systems, separation systems, data reconciliation, batch processes, crude oil scheduling, and natural gas production. Computational geometry problems formulated as MIQCQP include: point packing, cutting convex shapes from rectangles, maximizing the area of a convex polygon, and chip layout and compaction. Portfolio optimization in financial engineering can also be formulated as MIQCQP.

We consider a general framework for deterministically addressing MIQCQP to epsilon-global optimality [9, 10]. Algorithmic components include: reformulating user input, detecting special mathematical structure, generating tight convex relaxations, dynamically adding separating cuts, partitioning the search space, bounding variables, and finding feasible solutions. We consider individual solution strategies and their practical interaction.

We discuss computational experience with the Global Mixed-Integer Quadratic Optimizer, GloMIQO. GloMIQO is validated against a MIQCQP test suite including the following problem classes: process networks; computational geometry; maximum clique; quadratic assignment. We also address standard test library examples from MINLPLib [4], GLOBALLib [5, 7], PerformanceLib, www.minlp.org, and the Bonmin test set [3].

New components in GloMIQO include integrating a validated interval arithmetic library, dynamically adding separating hyperplanes, addressing discrete/discrete and discrete/continuous products, selectively adding bilinear terms to the model for advanced application of the Reformulation-Linearization Technique (RLT) [6], eliminating bilinear terms based on knapsack constraint inferences, and removing RLT equations to expedite the search for feasible solutions. With respect to the cutting planes, we highlight the inherit complementarity between globally valid cuts derived from alphaBB convexification [1, 2] and locally valid cuts based on higher-order (4 - 7D) edge-concave expressions [8, 11, 12].

References

[1] C. S. Adjiman, I. P. Androulakis, and C. A. Floudas. A global optimization method, alphaBB, 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, alphaBB, for general twice differentiable NLPs-I. Theoretical advances. Comput. Chem. Eng.,22:1137 – 1158, 1998a.

[3] 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.

[4] 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.

[5] 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.

[6] L. Liberti and C. C. Pantelides. An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms. J. Glob. Optim., 36(2):161–189, 2006.

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

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

[9] 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.

[10] 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).

[11] A. D. Rikun. A convex envelope formula for multilinear functions. J. Glob. Optim., 10:425 – 437, 1997.

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