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.
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 $ {\displaystyle Z= c^{T}y+f(x) } $ Subject to $ {\displaystyle h(x)=0} $ $ {\displaystyle g(x) \leq 0} $ $ {\displaystyle Ax=a} $ $ {\displaystyle By+Cx\leq d} $ $ {\displaystyle Ey\leq e} $ $ {\displaystyle x \in X=\big\{x \mid x \in R^{n}, x^{L} \leq x \leq x^{U}\big\}} $ $ {\displaystyle 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.} $
$ {\displaystyle Z(y^{k})=min~~ c^{T}y^{k}+f(x)} $ $ {\displaystyle s.t.~~~~~~~ h(x)=0} $ $ {\displaystyle ~~~~~~~g(x)\leq0} $ $ {\displaystyle ~~~~~~~h(x)\leq0} $ $ {\displaystyle ~~~~~~~Ax=a} $ $ {\displaystyle ~~~~~~~Cx\leq d-B~~y^{k}} $ $ {\displaystyle ~~~~~~~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: $ {\displaystyle IC^{K}= \big\{ \sum_{ieB^{K}} y_{i}-\sum_{ieN^{K}} y \leq \mid B^{K}\mid-1 \big\} } $ $ {\displaystyle 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: $ {\displaystyle 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} } $ $ {\displaystyle 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}} $ : $ {\displaystyle (w^{K})^{T}x-w_{c}^{K}=f(x^{K})+ \bigtriangledown f(x^{K})^{T}(x-x^{T}) } $ $ {\displaystyle R^{K}x-r^{K}=h(x^{K})+ \bigtriangledown h(x^{K})^{T}(x-x^{T}) } $ $ {\displaystyle 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:

$ {\displaystyle Z_{L}^{K}=min~~ c^{T}y+ \mu } $ $ {\displaystyle s.t.~~~~~~~(w^{k})x-\mu \leq w_{c}^{k} } $ $ {\displaystyle ~~~~~~~T^{k}R^{k}x\leq T^{k}r^{k}~~~~~~~~~~~~k=1,2...K } $ $ {\displaystyle ~~~~~~~ S^{k}x\leq s^{k}} $ $ {\displaystyle ~~~~~~~y \in IC^{k}} $ $ {\displaystyle ~~~~~~~ By+Cx \leq d} $ $ {\displaystyle ~~~~~~~ Ax=a} $ $ {\displaystyle ~~~~~~~ Ey \leq e} $ $ {\displaystyle ~~~~~~~ Z_{L}^{K-1} \leq c^{T}y+ \mu \leq Z_{U}} $ $ {\displaystyle ~~~~~~~ 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 $ {\displaystyle f(x)= y_{1} +y_{2} + \big(x_{1}\big)^{2} +\big(x_{2}\big)^{2} } $ Subject to $ {\displaystyle \big(x_{1}-2\big)^{2}-x_{2} \leq 0} $ $ {\displaystyle x_{1}-2y_{1} \geq 0} $ $ {\displaystyle x_{1}-x_{2}-3 \big(1-y_{1}\big) \geq 0} $ $ {\displaystyle x_{1}+y_{1}-1\geq 0} $ $ {\displaystyle x_{2}-y_{2}\geq 0} $ $ {\displaystyle x_{1}+x_{2}\geq 3y_{1}} $ $ {\displaystyle y_{1}+y_{2}\geq 1} $ $ {\displaystyle 0 \leq x_{1}\leq 4} $ $ {\displaystyle 0 \leq x_{2}\leq 4} $ $ {\displaystyle 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 $ {\displaystyle f= 2+ \big(x_{1}\big)^{2} +\big(x_{2}\big)^{2} } $ Subject to $ {\displaystyle \big(x_{1}-2\big)^{2}-x_{2} \leq 0} $ $ {\displaystyle x_{1}-2 \geq 0} $ $ {\displaystyle x_{1}-x_{2} \geq 0} $ $ {\displaystyle x_{1} \geq 0} $ $ {\displaystyle x_{2}-1 \geq 0} $ $ {\displaystyle x_{1}+x_{2} \geq 3} $ $ {\displaystyle 0 \leq x_{1}\leq 4} $ $ {\displaystyle 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] } $ :
$ {\displaystyle 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} } $ $ {\displaystyle 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)} $
$ {\displaystyle 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} } $

