Nonconvex Generalized disjunctive programming (GDP)
Author: Kaiwen Li (ChE345 Spring 2015)
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.
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.
Increased attention has been received to solution of Mixed-Integer Nonlinear Programming (MINLP) models because its practical importance in engineering and many other areas.
General Formulation for GDP
Consider the following Generalized Disjunctive Programming problem, which includes Boolean variables, disjunctions and logic propositions:
where, is a function of the continuous variables x in the objective function, bolongs to the set of global constraints, the disjuctions are composed of a number of terms , which is connected by the OR operator. is a Boolean varibale, is a set of inequalities, and is a cost variable. When is true, and are enforced.Also, 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,
are logic propositions for the Boolean variables.
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.
Detailed Formulation and Models
Convex Relaxation of GDP
The following reformulation shows the introduction of valid convex underestimating functions to change Problem (P) into a convex GDP problem.
where ,, are valid convex underestimators so that , , are satisfied if , (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:
where is the disaggregated continuous variable for the th term in the th disjunction and is the corresponding multiplier for each term in a given disjunction
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.
where is the big-M parameter, which provides a valid upper bound to the violation of and is an upper bound to .
Bound Contraction Procedure
The bound contraction scheme is designed to tighten the lower and upper bound of a given continuous variable , which will eliminate the nonoptimal subregions and accelerate the search. This will greatly reduce the difference between lower and upper bounds of the objective function and save computational work.
The contraction scheme is shown by the following NLP problem:
As is shown in the following Fig.3, if the solution point of problem (CRP) does not lie at its bound, then we solve the NLP problem (CRP) and update the upper and lower bounds based on the relative distance from the solution to each bound of to decide the direction of bound contraction. Bound contraction is applied to only the continuous variables. Not much reduction will be made if the contraction is not successful, and then move to next variable.
Branch and Bound on Boolean Variables
This step is where branch and bound method is applied in the space of the terms of the disjunctions by solving the relaxed convex NLP problem (CRP) at each node. The rule is to select the variable with the largest fractional value in the solution. By creating two child nodes with and , is fixed in problem (R) respectively. The nodes number should be finite due to finite Boolean variables and the global lower bound increases monotonically.
Upper bound needs to be updated when there is a gap between the solution of this problem and the original nonconvex GDP problem (P). When the feasible solution to problem (R) is obtained and the gap between nonconvex term and convex underestimator in problem (P) and problem (R) is nonzero, all Boolean variables should be fixed and Spatial Branch and Bound Method should be introduced.
Spatial Branch and Bound Method
Since there is a specific wiki page introducing this method, there is no need to discuss the detailed algorithm here. In this case, by solving problem (CRP), the nonconvex term with the max gap is chosen. Then, choose the middle point of the variable bound as the branching point. Lastly, select the node with lowest objective value. The current node will be fathomed if the lowest objective value of the node is greater than GUB.
Advantages and Disadvantages
Applications and Examples
Application in Solution Algorithm for nonconvex GDP problems
Step 0 Heuristic Search (Nonconvex MINLP)
Use MINLP solvers (such as DICOPT++) to solve the nonconvex problem (P-MIP), and set GUB as the best upper bound and let be the solution.
Step 1 Bound Contraction (Convex NLP)
- Initialize the Relative Distance from to each bound
- Increase iteration, solve problem (BCP)
Update bound and continue with when contraction is greater than . Otherwise select next x.
- Return to 2 and repeat until max iteration.
Step 2 Branch and Bound on Discrete Variables (Convex NLP)
- set tolerance for difference in and GUB. Set for max gap.
- Solve problem (CRP) to obtain lower bound . Update lowest lower bound as GLB.
- Fathom, go to step 3 or Branch on the node.
Spatial Branch and Bound (Convex NLP)
- Fix all according to solution from step 2
- Solve problem (CRP) until no open node with Failed to parse(unknown function '\l'): Z^L \l GUB - \alpha
- Go to step 2
- 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.
For nonconvex generalized disjunctive programming, specified algorithm can provide a global optimum more efficiently, compared with conventional MINLP and GBD algorithms.
- Lee, Sangbum, and Ignacio E. Grossmann. "New algorithms for nonlinear generalized disjunctive programming." Computers & Chemical Engineering 24.9 (2000): 2125-2141.
- 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.
- 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.
- 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.