Extended cutting plane (ECP)
Authors: Kyung Je Lee (ChE 345 Spring 2015) Stewards: Dajun Yue, Fengqi You
Extended Cutting Plane is an optimization method suggested by Westerlund and Petersson in 1996 to solve Mixed-Integer NonLinear Programming (MINLP) problems. ECP can be thought as an extension of Kelley's cutting plane method, which uses iterative Newton's method to refine feasible area and ultimately solve a problem within tolerable error. Therefore, ECP method does not require solving Non-Linear Programming(NLP) while Branch and Bound(BB) and Outer Approximation(OA) do require NLP solution for an upper bound. However, ECP generally requires more iterations. Although cutting plane method is criticized for its slow convergence, ECP is more efficient in cases where evaluation of non linear functions are time costly. For example, in optimization of a dynamic separation process done by Stefan Emet and Tapio Westerlund, ECP was 100 times faster than BB and 10 times faster than OA in solving the MINLP.
Comparison with outer approximation
ECP is closely related to OA in that it uses first differential approximation to cut the plane. The difference is that OA solves a NLP problem for its upper bound while ECP only uses solution of MILP in each iteration. This means that OA is more efficient in main iteration loops. This advantage of OA is more prominent in strongly non-linear MINLP problems that are mainly consisted of continuous variables. However, in pure integer non-linear programming problems, OA method does not have any advantage over ECP. Although it takes less iterations for OA to converge, solving NLP problem in each iteration incur more computation work than solving MILP because MILP has only one additional linear constraints in each iteration.
Formulation of MINLP problem
A general MINLP can be formulated as the following:
where, cx and cy are vectors with constants, x is a vector of continuous variables, y is a vector with discrete variables and g(x, y) is a vector with continuous convex functions, all defined on a set.
Since g(x,y) is a convex function set and continuously differentiable it follows that
then for all i
Using these properties, ECP algorithm is as follows:
Step 0. Set k=1. Leave out all nonlinear constraints and set up an MILP problem.
Step 1. Solve the MILP problem.
Step 2. Check if the solution satisfies nonlinear constraints. If all constraints are satisfied, in other words, if is true for all i, is a global optimum.
Step 3 If any of the constraints are not satisfied, add a constraint for most violated constraint, g
- set k= k+1 and go to Step 1.
First MILP can be set-up by leaving out non-linear constraint and
The first iteration gives . This leads to A new constraint is introduced for the second iteration with the most violated nonlinear constraint
Same procedure can be taken for consequent iterations, and with 17 iterations, ECP gives answer of .
In non-smooth functions, ECP algorithm can be generalized by relaxing continuous differentiability. Therefore, the only change in the algorithm is that subgradients are used instead of gradients. Subgradient of convex function at point is any vector that satifies
1. Tapio Westerlund, Frank Pettersson, An extended cutting plane method for solving convex MINLP problems, Computers & Chemical Engineering, Volume 19, Supplement 1, 11–14 June 1995, Pages 131-136, ISSN 0098-1354, http://dx.doi.org/10.1016/0098-1354(95)87027-X.
2. Stefan Emet and Tapio Westerlund. 2008. Solving a dynamic separation problem using MINLP techniques. Appl. Numer. Math. 58, 4 (April 2008), 395-406. DOI=10.1016/j.apnum.2007.01.023 http://dx.doi.org/10.1016/j.apnum.2007.01.023
3. An extended supporting hyperplane algorithm for convex MINLP problems http://blogs.abo.fi/ose/files/2014/10/ose2014_kronqvist.pdf