Nonconvex Generalized disjunctive programming (GDP)

From optimization
Revision as of 16:36, 7 June 2015 by Kld187 (Talk | contribs)

Jump to: navigation, search

Author: Kaiwen Li (ChE345 Spring 2015)

Contents

Introduction

General disjunctive programming, GDP, is an alternative approach to represent the formulation of traditional Mixed-Integer Nonlinear Programming, solving discrete/continuous optimization problems. By using algebraic constraints, disjunctions and logic propositions, Boolean and continuous variables are involved in the GDP formulation. The formulation process of GDP problem are more intuitive, and the underlying logic structure of the problem can be kept, so that solution can be found more efficiently. GDP has been successfully applied to Process Design and Planning and Scheduling areas.

However, funtions in GDP problem sometimes could be nonconvex. Due to nonconvexites, conventional MINLP algorithms are often trapped in suboptimal solutions. Thus, solutions to nonconvex GDP has been receiving increasing attention.

Algorithm

In the GDP formulation, some functions might be nonconvex, which will lead to a nonconvex GDP problem. Traditional algorithms for MINLP such as Generalized Benders Decomposition (GBD), or Outer Approximation (OA) will fail to provide a global optimum because the solution of the NLP subproblem can be only a local optimum, while the cuts in master problem may not be valid either. Therefore, in order to get a global optimum, we need to introduce special algorithm for nonconvex GBD problems.
Most of the methods rely on spatial branch and bound method.

Motivation

Increased attention has been received to solution of Mixed-Integer Nonlinear Programming (MINLP) models because its practical importance in engineering and many other areas.

Formulation and Models

General Formulation for GDP

Consider the following Generalized Disjunctive Programming problem, which includes Boolean variables, disjunctions and logic propositions:
min Z = \sum_{k\in K} c_k + f(x)

s.t. r(x)\le 0

\bigvee_{j\in J_k} \begin{bmatrix} Y_{jk} \\ g_{jk}(x) \le 0 \\ c_k = \gamma_{jk} \end{bmatrix},  k\in K

\Omega(Y) = True

0 \le x \le U

x \in R^n,  c_k \in R^1,  Y_{jk} \in {true, false}

where, f:R^n \rightarrow R^1 is a function of the continuous variables x in the objective function, g:R^n \rightarrow R^1 bolongs to the set of global constraints, the disjuctions  k\in K are composed of a number of terms  j\in J_k, which is connected by the OR operator. Y_{jk} is a Boolean varibale, g_{jk}(x) \le 0 is a set of inequalities, and c_k is a cost variable. When Y_{jk} is true, g_{jk}(x) \le 0 and c_k are enforced.Also, xrepresents continuous variables, with lower and upper bounds.Each term in the disjunctions gives rise to a nonempty feasible region which is generally nonconvex. Also, \Omega(Y) = True
are logic propositions for the Boolean variables.

Overall Procedure

The following flowchart(Fig.1) shows the overall procedure of the proposed two-level branch and bound algorithm. Flowchart01 KL.png
First, introduce convex underestimators in the non-convex GDP problem (P), and construct the underestimating problem (R). This convex GDP problem is then reformulated as the convex NLP problem (CRP) by using the convex hull relaxation of each disjunction, which generates valid lower bound. Initial upper bound is obtained in step 0, by sloving P-MIP problem. It is a MINLP reformulation of the nonconvex GDP by a standard MINLP method. Then, use upper bound for bound contraction to reduce the feasible region, which is solved as a Bound Contraction Problem (BCP) in step 1. Next in step 2, discrete branch and bound method is applied at the first level to slove problem (CRP). After fixing all Boolean variables, solve the corresponding nonconvex NLP problems for a upper bound by using spatial branch and bound at the second level. Then, problem (CRP) is solved with fixed discrete choice in step 3.

Convex Relaxation of GDP

The following reformulation shows the introduction of valid convex underestimating functions to change Problem (P) into a convex GDP problem.

min Z^R = \sum_{k\in K} c_k + \bar{f}(x)

s.t. \bar{r}(x)\le 0

\bigvee_{j\in J_k} \begin{bmatrix} Y_{jk} \\ \bar{g}_{jk}(x) \le 0 \\ c_k = \gamma_{jk} \end{bmatrix},  k\in K

\Omega(Y) = True

0 \le x \le U
,c_k \ge 0
x \in R^n, c_k \in R^1,  Y_{jk} \in \{ true, false\}

where \bar{f},\bar{r},\bar{g} are valid convex underestimators so that \bar{f}(x) \le f(x), \bar{r}(x) \le 0,\bar{g}(x) \le 0 are satisfied if r(x) \le 0,g(x) \le 0 (see fig.2)
Fig02 KL.png
Considering problem (R) is a convex GDP, by replacing each disjunction by its convex hull we can relax problem (R), which generates the folloing convex NLP model:

