View source for Extended cutting plane (ECP)

Authors: Kyung Je Lee (ChE 345 Spring 2015)
Stewards: Dajun Yue, Fengqi You

==Introduction==
===Background===
'''Extended Cutting Plane''' is an optimization method suggested by Westerlund and Petersson in 1996 to solve Mixed-Integer NonLinear Programming (MINLP) problems<span style="font-size: 8pt; position:relative; bottom: 0.3em;">[1]</span>. 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<span style="font-size: 8pt; position:relative; bottom: 0.3em;">[2]</span>. 

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

<math> \min_{x,y}  Z=C_x^T x + C_y^T y </math>

<math>s.t. \quad g(x,y) \leq 0</math>

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.

==ECP algorithm==
Since g(x,y) is a convex function set and continuously differentiable it follows that

<math> g_i(x^k,y^k) + \left( \frac{\partial g_i}{\partial x}\right)_{x^k,y^k} (x-x^k) + \left( \frac{\partial g_i}{\partial y}\right)_{x^k,y^k} (y-y^k) \leq g_i(x,y)</math>

Also, if,

<math> max(g_i(x^k,y^k)) \leq 0 </math>

then for all i

<math> g_i(x^k,y^k) \leq 0</math>


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 <math> g_i(x^k,y^k) \leq 0</math> is true for all i, <math>(x^k, y^k)</math> is a global optimum.

'''Step 3''' If any of the constraints are not satisfied, add a constraint for most violated constraint, g
::<math> g_i(x^k,y^k) + \left( \frac{\partial g_i}{\partial x}\right)_{x^k,y^k} (x-x^k) + \left( \frac{\partial g_i}{\partial y}\right)_{x^k,y^k} (y-y^k)\leq 0 </math> 
::set k= k+1 and go to Step 1.

== Example == 
<math> \min z = -x_1-x_2 </math>

<math> s.t. \quad g1(x_1,x_2) = 0.15(x_1-8)^2 + 0.1 (x_2-6)^2+0.025e^{x_1}x_2^{-2}-5 \leq 0 </math>
::<math> g2(x_1,x_2) = 1/x_1 + 1/x_2- x_1^{0.5}x_2^{0.5}+4 \leq 0 </math>
::<math> 2x_1-3x_2-2 \leq 0 </math>
::<math> 1\leq x_1 \leq 20,\quad 1\leq x_2\leq 20, \quad x_1\in \R \quad x_2 \in \N</math>


First MILP can be set-up by leaving out non-linear constraint <math> g_1</math> and <math> g_2</math>
[[File:ECP.PNG|350px|thumb|right|Visualization of how ECP is used to solve MINLP<sup>4</sup>]]
<math> \min z = -x_1-x_2 </math>

<math> s.t. \quad2x_1-3x_2-2 \leq 0 </math>
::<math> 1\leq x_1 \leq 20,\quad 1\leq x_2\leq 20 </math>
::<math> x_1\in \R \quad x_2 \in \N </math>


The first iteration gives <math>x_1^1 = 20, x_2^1=20 </math>.
This leads to <math>g_1(x_1^1,x_2^1)=30359, \quad g_2(x_1^1,x_2^1)= -15.9 </math>

A new constraint is introduced for the second iteration with the most violated nonlinear constraint <math>g_1</math>

<math> \min z = -x_1-x_2 </math>

<math> s.t. \quad g_1(x_1^1,x_2^1)+\triangledown g_1(x_1^1,x_2^1)^T(x-x_1^1,x-x_2^1) \leq 0 </math>
::<math> 2x_1-3x_2-2 \leq 0 </math>
::<math> 1\leq x_1 \leq 20,\quad 1\leq x_2\leq 20 </math>
::<math> x_1\in \R \quad x_2 \in \N </math>

Same procedure can be taken for consequent iterations, and with 17 iterations, ECP gives answer of <math>x_1^1 = 8.9, x_2^1=12 </math>.


==Non-smooth Functions==
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 <math>h</math> at point<math>z_0</math> is any vector <math>\xi</math> that satifies
<math>h(z_0) + \xi(z-z_0) \leq h(z)</math> <sup> 3 </sup>


==Conclusion==
ECP is an extension of cutting plane(CP) method that is used to solve NLP problems. The application of cutting plane to MINLP is rather straight forward and the strength of ECP lies in that it is simple and robust. Therefore, it is suitable for solving large MINLP problems with moderate degree of non-linearity and complex system that require extensive computational work. ECP only requires one additional constraint to improve one solution for MILP problem at each iteration whereas both NLP and MILP problems are solved in other MINLP methods. However, since there is only one adjustment made at a time, it has slow convergence to solution.


==Reference==
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.Tapio Westerlund, Hans Skrifvars, Iiro Harjunkoski, Ray Pörn, An extended cutting plane method for a class of non-convex MINLP problems, Computers & Chemical Engineering, Volume 22, Issue 3, 28 February 1998, Pages 357-365, ISSN 0098-1354, http://dx.doi.org/10.1016/S0098-1354(97)00000-8.
(http://www.sciencedirect.com/science/article/pii/S0098135497000008)

4. An extended supporting hyperplane algorithm for convex  MINLP problems http://blogs.abo.fi/ose/files/2014/10/ose2014_kronqvist.pdf