$ {\displaystyle 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 $ {\displaystyle \alpha } $ Subject to $ {\displaystyle \alpha\geq y_{1}+y_{2}+5+4\big(x_{1}-2\big)+2\big(x_{2}-1\big) } $ $ {\displaystyle -x_{2}\leq0} $ $ {\displaystyle x_{1}-2y_{1} \geq 0} $ $ {\displaystyle x_{1}-x_{2}-3 \big(1-y_{1}\big) \geq 0} $ $ {\displaystyle x_{1}+y_{1}-1\geq 0} $ $ {\displaystyle x_{2}-y_{2}\geq 0} $ $ {\displaystyle x_{1}+x_{2}\geq 3y_{1}} $ $ {\displaystyle y_{1}+y_{2}\geq 1} $ $ {\displaystyle 0 \leq x_{1}\leq 4} $ $ {\displaystyle 0 \leq x_{2}\leq 4} $ $ {\displaystyle 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 $ {\displaystyle f= 1+ \big(x_{1}\big)^{2} +\big(x_{2}\big)^{2} } $ Subject to $ {\displaystyle \big(x_{1}-2\big)^{2}-x_{2} \leq 0} $ $ {\displaystyle x_{1}-2 \geq 0} $ $ {\displaystyle x_{1}-x_{2} \geq 0} $ $ {\displaystyle x_{1} \geq 0} $ $ {\displaystyle x_{2} \geq 0} $ $ {\displaystyle x_{1}+x_{2} \geq 3} $ $ {\displaystyle 0 \leq x_{1}\leq 4} $ $ {\displaystyle 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;

Applications

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. The followings are some MINLP applications that can be solved by the OA method:

Uncapacitated Facility Location

Given a set of "customers" $ {\textstyle N= \big\{1,2,...n\big\} } $ with demand for a single commodity and a set of potential "facilities" $ {\textstyle M= \big\{1,2,...m\big\} } $ with unlimited capacity, the Uncapacitated Facility Location (UFL) problem involves $ {\textstyle (i)} $ choosing a subset of the facilities to open and $ {\textstyle (ii)} $ determining how much of each customer's demand is satisfied by each open facility. The objective function consists of transportations costs as well as fixed costs associated with opening facilities.

Delay constrained routing problem

The delay constrained routing problem consists in finding an optimal routing in a telecommunication network that satisfies both a given demand and constraints on the delay of communications. We are given a graph $ {\textstyle G=(V,E) } $ with arc costs $ {\textstyle w_e } $ and capacities $ {\textstyle c_e } $ and a set of $ {\textstyle K} $ demands which are described by the set of paths they can use $ {\textstyle P(k)} $, the quantity of flow $ {\textstyle v_k } $ that need to be routed and the maximum delay for this demand $ {\textstyle \alpha_k } $. A feasible routing is an assignment of a sufficient flow to candidate paths to satisfy demand and such that the total delay on each active path $ {\textstyle P_k^i } $ is smaller than $ {\textstyle \alpha_k } $.

Stochastic Service Systems Design Problems (SSSD)

SSSD consists in configuring optimally the service levels of a network of $ {\textstyle M/M/1} $ queues. We are given a set of customers $ {\textstyle J} $, a set of facilities $ {\textstyle I} $ and a set of service levels $ {\textstyle K} $. Each customer has a mean demand rate $ {\textstyle \lambda_j} $. The goal is to determine service rates for the facilities so that the customer demand is met. There is a fixed cost for operating facility $ {\textstyle j} $ at rate $ {\textstyle k} $, a fixed cost for assigning customer $ {\textstyle i} $ to facility $ {\textstyle j} $. A binary variable $ {\textstyle x_ij} $ indicates if customer $ {\textstyle i} $ is served by facility $ {\textstyle j} $, and a binary variable $ {\textstyle y_jk} $ indicates if facility $ {\textstyle j} $ is operated at service level $ {\textstyle k} $.

Conclusion

Outer-Approximation is a well known efficient approach for solving convex mixed-integer nonlinear programs (MINLP). It consists in building a mixed-integer linear equivalent to the feasible region of the problem by taking tangents at well specified points. Different algorithms have been devised to build the mixed-integer linear equivalent including an algorithm proposed by by Duran and and Grossmann in 1986. A step-by-step numerical example was presented to illustrate the OA algorithm. Finally, three MINLP applications that can be solved by the OA method were discussed.