Outer-approximation (OA)

Author: Yousef Aloufi (CHEME 6800 Fall 2021)

Introduction

Mixed-integer nonlinear programming (MINLP) deals with optimization problems by combining the modeling capabilities of mixed-integer linear programming (MILP) and nonlinear programming (NLP) into a powerful modeling framework. The integer variables make it possible to incorporate discrete decisions and logical relations in the optimization problems, and the combination of linear and nonlinear functions make it possible to accurately describe a variety of different phenomena. The ability to accurately model real-world problems has made MINLP an active research area and there exists a vast number of applications in fields such as engineering, computational chemistry, and finance. Although MINLPs are non-convex optimization problems because of some variables’ discreteness, the term convex MINLP is used to denote problems where the continuously relaxed feasible region described by the constraints and the objective function are convex. Convex MINLP problems are an important class of problems, as the convex properties can be exploited to derive efficient decomposition algorithms. These decomposition algorithms rely on the solution of different subproblems derived from the original MINLP. Among these decomposition algorithms for MINLP, are Branch & Bound, Generalized Benders Decomposition, Outer Approximation, Partial Surrogate Cuts, Extended Cutting Plane , Feasibility Pump, and the center-cut method. MINLP problems are usually the hardest to solve unless a special structure can be exploited. Consider the following MINLP formulation :
Minimize

$$Z=c^{T}y+f(x)$$

Subject to

$$h(x)=0$$

$$g(x)\leq 0$$

$$Ax=a$$

$$By+Cx\leq d$$

$$Ey\leq e$$

$$x\in X={\big \{}x\mid x\in R^{n},x^{L}\leq x\leq x^{U}{\big \}}$$

$$y_{1},y_{2}\in {\big \{}0,1{\big \}}^{t}$$

This mixed-integer nonlinear problem can be solved with the branch and bound method. However, an important drawback of the branch and bound method for MINLP is that the solution of the NLP subproblems can be expensive since they cannot be readily updated as in the case of the MILP. Therefore, in order to reduce the computational expense involve in solving many NLP subproblems, we can resort to another method: Outer-Approximation.

Theory

The Outer-Approximation (OA) algorithm was first proposed by Duran and and Grossmann in 1986 to solve MINLP problems. The basic idea of the OA method is to solve a sequence of nonlinear programming sub-problems and relaxed mixed-integer linear master problem successfully. In a minimization problem, for example, the NLP subproblems appear for a fixed number of binary variables, and involve the optimization of continuous variables with an upper bound to the original MINLP is obtained. The MILP master problem provides a global linear approximation to the MINLP in which the objective function is underestimated and the nonlinear feasible region is overestimated. In addition, the linear approximations to the nonlinear equations are relaxed as inequalities. This MILP master problem accumulates the different linear approximations of previous iterations so as to produce an increasingly better approximation of the original MINLP problem. At each iteration the master problem predicts new values of the binary variables and a lower bound to the objective function. Finally, the search is terminated when no lower bound can be found below the current best upper bound which then leads to an infeasible MILP.

Algorithm

Refer to the MINLP problem in the introduction section. The specific steps of OA algorithm, assuming feasible solutions for the NLP subproblems, are as follows:
Step 1: Select an initial value of the binary variables ${\textstyle y^{1}}$. Set the iteration counter ${\textstyle K=1}$. Initialize the lower bound ${\textstyle Z_{L}=-\infty }$, and the upper bound ${\textstyle Z_{U}=+\infty }$.
Step 2: Solve the NLP subproblem for the fixed value ${\textstyle y^{k}}$, to obtain the solution ${\textstyle x^{k}}$ and the multipliers ${\textstyle \lambda ^{k}}$ for the equations ${\textstyle h(x)=0.}$

$$Z(y^{k})=min~~c^{T}y^{k}+f(x)$$

$$s.t.~~~~~~~h(x)=0$$

$$~~~~~~~g(x)\leq 0$$

$$~~~~~~~h(x)\leq 0$$

$$~~~~~~~Ax=a$$

$$~~~~~~~Cx\leq d-B~~y^{k}$$

$$~~~~~~~x\in X$$

Step 3: Update the bounds and prepare the information for the master problem:
a. Update the current upper bound; if ${\textstyle Z(y^{k})<Z_{U}}$, set ${\textstyle Z_{U}=Z(y^{k}),~~y^{*}=y^{k},~~x^{*}=x^{k}.}$
b. Derive the integer cut, ${\textstyle IC^{k}}$, to make infeasible the choice of the binary ${\textstyle y^{k}}$ from the subsequent iterations:

