Extended cutting plane (ECP)

This web page is a duplicate of https://optimization.mccormick.northwestern.edu/index.php/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[1]. 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[2].

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:

$\min _{x,y}Z=C_{x}^{T}x+C_{y}^{T}y$

$s.t.\quad g(x,y)\leq 0$

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

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

Also, if,

$max(g_{i}(x^{k},y^{k}))\leq 0$

then for all i

$g_{i}(x^{k},y^{k})\leq 0$

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 $g_{i}(x^{k},y^{k})\leq 0$ is true for all i, $(x^{k},y^{k})$ is a global optimum.

Step 3 If any of the constraints are not satisfied, add a constraint for most violated constraint, g

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

set k= k+1 and go to Step 1.

Example

$\min z=-x_{1}-x_{2}$

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

$g2(x_{1},x_{2})=1/x_{1}+1/x_{2}-x_{1}^{0.5}x_{2}^{0.5}+4\leq 0$

$2x_{1}-3x_{2}-2\leq 0$

$1\leq x_{1}\leq 20,\quad 1\leq x_{2}\leq 20,\quad x_{1}\in \mathbb {R} \quad x_{2}\in \mathbb {N}$

First MILP can be set-up by leaving out non-linear constraint $g_{1}$ and $g_{2}$

Visualization of how ECP is used to solve MINLP⁴

$\min z=-x_{1}-x_{2}$

$s.t.\quad 2x_{1}-3x_{2}-2\leq 0$

$1\leq x_{1}\leq 20,\quad 1\leq x_{2}\leq 20$

$x_{1}\in \mathbb {R} \quad x_{2}\in \mathbb {N}$

The first iteration gives $x_{1}^{1}=20,x_{2}^{1}=20$. This leads to $g_{1}(x_{1}^{1},x_{2}^{1})=30359,\quad g_{2}(x_{1}^{1},x_{2}^{1})=-15.9$

A new constraint is introduced for the second iteration with the most violated nonlinear constraint $g_{1}$

$\min z=-x_{1}-x_{2}$

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

$2x_{1}-3x_{2}-2\leq 0$

$1\leq x_{1}\leq 20,\quad 1\leq x_{2}\leq 20$

$x_{1}\in \mathbb {R} \quad x_{2}\in \mathbb {N}$

Same procedure can be taken for consequent iterations, and with 17 iterations, ECP gives answer of $x_{1}^{1}=8.9,x_{2}^{1}=12$.

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 $h$ at point$z_{0}$ is any vector $\xi$ that satifies $h(z_{0})+\xi (z-z_{0})\leq h(z)$ ³

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