Outer-approximation (OA): Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
Line 168: Line 168:
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.<ref name "Hijazi">Hijazi, H., Bonami, P., & Ouorou, A. (2010). [http://www.optimization-online.org/DB_FILE/2012/08/3581.pdf  “An outer-inner approximation for separable MINLPs”]. LIF.</ref> The followings are some MINLP applications that can be solved by the OA method:  
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.<ref name "Hijazi">Hijazi, H., Bonami, P., & Ouorou, A. (2010). [http://www.optimization-online.org/DB_FILE/2012/08/3581.pdf  “An outer-inner approximation for separable MINLPs”]. LIF.</ref> The followings are some MINLP applications that can be solved by the OA method:  


====Uncapacitated Facility Location====
====Process Synthesis====
Given a set of "customers" <math display=inline>N= \big\{1,2,...n\big\} </math> with demand for a single commodity and a set of potential "facilities" <math display=inline>M= \big\{1,2,...m\big\} </math> with unlimited capacity, the Uncapacitated Facility Location (UFL) problem involves <math display=inline>(i)</math> choosing a subset of the facilities to open and <math display=inline>(ii)</math> 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. <ref>Günlük, O., Lee, J., & Weismantel, R. (2007). [https://dominoweb.draco.res.ibm.com/reports/rc24213.pdf “MINLP strengthening for separable convex quadratic transportation-cost UFL”]. IBM Res. Report, 1-16.</ref>
Process synthesis problems involving the selection of process units and their interconnection as well as the evaluation of the design and operating variables can be conceptually posed as large-scale mixed-integer nonlinear programs (MINLP), where 0-1 binary variables are used to denote the existence (or not) of process units, while continuous variables represent process design and operating values. For the case when multiple choices are possible, one can in fact develop valid linear outer-approximations that properly bound the nonconvex solution space in the MILP master problem.<ref>Grossmann, I. E. (1989). [https://kilthub.cmu.edu/articles/MINLP_optimization_strategies_and_algorithms_for_process_synthesis/6467159/files/11895611.pdf “MINLP optimization strategies and algorithms for process synthesis”]. </ref>


====Delay constrained routing problem====
====Biological kinetic model====
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 <math display=inline>G=(V,E) </math>  with arc costs <math display=inline>w_e </math> and capacities <math display=inline>c_e </math> and a set of <math display=inline>K</math> demands which are described by the set of paths they can use <math display=inline>P(k)</math>, the quantity of flow <math display=inline>v_k </math> that need to be routed and the maximum delay for this demand <math display=inline>\alpha_k </math>. 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 <math display=inline>P_k^i </math> is smaller than  <math display=inline>\alpha_k </math>. <ref>Ben-Ameur, W., & Ouorou, A. (2006). [https://www.erudit.org/en/journals/aor/2009-v4-n2-aor_1_2/AOR1_2art04/  “Mathematical models of the delay constrained routing problem”]. Algorithmic Operations Research, 1(2), 94-103.</ref>
Consider a dynamic kinetic model describing the mechanism of a set of biochemical reactions. The goal is to determine the appropriate values of the model coefficients (e.g., rate constants, initial conditions, etc.), so as to minimize the sum-of-squares of the residuals between the simulated data provided by the model and the experimental observations. The problem solution strategy relies on reformulating the nonlinear dynamic optimization problem as a finite dimensional MINLP by applying a complete discretization using orthogonal collocation on finite elements. This MINLP is next solved using an outer approximation algorithm. <ref>Miró, A., Pozo, C., Guillén-Gosálbez, G., Egea, J. A., & Jiménez, L. (2012). [https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-13-90 “Deterministic global optimization algorithm based on outer approximation for the parameter estimation of nonlinear dynamic biological systems”]. BMC bioinformatics, 13(1), 1-12. </ref>


====Stochastic Service Systems Design Problems (SSSD)====
====Large Hadron Collider====
SSSD consists in configuring optimally the service levels of a network of <math display=inline>M/M/1</math> queues. We are given a set of customers <math display=inline>J</math>, a set of facilities <math display=inline>I</math> and a set of service levels <math display=inline>K</math>. Each customer has a mean demand rate <math display=inline>\lambda_j</math>. 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 <math display=inline>j</math> at rate <math display=inline>k</math>, a fixed cost for assigning customer <math display=inline>i</math> to facility <math display=inline>j</math>. A binary variable <math display=inline>x_ij</math> indicates if customer <math display=inline>i</math> is served by facility <math display=inline>j</math>, and a binary variable <math display=inline>y_jk</math> indicates if facility <math display=inline>j</math> is operated at service level <math display=inline>k</math>. <ref>Elhedhli, S. (2006). [https://pubsonline.informs.org/doi/abs/10.1287/msom.1050.0094?casa_token=Jof1qfCxtP8AAAAA:OOH7rqGeKkrUYx6K2ZE3r0GrfLvIu7H5fjWHWPSLnNtAbg442_c65RaGmI4VIUtmpDZkMgpvfbyz  “Service system design with immobile servers, stochastic demand, and congestion”]. Manufacturing & Service Operations Management, 8(1), 92-97.</ref>
A thermal insulation system uses a series of heat intercepts and surrounding insulators to minimize the power required to maintain the heat intercepts at certain temperatures. The designer chooses the maximum number of intercepts, the thickness and area of each intercept, and the material of intercept from a discrete set of materials. The choice of material affects the thermal conductivity and total mass of the insulation system. Nonlinear functions in the model are required to accurately model system characteristics such as heat flow between the intercepts, thermal expansion, and stress constraints. Integer variables are used to model the discrete choice of the type of material to use in each layer. This problem can be modeled as MINLP and solved by OA. <ref>Leyffer, S., Linderoth, J., Luedtke, J., Miller, A., & Munson, T. (2009, July).[ https://iopscience.iop.org/article/10.1088/1742-6596/180/1/012014/meta “Applications and algorithms for mixed integer nonlinear programming”]. In Journal of Physics: Conference Series (Vol. 180, No. 1, p. 012014). IOP Publishing. </ref>


==Conclusion==
==Conclusion==

Revision as of 05:57, 15 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 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.[4]

Theory

The Outer-Approximation (OA) algorithm was proposed by Duran and and Grossmann in 1986 to solve MINLP problems.[5] 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.[5] 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. [6]

Algorithm

Consider the following MINLP formulation : [6]
min
s.t.






The specific steps of OA algorithm, assuming feasible solutions for the NLP subproblems, are as follows:[6]
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.

Numerical Example

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

Problem

Solution

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

Iteration 1:

Solution: , Upper Bound


Step 3: Update the bounds and prepare the information for the master problem:
set
Obtain the following linear outer-approximations for the nonlinear terms by performing first order linearizations at the point  :






Step 4: Solve the MILP master problem with OA for  :

MILP Solution: , Lower Bound

Lower Bound < Upper Bound, Integer cut:
Set iteration , return to step 2.

Iteration 2:

Step 2: Start from and solve the NLP below:

Solution: , Upper Bound
Upper Bound = 6 = Lower Bound, Optimum!

Optimal Solution for the MINLP:

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

Process Synthesis

Process synthesis problems involving the selection of process units and their interconnection as well as the evaluation of the design and operating variables can be conceptually posed as large-scale mixed-integer nonlinear programs (MINLP), where 0-1 binary variables are used to denote the existence (or not) of process units, while continuous variables represent process design and operating values. For the case when multiple choices are possible, one can in fact develop valid linear outer-approximations that properly bound the nonconvex solution space in the MILP master problem.[9]

Biological kinetic model

Consider a dynamic kinetic model describing the mechanism of a set of biochemical reactions. The goal is to determine the appropriate values of the model coefficients (e.g., rate constants, initial conditions, etc.), so as to minimize the sum-of-squares of the residuals between the simulated data provided by the model and the experimental observations. The problem solution strategy relies on reformulating the nonlinear dynamic optimization problem as a finite dimensional MINLP by applying a complete discretization using orthogonal collocation on finite elements. This MINLP is next solved using an outer approximation algorithm. [10]

Large Hadron Collider

A thermal insulation system uses a series of heat intercepts and surrounding insulators to minimize the power required to maintain the heat intercepts at certain temperatures. The designer chooses the maximum number of intercepts, the thickness and area of each intercept, and the material of intercept from a discrete set of materials. The choice of material affects the thermal conductivity and total mass of the insulation system. Nonlinear functions in the model are required to accurately model system characteristics such as heat flow between the intercepts, thermal expansion, and stress constraints. Integer variables are used to model the discrete choice of the type of material to use in each layer. This problem can be modeled as MINLP and solved by OA. [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.[6] 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

  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. Grossmann, I. E. (2002). “Review of nonlinear mixed-integer and disjunctive programming techniques”. Optimization and engineering, 3(3), 227-252.
  5. 5.0 5.1 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.
  6. 6.0 6.1 6.2 6.3 Biegler, L. T., Grossmann, I. E., & Westerberg, A. W. (1997). “Systematic methods for chemical process design”.
  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. Grossmann, I. E. (1989). “MINLP optimization strategies and algorithms for process synthesis”.
  10. Miró, A., Pozo, C., Guillén-Gosálbez, G., Egea, J. A., & Jiménez, L. (2012). “Deterministic global optimization algorithm based on outer approximation for the parameter estimation of nonlinear dynamic biological systems”. BMC bioinformatics, 13(1), 1-12.
  11. Leyffer, S., Linderoth, J., Luedtke, J., Miller, A., & Munson, T. (2009, July).[ https://iopscience.iop.org/article/10.1088/1742-6596/180/1/012014/meta “Applications and algorithms for mixed integer nonlinear programming”]. In Journal of Physics: Conference Series (Vol. 180, No. 1, p. 012014). IOP Publishing.