$$IC^{K}={\big \{}\sum _{ieB^{K}}y_{i}-\sum _{ieN^{K}}y\leq \mid B^{K}\mid -1{\big \}}$$

$$where~~B^{k}={\big \{}i\mid y_{i}^{K}=1{\big \}},~~N^{k}={\big \{}i\mid y_{i}^{K}=0{\big \}}$$

c. Define the diagonal direction matrix ${\textstyle T^{K}}$ for relaxing the equations into inequalities based on the sign of the multipliers ${\textstyle \lambda ^{k}}$. The diagonal elements are given by:

$$t_{jj}^{K}={\begin{cases}-1&if~~\lambda _{j}^{K}<0\\+1&if~~\lambda _{j}^{K}>0\\0&if~~\lambda _{j}^{K}=0\end{cases}}$$

$$where~~j=1,2...m$$

d. Obtain the following linear outer-approximations for the nonlinear terms ${\textstyle f(x),~~h(x),~~g(x)}$ by performing first order linearizations at the point ${\textstyle x^{K}}$ :

$$(w^{K})^{T}x-w_{c}^{K}=f(x^{K})+\bigtriangledown f(x^{K})^{T}(x-x^{T})$$

$$R^{K}x-r^{K}=h(x^{K})+\bigtriangledown h(x^{K})^{T}(x-x^{T})$$

$$S^{K}x-s^{K}=g(x^{K})+\bigtriangledown g(x^{K})^{T}(x-x^{T})$$

Step 4: a. Solve the following MILP master problem:

$$Z_{L}^{K}=min~~c^{T}y+\mu$$

$$s.t.~~~~~~~(w^{k})x-\mu \leq w_{c}^{k}$$

$$~~~~~~~T^{k}R^{k}x\leq T^{k}r^{k}~~~~~~~~~~~~k=1,2...K$$

$$~~~~~~~S^{k}x\leq s^{k}$$

$$~~~~~~~y\in IC^{k}$$

$$~~~~~~~By+Cx\leq d$$

$$~~~~~~~Ax=a$$

$$~~~~~~~Ey\leq e$$

$$~~~~~~~Z_{L}^{K-1}\leq c^{T}y+\mu \leq Z_{U}$$

$$~~~~~~~y\in {\big \{}0,1{\big \}}^{t}~~~~x\in X~~~~\mu \in R^{1}$$

b. If the MILP master problem has no feasible solution, stop. The optimal solution is ${\textstyle x^{*},~~y^{*},~~Z_{U},}$.
c. If the MILP master problem has a feasible solution, the new binary value ${\textstyle y^{K+1}}$ is obtained. Set ${\textstyle K=K+1}$, return to step 2.

Example

Numerical Example

The following is a step-by-step solution for an MINLP optimization problem using Outer-Approximation method:
Minimize

$$f(x)=y_{1}+y_{2}+{\big (}x_{1}{\big )}^{2}+{\big (}x_{2}{\big )}^{2}$$

Subject to

$${\big (}x_{1}-2{\big )}^{2}-x_{2}\leq 0$$

$$x_{1}-2y_{1}\geq 0$$

$$x_{1}-x_{2}-3{\big (}1-y_{1}{\big )}\geq 0$$

$$x_{1}+y_{1}-1\geq 0$$

$$x_{2}-y_{2}\geq 0$$

$$x_{1}+x_{2}\geq 3y_{1}$$

$$y_{1}+y_{2}\geq 1$$

$$0\leq x_{1}\leq 4$$

$$0\leq x_{2}\leq 4$$

$$y_{1},y_{2}\in {\big \{}0,1{\big \}}$$

Solution
Step 1a: Start from ${\textstyle y_{1}=y_{2}=1}$ and solve the NLP below:
Minimize

$$f=2+{\big (}x_{1}{\big )}^{2}+{\big (}x_{2}{\big )}^{2}$$

Subject to

$${\big (}x_{1}-2{\big )}^{2}-x_{2}\leq 0$$

$$x_{1}-2\geq 0$$

$$x_{1}-x_{2}\geq 0$$

$$x_{1}\geq 0$$

$$x_{2}-1\geq 0$$

$$x_{1}+x_{2}\geq 3$$

$$0\leq x_{1}\leq 4$$

$$0\leq x_{2}\leq 4$$

