(545e) Nonconvex Generalized Benders Decomposition and Piecewise Convex Relaxations for Optimal Process Design and Operation Under Uncertainty

Integrated process design and operation problems are often cast as mathematical programming problems for systematic solution. If a process involves uncertain factors that could impact the process performance significantly, the uncertainties need to be explicitly addressed in the mathematical programming, which results in a stochastic programming problem.

Recently, a nonconvex generalized Benders decomposition (NGBD) [1] has been developed to solve a class of stochastic nonconvex mixed-integer nonlinear programming (MINLP) problems arising from integrated process design and operation under uncertainty. By exploiting the decomposable structure of the problem, NGBD can solve the problem to global optimality finitely, and it exhibits dramatic computational advantages over traditional branch-and-bound based global optimization methods. As the convergence rate of NGBD is largely dependent on the tightness of the convex relaxations of the nonconvex functions, the efficiency of NGBD can be significantly improved by generating tighter convex relaxations.

It has been recognized in the process systems engineering literature that piecewise linear relaxation enables much tighter relaxation of bilinear programs and can expedite global optimization significantly in the branch-and-bound framework (e.g. [2] [3] [4] [5]). This paper generalizes the notion of piecewise relaxation to factorable functions in the context of McCormick relaxation [6] [7] and integrates the so-obtained piecewise McCormick relaxation technique into the NGBD algorithm to reduce the gap between the original problem and its convex relaxation. In addition, most subproblems in a NGBD iteration can be solved without exchanging information among them, and therefore they can be solved in parallel to reduce the solution time. The parallelization for NGBD will be briefly discussed in the paper as well.

Case studies of a pump network configuration problem [8] and an energy polygeneration problem [9] show that, while NGBD can solve problems that are intractable for a state-of-the-art global optimization solver (BARON [10]), integrating the proposed piecewise convex relaxation into NGBD helps to reduce the solution time by up to an order of magnitude. The case study results also show that parallel computation can reduce the NGBD solution time significantly.

References

[1] Li, X.; Tomasgard, A.; Barton, P. I. Nonconvex generalized Benders decomposition for stochastic separable mixed-integer nonlinear programs. Journal of Optimization Theory and Applications 2011, 151, 3, 425-454.

[2] Karuppiah, R.; Grossmann, I. E. Global optimization for the synthesis of integrated water systems in chemical processes. Computers and Chemical Engineering 2006, 30, 650–673.

[3] Meyer, C. A.; Floudas, C. A. Global optimization of a combinatorially complex generalized pooling problem. AIChE Journal 2006, 52, 1027–1037.

[4] Wicaksono, D. S.; Karimi, I. A. Piecewise MILP under- and overestimators for global optimization of bilinear programs. AIChE Journal 2008, 54, 991–1008.

[5] Gounaris, C. E.; Misener, R.; Floudas, C. Computational comparison of piecewise-linear relaxations for pooling problems. Industrial and Engineering Chemistry Research 2009, 48, 5742–5766.

[6] McCormick, G. P. Computability of global solutions to factorable nonconvex programs: Part I - Convex underestimating problems. Mathematical Programming 1976, 10, 147–175.

[7] Scott, J. K.; Stuber, M. D.; Barton, P. I. Generalized McCormick relaxations. Journal of Global Optimization 2011, 51, 4, 569-606.

[8] Westerlund, T.; Pettersson, F.; Grossmann, I. E. Optimization of pump configurations as a MINLP problem. Computers and Chemical Engineering 1994, 18, 845–858.

[9] Chen, Y.; Adams II, T. A.; Barton, P. I. Optimal design and operation of flexible energy polygeneration systems. Industrial and Engineering Chemistry Research 2011, 50, 4553–4566.

[10] Tawarmalani, M.; Sahinidis, N. V. Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Mathematical Programming 2004, 99, 563–591.