(315f) Tightening Mccormick Relaxations Via Reformulation of Intermediate Functions into Schema

Generalized McCormick relaxations [2] can present significant boons in global optimization applications. This framework allows for the relaxation and subsequent optimization of algorithmically-defined functions that naturally arise during flowsheet modeling. Relaxations of functions considered under this theory exhibit quadratic convergence, helping to reduce the degree of clustering in spatial branch-and-bound algorithms [1-4]. Moreover, this simulation-based feasible-path approach enables the solution of flowsheeting problems in a reduced-dimension decision space, in contrast to the higher-dimensionality “lifting” of the decision space required by state-of-the-art auxiliary variable methods (AVMs) [5-6].

McCormick relaxations are typically calculated by overloading common arithmetic operators [2,3] in object-oriented programming languages [7]. Most recent research in McCormick-related relaxations have focused on providing improvements to the properties of these calculations to yield tighter relaxations, faster. Mitsos et al. developed tighter multivariate relaxations [8]. Khan et al. extended this to develop differentiable analogs [9]. Recently, Najman et al. extended this standard framework; provided tighter relaxations by using affine relaxations to shrink the associated interval bounds [10]. This represents one of the first usages of a reformulation of the directed-acyclic-graphs (DAGs) to tighten McCormick relaxations.

Analysis of the DAG representation of functions has been used in many applications ranging from constraint-satisfaction problems to scheduling [11,12]. Recently, the usage of convex-transformable functions was explored within the BARON context resulting in a significant improvement to performance on standard benchmark libraries [13]. Khajavirad et al. identified a number of regular expressions in DAGs that allow for tighter relaxations when relaxed directly [14]. In this work, we discuss the potential of tightening McCormick relaxations via the reformulation of intermediate functions.

Rather than define a series of regular expressions, we define a series of schema based on various functional attributes (convexity information). A graph theoretic approach to identifying potential intermediate function reformulations is developed that allows for reformulation presented in terms of cut vertices [15-17]. At these potential points of reformulation, a series of general tests based on interval arithmetic are applied to determine the function schema. This approach makes use of the abstract-syntax tree (AST) feature of Julia [18] to dynamically build tighter convex and concave relaxations of expressions belonging to these schemata. A series of examples from both the COCONUT library and extant literature are presented [19].

[1] McCormick, G.P. Computability of Global Solutions to Factorable Nonconvex Programs: Part I – Convex Underestimating Problems. Mathematical Programming 10: 147-175, 1976.

[2] Scott, J.K., Stuber, M.D., and Barton, P.I. Generalized McCormick Relaxations. J Global Optim, 51:569-606, 2011.

[3] Mitsos, A., Chachuat, B., and Barton, P.I. McCormick-Based Relaxations of Algorithms. SIAM J. Optim. 20(2): 573-601.

[4] Bompadre A. and Mitsos A. Convergence rate of McCormick relaxations. J Global Optim, 52(1):1-28, 2012.

[5] Tawarmalani, M. and Sahinidis, N. V. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming, 103(2), 225-249, 2005.

[6] Sahinidis, N. V., BARON 14.4.0: Global Optimization of Mixed-Integer Nonlinear Programs, User's manual, 2014.

[7] Chachuat, B. MC++ 2.0 [Computer Software]. (2017) Retrieved from https://omega-icl.github.io/mcpp.

[8] Tsoukalas, A. and Mitsos, A. Mutlivariate McCormick Relaxations. J Global Optim, 59:633-662, 2014.

[9] Khan, K.A., Watson, H.A., and Barton, P.I. Differentiable McCormick Relaxations. J Global Optim, 67(4):687-729, 2017.

[10] Najman, J. and Mitsos, A. Tighter McCormick Relaxations through Subgradient Propagation, arXiv preprint arXiv:1710.09188, 2017

[11] X. H. Vu, H. Schichl and D. Sam-Haroud. Using directed acyclic graphs to coordinate propagation and search for numerical constraint satisfaction problems. 16th IEEE International Conference on Tools with Artificial Intelligence, pp. 72-81, 2004.

[12] Baskiyar, Sanjeev, and Rabab Abdel-Kader. "Energy aware DAG scheduling on heterogeneous systems." Cluster Computing 13.4 (2010): 373-383.

[13] Nohra, C. “Global Optimization of Nonconvex Problems with Convex-Transformable Intermediates” 2017 Fall AIChE Meeting, Minneapolis, MN.

[14] A. Khajavirad, J. J. Michalek, and N. V. Sahinidis. Relaxations of factorable functions with convex-transformable intermediates. Mathematical Programming, 144:107–140, 2014

[15] Merris, R. Graph Theory. John Wiley & Sons, Inc., Hoboken, NJ, USA. doi: 10.1002/9781118033043, 2000.

[16] Schmidt, Jens M. A Simple Test on 2-Vertex- and 2-Edge-Connectivity. Information Processing Letters, 113 (7): 241-244, 2013.

[17] Fourer, R. et al. Convexity and Concavity Detection in Computational Graphs: Tree Walks for Convexity Assessment. INFORMS Journal on Computing 22.1: 26-43, 2010.

[18] Bezanson, J. et al. Julia: A fresh approach to numerical computing. SIAM Review. 59, 65-98, 2017.

[19] O. Shcherbina, et al. Benchmarking Global Optimization and Constraint Satisfaction Codes, In Global Optimization and Constraint Satisfaction, Bliek, Ch., Jermann, Ch. and Neumaier, A. Springer, Berlin 2003, 212-222.