Convex Generalized disjunctive programming (GDP)

From optimization
Jump to: navigation, search

Author: Yunjie Wang (ChE 345 Spring 2015)

Steward: Dajun Yue, Fengqi You

Contents

1. Background

Introduction

The generalized disjunctive programming (GDP) was first introduced by Raman and Grossman (1994). The GDP extends the use of (linear) disjunctive programming (Balas, 1985) into mixed-integer nonlinear programming (MINLP) problems, and hence the name. The GDP enables programmers to solve the MINLP/MILP optimization problems by applying a combination of algebraic formulation and logic-based formulation, reformulating them into normal MINLP/MILP problems, and then solving them with MINLP/MILP algorithms. The permission for using logic propositions makes the formulation process more direct and intuitive for problems involving choices and decisions, and such formulation may lead to the solution faster than the regular MINLP formulation. The GDP can be further categorized as the convex GDP and the nonconvex GDP. The GDP sees great application in process planning and optimization problems that involve decisions among a number of choices of equipment, reaction pathways, material inputs, and outputs, etc. In this Wiki page, the convex GDP is addressed. The description of nonconvex GDP can be found here.


MINLP

Formulation

A mixed-integer nonlinear programming (MINLP) problem involves both nonlinear terms and discrete integer variables in the objective function or/and the constraints in addition to basic linear programming. MINLP bears the form as shown below.

MINLP.png

where f is the objective function, and g_{j} are the constraints. Both can be nonlinear. X represents a convex compact set, and Y =0,1.


Algorithm

A MINLP problem can be solved using two methods. The first method is Branch and Bound. It enumerates the possible combinations of the solutions to the binary integers in the form of a decision tree. Then each node becomes an NLP problem and can be readily solved using NLP algorithms. Comparison between the branches are made to eliminate sub-optimal branches during the calculation to enhance the efficiency of the search.


The second method is to decompose the MINLP problem into NLP and MILP subproblems to find the upper and lower bounds of the solution to the objective function and make the solution converge through iterations. Some popular methods include Outer-Approximation (OA), Generalized Benders decomposition (GBD), and Extended cutting plane (ECP).

MINLP decomposition.png


2. GDP Method

Formulation

Instead of using equations and inequalities to formulate system constraints, a generalized disjunctive programming (GDP) method makes it easy to incorporate logic expressions into constraints. A standard form of GDP is shown below.

GDP.png

where f is a function of continuous variables x, g_{j} denotes common constraints, \Omega is a condensed form of logic propositions of Y_{ik}, and r_{ik} and c_{k} denote constraints and fixed charges within the disjunction k.


Reformulation

To solve for a GDP problem using existing solvers, one has to first translate the problem into a MINLP problem by reformulating all the logic expressions into algebraic forms. Two common reformulation methods are the Big-M and the Convex Hull reformulation.

Big-M Reformulation

Below is the general form of reformulated GDP by the Big-M Reformulation.

BigM.png

where M are sufficiently large constants.


Convex Hull Reformulation

Below is the general form of reformulated GDP by the Convex Hull Reformulation.

ConvexHull.png

where x are disaggregated into a sum of variables v^{ik} for each disjunction.


Solution

After reformulation, the GDP problems are solved using algorithms for MINLP problems as discussed in the introduction.


Solvers

After reformulation, all convex GDP problems can be solved using a software package like GAMS or AMPL with inbuilt codes for the MINLP. Below is a list of common algorithms for MINLP in GAMS.


SBB - Bussieck, Drud (2003) (B&B)

Bonmin (COIN-OR) - Bonami et al (2006) (B&B, OA, Hybrid)

DICOPT (GAMS) - Viswanathan and Grossman (1990) (OA)

α-ECP - Westerlund and Peterssson (1996) (ECP)

MINOPT - Schweiger and Floudas (1998) (GBD, OA)

BARON - Sahinidis et al. (1998) (Deterministic Global Optimization)


In GAMS, the GDP problems can be formulated and solved directly too by using the following solver:

LOGMIP - Vecchietti and Grossmann (1996)


3. Example

Ex1.png

Here is an illustration of the formulation of the GDP problems. As shown in the process system diagram above, there are two paths to produce product B from raw material A. One is through using a reactor R1 followed by a distillation column DC1, another is through a heat exchanger HX1 followed by a reactor R2. The plant purchases A and sells B both at a fixed unit cost. The adoption of each unit process bears a fixed cost and is decided by the optimization outcome. Notice that in the logic propositions \Omega here are replaced by (7) and (8) indicating that the operation units in the same path of production are tied together in the decision on process adoption.F denotes the flow rate of each stream and \beta denotes the fraction of inlet stream that goes to an outlet stream.

Ex2.png


4. Conclusion

The GDP is a nonlinear mixed-integer and disjunctive programming method. It accommodates the use of logic expressions and nonlinear inequalities in the constraints. A convex GDP problem can be solved directly by LOGMIP in GAMS or solved by a selected number of MINLP solvers after reformulating the problem into a convex MINLP problem using the Big-M or the Convex Hull reformulation.


5. Reference

1. Balas, Egon. "Disjunctive programming and a hierarchy of relaxations for discrete optimization problems." SIAM Journal on Algebraic Discrete Methods6.3 (1985): 466-486.

2. Raman, Ramesh, and Ignacio E. Grossmann. "Modelling and computational techniques for logic based integer programming." Computers & Chemical Engineering 18.7 (1994): 563-578.

3. Grossmann, Ignacio E., and E. W. O. Seminar. "Overview of Generalized Disjunctive Programming." (2009).

4. Grossmann, Ignacio E., and Sangbum Lee. "Generalized convex disjunctive programming: Nonlinear convex hull relaxation." Computational Optimization and Applications 26.1 (2003): 83-100.

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

6. Ruiz, Juan P., and Ignacio E. Grossmann. "A hierarchy of relaxations for nonlinear convex generalized disjunctive programming." European Journal of Operational Research 218.1 (2012): 38-47.

7. You, Fengqi. Mixed-Integer Nonlinear Programming. (2015)