A Cross Decomposition Method for Stochastic Nonconvex Mixed-Integer Nonlinear Programming

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 [1]; 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:

                                (P)

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 x₀ (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).

Various decomposition strategies have been developed in the literature for solving Problem (P). When Problem (P) is partially convex (with respect to ) and some constraint qualification holds, Benders decomposition [2] or generalized Benders decomposition [3] can be used to solve Problem (P) to global optimality. Furthermore, if Problem (P) is fully convex, then Dantzig-Wolfe decomposition [4] can also be used to achieve an optimal solution. However, when set  or/and functions ,  are nonconvex, classical decomposition approaches cannot guarantee convergence to a global optimal solution due to the loss of strong duality. Recently, two rigorous decomposition-based global optimization methods have been developed for solving Problem (P) that includes nonconvexity in  space. One method utilizes Lagrangian decomposition [5][6], but needing branch-and-bound search in the x₀ space to guarantee global optimality. The other is a variant of (generalized) Benders decomposition that yields values for x₀ via solving convex lower bounding problems, but the convergence to a global optimal solution is guaranteed only when x₀ are integer variables [7].

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

References

[1] Birge, J. R.; Louveaux, F. Introduction to stochastic programming, Second Edition; Springer: New York, 2011.

[2] Benders, J. F. Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 1962, 4, 238-252.

[3] Geoffrion, A. M. Generalized Benders decomposition. Journal of Optimization Theory and Applications 1972, 10, 237–260.

[4] Dantzig, G. B.; Wolfe, P. Decomposition principle for linear programs. Operations Research 1960, 8, 101-111.

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

[6] Carze, C. C.; Schultz, R. Dual decomposition in stochastic integer programming. Operations Research Letters 1999, 24, 37–45.

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

[8] Van Roy, T. J. Cross decomposition for mixed integer programming. Mathematical Programming 1983, 25, 46-63.