(508f) 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.