Solution: ${\textstyle x_{1}=2,x_{2}=1}$, Upper Bound = 7

Step 1b: Solve the MILP master problem with OA for ${\textstyle x^{*}=[2,1]}$ :

$$f{\big (}x{\big )}={\big (}x_{1}{\big )}^{2}+{\big (}x_{2}{\big )}^{2},~~\bigtriangledown f{\big (}x{\big )}=[2x_{1}~~~~2x_{1}]^{T}~~for~~x^{*}=[2~~~~1]^{T}$$

$$f{\big (}x^{*}{\big )}+\bigtriangledown f{\big (}x^{*}{\big )}^{T}{\big (}x-x^{*}{\big )}=5+[4~~~~2]{\begin{bmatrix}x_{1}-2\\x_{2}-1\end{bmatrix}}=5+4{\big (}x_{1}-2{\big )}+2{\big (}x_{2}-1{\big )}$$

$$g{\big (}x{\big )}={\big (}x_{1}-2{\big )}^{2}-x_{2},~~\bigtriangledown g{\big (}x{\big )}=[2x_{1}-4~~~~-1]^{T}~~for~~x^{*}=[2~~~~1]^{T}$$

$$g{\big (}x^{*}{\big )}+\bigtriangledown g{\big (}x^{*}{\big )}^{T}{\big (}x-x^{*}{\big )}=-1+[0~~~~-1]{\begin{bmatrix}x_{1}-2\\x_{2}-1\end{bmatrix}}=-x_{2}$$

Minimize

$$\alpha$$

Subject to

$$\alpha \geq y_{1}+y_{2}+5+4{\big (}x_{1}-2{\big )}+2{\big (}x_{2}-1{\big )}$$

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

$$x_{1}-2y_{1}\geq 0$$

$$x_{1}-x_{2}-3{\big (}1-y_{1}{\big )}\geq 0$$

$$x_{1}+y_{1}-1\geq 0$$

$$x_{2}-y_{2}\geq 0$$

$$x_{1}+x_{2}\geq 3y_{1}$$

$$y_{1}+y_{2}\geq 1$$

$$0\leq x_{1}\leq 4$$

$$0\leq x_{2}\leq 4$$

$$y_{1},y_{2}\in {\big \{}0,1{\big \}}$$

MILP Solution: ${\textstyle x_{1}=2,x_{2}=1,y_{1}=1,y_{2}=0}$, Lower Bound = 6
Lower Bound < Upper Bound, Integer cut: ${\textstyle y_{1}-y_{2}\leq 0}$

Step 2a: Start from ${\textstyle y=[1,0]}$ and solve the NLP below:
Minimize

$$f=1+{\big (}x_{1}{\big )}^{2}+{\big (}x_{2}{\big )}^{2}$$

Subject to

$${\big (}x_{1}-2{\big )}^{2}-x_{2}\leq 0$$

$$x_{1}-2\geq 0$$

$$x_{1}-x_{2}\geq 0$$

$$x_{1}\geq 0$$

$$x_{2}\geq 0$$

$$x_{1}+x_{2}\geq 3$$

$$0\leq x_{1}\leq 4$$

$$0\leq x_{2}\leq 4$$

Solution: ${\textstyle x_{1}=2,x_{2}=1}$, Upper Bound = 6
Upper Bound = 6 = Lower Bound, Optimum!
Optimal Solution for the MINLP: ${\textstyle x_{1}=2,x_{2}=1,y_{1}=1,y_{2}=0}$

GAMS Model

The above MINLP example can be expressed in the General Algebraic Modeling System (GAMS) as follows:

Variable z;
Positive Variables x1, x2;
Binary Variables y1, y2;
Equations obj, c1, c2, c3, c4, c5, c6, c7;
obj.. z =e= y1 + y2 + sqr(x1) + sqr(x2);
c1.. sqr(x1 - 2) - x2 =l= 0;
c2.. x1 - 2*y1 =g= 0;
c3.. x1 - x2 - 3*sqr(1 - y1) =g= 0;
c4.. x1 + y1 - 1 =g= 0;
c5.. x2 - y2 =g= 0;
c6.. x1 + x2 =g= 3*y1;
c7.. y1 + y2 =g= 1;
x1.lo = 0; x1.up = 4;
x2.lo = 0; x2.up = 4;
model Example /all/;
option minlp = bonmin;
option optcr = 0;
solve Example minimizing z using minlp;
display z.l, x1.l, x2.l, y1.l, y2.l;