# Difference between revisions of "Nonconvex Generalized disjunctive programming (GDP)"

Jump to: navigation, search

Author: Kaiwen Li (ChE345 Spring 2015)

# 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, $x$represents 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.
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)

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$.

### 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.

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

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

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.