min Z^L = \sum_{k\in K}\sum_{j\in J_k} \gamma_{jk}\lambda_{jk} + \bar{f}(x)

s.t. \bar{r}(x)\le 0

 x = \sum_{j \in J_k} \nu_{jk}, \sum_{j \in J_k} \lambda_{jk} = 1,  k\in K

 0 \le \nu_{jk} \le \lambda_{jk}U_{jk}, j \in J_k, k\in K

 \lambda_{jk}\bar{g}_{jk}(\nu_{jk}/\lambda_{jk}) \le 0, j \in J_k, k\in K

 A\lambda \le a
0 \le x, \nu_{jk} \le U, 0 \le \lambda_{jk} \le 1, j \in J_k, k\in K, (CRP)

where \nu_{jk} is the disaggregated continuous variable for the j th term in the k th disjunction and \lambda_{jk} is the corresponding multiplier for each term j \in J_k in a given disjunction k\in K
Given the problem (R) yields a lower bound, the problem (CRP) is a relaxation of problem (R).

Global Upper Bound Subproblem

This is step is to obtain a valid upper bound for problem (P) based on MINLP reformulation of (P) using big-M formulation.
min Z = \sum_{k\in K}\sum_{j\in J_k} \gamma_{jk}y_{jk} + f(x)

s.t. r(x)\le 0

g_{jk}(x) \le M_jk(1-y_jk), j \in J_k, k\in K

 x = \sum_{j \in J_k} y_{jk}= 1,  k\in K

 Ay \le a
0 \le x \le U, y_{jk} \in \{0,1\}, j \in J_k, k\in K, (P-MIP)

where M_jk is the big-M parameter, which provides a valid upper bound to the violation of g_jk \le 0 and U is an upper bound to x.

Bound Contraction Procedure

jiji


For the feasible region relaxation, just replace each disjunction by its convex hull, which leads to the following convex NLP problem with a lower bound of the global optimum, proven by Lee & Grossmann:

Step1 AfterRelaxation.png

Second Step - Predict Lower Bounds using spatial brand and bound. The detailed procedures are as follows:

  1. Solve MINLP reformulation to get a local solution as upper bound (Z^U).
  2. Bound contraction by Zamora and Grossmann (1999).
  3. Use partial branch and bound by Lee & Grossmann (1999), until a node with all the Boolean variables fixed is reached.
  4. Spatial branch and bound by Quesada and Grossmann (1995).

which can be summarized as the following diagram:
Alt text

Enhanced Methodology

Ruiz and Grossmann proposed a stronger relaxation methodology based on Saway & Grossmann's work. The key point in the methodology is to use valid linear over- and underestimators before applying basic steps, to further restrict the relaxation of the nonconvex terms, and end up with a new linear GDP with a tighter continuous relaxation.

Advantages and Disadvantages

Applications and Examples

  1. Water Treatment Network (Galan and Grossmann, 1998)

The problem tries to solve the interconnections of technologies and flowrates to reach the minimum total cost for a water treatment system, after which a set of process liquid streams with known composition can meet the specified discharge composition of pollutant. Discrete choices involve deciding what equipment to use for each unit. The system is shown by the following diagram:

Example water treatment.png

An nonconvex GDP problem, with 9 discrete variables, 114 continuous variables and 36 bilinear terms, was formulated by Lee & Grossmann as follows:
Example water treatment solution.png


The authors also compared different algorithms in terms of performance, the conclusion is the enhanced methodology improved the original algorithm. It is proven by lower bounds results, spatial B&B, and size of LP relaxation.

Conclusion

For nonconvex generalized disjunctive programming, specified algorithm can provide a global optimum more efficiently, compared with conventional MINLP and GBD algorithms.

References

  1. Lee, Sangbum, and Ignacio E. Grossmann. "New algorithms for nonlinear generalized disjunctive programming." Computers & Chemical Engineering 24.9 (2000): 2125-2141.
  2. Lee, Sangbum, and Ignacio E. Grossmann. "A global optimization algorithm for nonconvex generalized disjunctive programming and applications to process systems." Computers & Chemical Engineering 25.11 (2001): 1675-1697.
  3. Lee, Sangbum, and Ignacio E. Grossmann. "Global optimization of nonlinear generalized disjunctive programming with bilinear equality constraints: applications to process networks." Computers & chemical engineering 27.11 (2003): 1557-1575.
  4. Grossmann, Ignacio E., and Juan P. Ruiz. "Generalized Disjunctive Programming: A framework for formulation and alternative algorithms for MINLP optimization." Mixed Integer Nonlinear Programming. Springer New York, 2012. 93-115.