**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:

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*_{0} (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
* _{0}* 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*

_{0}*are integer variables [7].*

_{0}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.

**Extended Abstract:**File Not Uploaded

See more of this Group/Topical: Computing and Systems Technology Division