Outer-approximation (OA): Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
Line 17: Line 17:


== Theory ==
== 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. <ref>Duran MA, Grossmann I (1986) An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Programming 36(3):307–339.</ref> 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.  <ref name=" Book" />
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. <ref>Duran, M. A., & Grossmann, I. E. (1986). [https://link.springer.com/article/10.1007/BF02592064 “An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Mathematical programming”], 36(3), 307-339.</ref> 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.  <ref name=" Book" />


== Algorithm==
== Algorithm==

Revision as of 03:55, 14 December 2021

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. [1]
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. [2] 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. [3]
MINLP problems are usually the hardest to solve unless a special structure can be exploited. Consider the following MINLP formulation : [4]
Minimize

Subject to
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.[5]

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. [6] 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. [4]

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:[4]
Step 1: Select an initial value of the binary variables . Set the iteration counter . Initialize the lower bound , and the upper bound .
Step 2: Solve the NLP subproblem for the fixed value , to obtain the solution and the multipliers for the equations

Step 3: Update the bounds and prepare the information for the master problem:
a. Update the current upper bound; if , set
b. Derive the integer cut, , to make infeasible the choice of the binary from the subsequent iterations:

c. Define the diagonal direction matrix for relaxing the equations into inequalities based on the sign of the multipliers . The diagonal elements are given by:
d. Obtain the following linear outer-approximations for the nonlinear terms by performing first order linearizations at the point  :
Step 4: a. Solve the following MILP master problem:

b. If the MILP master problem has no feasible solution, stop. The optimal solution is .
c. If the MILP master problem has a feasible solution, the new binary value is obtained. Set , return to step 2.

Example

Numerical Example

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

Subject to
Solution
Step 1a: Start from and solve the NLP below:
Minimize
Subject to
Solution: , Upper Bound = 7

Step 1b: Solve the MILP master problem with OA for  :


Minimize

Subject to

MILP Solution: , Lower Bound = 6
Lower Bound < Upper Bound, Integer cut:

Step 2a: Start from and solve the NLP below:
Minimize

Subject to
Solution: , Upper Bound = 6
Upper Bound = 6 = Lower Bound, Optimum!
Optimal Solution for the MINLP:

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: [8]

Uncapacitated Facility Location

Given a set of "customers" with demand for a single commodity and a set of potential "facilities" with unlimited capacity, the Uncapacitated Facility Location (UFL) problem involves choosing a subset of the facilities to open and 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. [9]

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 with arc costs and capacities and a set of demands which are described by the set of paths they can use , the quantity of flow that need to be routed and the maximum delay for this demand . 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 is smaller than . [10]

Stochastic Service Systems Design Problems (SSSD)

SSSD consists in configuring optimally the service levels of a network of queues. We are given a set of customers , a set of facilities and a set of service levels . Each customer has a mean demand rate . 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 at rate , a fixed cost for assigning customer to facility . A binary variable indicates if customer is served by facility , and a binary variable indicates if facility is operated at service level . [11]

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.[4] 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.

References

Template:Reflist

  1. Kronqvist, J., Bernal, D. E., Lundell, A., & Westerlund, T. (2019). “A center-cut algorithm for quickly obtaining feasible solutions and solving convex MINLP problems”. Computers & Chemical Engineering, 122, 105-113.
  2. Kronqvist, J., Bernal, D. E., Lundell, A., & Grossmann, I. E. (2019). “A review and comparison of solvers for convex MINLP”. Optimization and Engineering, 20(2), 397-455.
  3. Bernala, D. E., Pengb, Z., Kronqvistc, J., & Grossmanna, I. E. (2021). “Alternative Regularizations for Outer-Approximation Algorithms for Convex MINLP”.
  4. 4.0 4.1 4.2 4.3 Biegler, L. T., Grossmann, I. E., & Westerberg, A. W. (1997). “Systematic methods for chemical process design”.
  5. Grossmann, I. E. (2002). “Review of nonlinear mixed-integer and disjunctive programming techniques”. Optimization and engineering, 3(3), 227-252.
  6. Duran, M. A., & Grossmann, I. E. (1986). “An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Mathematical programming”, 36(3), 307-339.
  7. You, F. (2021). Lecture on Mixed Integer Non-Linear Programming (MINLP). Archives for CHEME 6800 Computational Optimization (2021FA), Cornell University, Ithaca, NY.
  8. Hijazi, H., Bonami, P., & Ouorou, A. (2010). An outer-inner approximation for separable MINLPs. LIF.
  9. Günlük, O., Lee, J., & Weismantel, R. (2007). MINLP strengthening for separable convex quadratic transportation-cost UFL. IBM Res. Report, 1-16.
  10. Ben-Ameur, W., & Ouorou, A. (2006). Mathematical models of the delay constrained routing problem. Algorithmic Operations Research, 1(2), 94-103.
  11. Elhedhli, Samir. 2006. Service System Design with Immobile Servers, Stochastic Demand, and Congestion. Manufacturing & Service Operations Management 8 92–97. doi:10.1287/msom.1050.0094.