A cross decomposition approach to stochastic nonconvex mixed-integer nonlinear programming
Emmanuel Ogbe, Xiang Li*
Department of Chemical Engineering, Queen's University,
19 Division Street, Kingston, ON, K7L 3N6, Canada
When considering uncertainties explicitly, many process systems engineering problems (such as process design and operation problems) can be cast as a two-stage stochastic program ; when nonlinear models and integer decisions are involved, the stochastic program leads to a large-scale nonconvex mixed nonlinear programming (MINLP) problem in the following general form:
Here ω indicates different scenarios, and the size of the problem depends linearly on the number of scenarios included. Problem (P) has a decomposable structure in the sense that, when x0 (called linking variable) is fixed, the problem is naturally decomposable over the scenarios. Therefore, a decomposition approach is often computationally more efficient than a regular solution method for solving Problem (P).
strategies have been developed in the literature for solving Problem (P). When
Problem (P) is partially convex (with respect to
This paper presents a cross decomposition approach that guarantees finding an ε-optimal solution in finite time, without the need of explicit branch-and-bound search and the convexity assumption for the problem. This approach is motivated by a cross decomposition method  that was originally developed for solving mixed-integer linear programming (MILP) problems with special structures. The basic idea of cross decomposition is to use two different decomposition approaches iteratively. The one that is more computationally efficient but less rigorous is performed more frequently, so that good quality solutions or even a global optimal solution can be generated quickly. The one that is relatively inefficient but able to guarantee convergence is performed only when necessary, so that the convergence of lower and upper bounds is guaranteed. It will be shown that, a cross decomposition framework that combines a variant of Dantzig-Wolfe decomposition (also a variant of Lagrangian decomposition) and generalized Benders decomposition, can be used to solve Problem (P) to global optimality, regardless of the convexity of the problem. It will be also shown that, with extensive domain reduction computation at each iteration of the cross decomposition, the efficiency of the cross decomposition can be significantly improved. The computational advantages of the proposed cross decomposition method over state-of-the-art global optimization solvers will be demonstrated through several process network design and operation problems.
 Birge, J. R.; Louveaux, F. Introduction to stochastic programming, Second Edition; Springer: New York, 2011.
 Benders, J. F. Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 1962, 4, 238-252.
 Geoffrion, A. M. Generalized Benders decomposition. Journal of Optimization Theory and Applications 1972, 10, 237–260.
 Dantzig, G. B.; Wolfe, P. Decomposition principle for linear programs. Operations Research 1960, 8, 101-111.
 Karuppiah, R.; Grossmann, I. E. A Lagrangean based branch-and-cut algorithm for global optimization of nonconvex mixed-integer nonlinear programs with decomposable structures. Journal of Global Optimization 2008, 41, 163-186.
 Carze, C. C.; Schultz, R. Dual decomposition in stochastic integer programming. Operations Research Letters 1999, 24, 37–45.
 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, 425-454.
 Van Roy, T. J. Cross decomposition for mixed integer programming. Mathematical Programming 1983, 25, 46-63.