McCormick envelopes: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
VisualWikitext
mNo edit summary
No edit summary
 
(50 intermediate revisions by the same user not shown)
Line 1: Line 1:
Author: Susan Urban (smu29) (SYSEN 5800 Fall 2021)  
Author: Susan Urban (SYSEN 5800 Fall 2021)  


== '''Introduction''' ==
== Introduction ==
Optimization of a non-convex function f(x) is challenging since it may have multiple locally optimal solutions or no solution and it can take a significant amount of time, resources, and effort to determine if the solution is global or the problem has no solution. Gradient based solvers are unable to certify optimality<sup>1</sup>. Different techniques are used to address this challenge depending on the characteristics of the problem. One technique used is convex envelopes<sup>2</sup>:
The McCormick Envelope, originally developed by Dr. Garth McCormick, is a type of convex relaxation used for the optimization of bilinear <math>(e.g., x*y, e^xy + y, sin(x+y) - x^2)
</math> non-linear programming (NLP) problems<sup>1</sup>. Optimization of these non-convex functions f(x) is challenging since they may have multiple locally optimal solutions or no solution. It can take a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution<sup>2</sup>. Different techniques are used to address this challenge depending on the characteristics of the problem.
== Theory, Methodology and Algorithmic Discussions ==
[[File:Image of updated estimators and envelopes.png|thumb|Figure 1: Relationships between the given function, concave over-estimators, convex under-estimators, a concave envelope, and a convex envelope. ]]
As McCormick noted, McCormick Envelopes are based on the key assumption that convex and concave envelopes can be constructed for the given function<sup>1</sup>. The concave envelope, and respectively the convex envelope, is the concave over-estimator and convex under-estimator for the given function providing the tightest fit to the given function<sup>1</sup>.  The envelope surrounds the given function, like an envelope encloses a letter, and limits the feasible solution space the most in comparison to all other concave over-estimators and convex under-estimators. Multiple concave over-estimators and multiple convex under-estimators may exist but there is only one concave envelope and one convex envelope for a given function and domain.  Figure 1 depicts the relationship between the given function f(x), multiple concave over-estimators, multiple convex under-estimators, a convex envelope, and a concave envelope. 


Given a non-convex function f(x), g(x) is a convex envelope of f(x) for X <math>\in</math> S if:
Each bilinear term is replaced with a new variable and four sets of constraints are added<sup>1</sup>. The non-linear programming is converted to a relaxed convex linear programming (LP) which can be more easily solved.


·      g(x) is convex under-estimator of f(x)
The LP solution gives a lower (L) bound and any feasible solution to the problem gives an upper (U) bound.


·      g(x)>=h(x) for all convex under-estimators h(x)
As noted by Scott et al, McCormick envelopes are effective since they are recursive, can be applied to a variety of applications, and are typically stronger than those resulting from convexification or linearization procedures<sup>3</sup>.


== '''McCormick Envelopes''' ==
The following is a derivation of the McCormick Envelopes for a given bilinear function<sup>1</sup>:
In particular, for bilinear (e.g., x*y, x<sup>2</sup>) Non-Linear Programming (NLP) problems<sup>3</sup>, the McCormick Envelope<sup>4</sup> is a type of convex relaxation used for optimization.  


In case of an NLP, an LP relaxation is derived by replacing each bilinear term with a new variable and adding four sets of constraints. In the case of an MINLP, an MILP relaxation is derived. This strategy is known as McCormick relaxation.
<math>Let \ w = xy</math>
 
The LP solution gives a lower bound and any feasible solution gives an upper bound.
 
As noted by Scott et al5, McCormick envelopes are attractive due to their recursive nature of their definition, which affords wide applicability and easy implementation computationally.  Furthermore, these relaxations are typically stronger than those resulting from convexification or linearization procedures.
 
== '''Derivation of McCormick Envelopes''' ==
The following is a derivation of the McCormick Envelopes:<sup>2</sup>
 
<math>w = xy</math>


<math>x^{L}\leq x\leq x^{U}</math>
<math>x^{L}\leq x\leq x^{U}</math>
Line 33: Line 27:


<math>b=\left (y-y^{L} \right )</math>
<math>b=\left (y-y^{L} \right )</math>
a and b are both positive resulting in a positive product


<math>a * b\geq 0</math>
<math>a * b\geq 0</math>


<math>a * b=\left ( x-x^{L} \right )\left ( y-y^{L} \right )=xy-x^{L}y-xy^{L}+x^{L}y^{L}\geq 0 </math>
<math>a * b=\left ( x-x^{L} \right )\left ( y-y^{L} \right )=xy-x^{L}y-xy^{L}+x^{L}y^{L}\geq 0 </math>
substituting w=xy and reformulating the inequality produces


<math>w\geq x^{L}y+xy^{L}-x^{L}y^{L}</math>
<math>w\geq x^{L}y+xy^{L}-x^{L}y^{L}</math>
Following the same sequence of steps, the remaining inequalities are produced:


<math>a=\left ( x^{U}-x \right )</math>
<math>a=\left ( x^{U}-x \right )</math>
Line 45: Line 45:


<math>w\geq x^{U}y+xy^{U}-x^{U}y^{U}</math>
<math>w\geq x^{U}y+xy^{U}-x^{U}y^{U}</math>


<math>a=\left ( x^{U}-x\right )</math>
<math>a=\left ( x^{U}-x\right )</math>
Line 58: Line 59:


<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>
<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>


The under-estimators of the function are represented by:
The under-estimators of the function are represented by:
Line 65: Line 65:


<math>w\geq x^{U}y+xy^{U}-x^{U}y^{U}</math>
<math>w\geq x^{U}y+xy^{U}-x^{U}y^{U}</math>


The over-estimators of the function are represented by:
The over-estimators of the function are represented by:
Line 73: Line 72:
<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>
<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>


== '''Example: Convex Relaxation''' ==
The following shows the relaxation of a non-convex problem using McCormick Envelopes:
The following shows the relaxation of a non-convex problem:<sup>2</sup>


Original non-convex problem:  
The original non-convex problem:  


<math>\min Z= \textstyle \sum_{i=1} \sum_{j=1}  c_{i,j}x_i x_j +g_0(x)
<math>\min Z= \textstyle \sum_{i=1} \sum_{j=1}  c_{i,j}x_i x_j +g_0(x)
</math>
</math>


<math>s.t. \sum_{i=1}^N\sum_{j=1}^N c_{i,j}^l x_i x_j + g_l (x) \leq 0,\forall l \in L
<math>s.t. \sum_{i=1}\sum_{j=1} c_{i,j}^l x_i x_j + g_l (x) \leq 0,\forall l \in L


</math>
</math>
Line 89: Line 87:
</math>
</math>


Replacing <math>u_{i,j} = x_i x_j</math> we obtain a relaxed, convex problem:  
Replacing <math>u_{i,j} = x_i x_j</math>, we obtain a relaxed, convex problem using McCormick Envelopes:


<math>\min Z= \textstyle \sum_{i=1} \sum_{j=1}  c_{i,j} u_{i,j} +g_0(x)</math>
<math>\min Z= \textstyle \sum_{i=1} \sum_{j=1}  c_{i,j} u_{i,j} +g_0(x)</math>


<math>s.t. \sum_{i=1}^N\sum_{j=1}^N c_{i,j}^l u_{i,j}+ g_l (x) \leq 0,\forall l \in L</math>
<math>s.t. \sum_{i=1}\sum_{j=1} c_{i,j}^l u_{i,j}+ g_l (x) \leq 0,\forall l \in L</math>


<math>u_{i,j} \geq x_i^L x_j + x_i x_j^L - {x_i}^L {x_j}^L, \forall l \in L
<math>u_{i,j} \geq x_i^L x_j + x_i x_j^L - {x_i}^L {x_j}^L, \forall i,j \  




Line 101: Line 99:
</math>
</math>


<math>u_{i,j} \geq x_i^U x_j + x_i x_j^U - {x_i}^U {x_j}^U, \forall l \in L
<math>u_{i,j} \geq x_i^U x_j + x_i x_j^U - {x_i}^U {x_j}^U, \forall i,j \  




</math>
</math>


<math>u_{i,j} \geq x_i^L x_j + x_i x_j^U - {x_i}^L {x_j}^U, \forall l \in L
<math>u_{i,j} \leq x_i^L x_j + x_i x_j^U - {x_i}^L {x_j}^U, \forall i,j \  


</math>
</math>


<math>u_{i,j} \geq x_i^U x_j + x_i x_j^L - {x_i}^U {x_j}^L, \forall l \in L
<math>u_{i,j} \leq x_i^U x_j + x_i x_j^L - {x_i}^U {x_j}^L, \forall i,j \  


</math>
</math>


<math>x^L \leq x^U, u^L \leq u^U</math>
<math>x^L \leq x \leq x^U,   \ \ u^L \leq u \leq u^U</math>
 
Similar steps are taken to derive the McCormick Envelopes for given functions with different formats e.g., e<sup>xy</sup>.


Good bounds are essential to focusing the feasible solution and reducing the number of iterations.  Good bounds may be obtained either by inspection or solving the optimization problem to minimize (maximize) x, subject to the same constraints as the original problem.<sup>2</sup>
Good lower and upper bounds focus and minimize the feasible solution space; they reduce the number of iterations to find the optimal solution.


As noted by Hazaji<sup>6</sup>, state-of-the-art global optimization solvers implement bound contraction techniques in order to improve this bounding procedure. Once bound contraction is optimized or completed,
'''Piecewise McCormick Relaxation'''


domain partitioning may become necessary. Spatial branch and bound schemes<sup>7,8</sup>  are among the most effective partitioning methods in global optimization<sup>4</sup>.  By dividing the domain of a given variable, the solver is able to divide the original domain into smaller regions, further tightening the convex relaxations of each partition.
As discussed by Hazaji, global optimization solvers focus initially on optimizing the lower and upper bounds, and when necessary, focus on domain partitioning<sup>4</sup>.  By dividing the domain of a given variable into partitions or smaller regions, the solver is able to tailor and further tighten the convex relaxations of each partition. This strategy is known as the Piecewise McCormick relaxation<sup>5</sup>. 
 
== Example: Numerical ==
For the given problem,


== '''Example: Numerical''' ==
<math>min \  Z = xy + 6x + y</math>
<math>min \  Z = xy + 6x + y</math>


Line 131: Line 133:


<math>0 \leq y \leq 2</math>
<math>0 \leq y \leq 2</math>




<math>Let\  w = xy  
<math>Let\  w = xy  
</math>
</math>
<math>x^L = 0 
</math>
<math>x^U = 10</math>
<math>y^L = 0
</math>
<math>y^U = 2




<math>min \ Z = -w + 6x + y
</math>
 
Substituting these values into the original problem and the McCormick Envelopes, the problem is reformulated:
 
<math>min \ Z = w + 6x + y
</math>  
</math>  


<math>s.t. \ w \leq 18</math>
<math>s.t. \ w \leq 18</math>


<math>w \geq 0
<math>w\geq x^{L}y+xy^{L}-x^{L}y^{L}</math>
 
<math>w \geq 0*y + x * 0 - 0*0


</math>


<math>w \geq 10y + 2x - 20




</math>


<math>w \geq 0


</math>
</math>


<math>w \leq 10y
<math>w\geq x^{U}y+xy^{U}-x^{U}y^{U}</math>


<math>w \geq 10*y + x*2 - 10*2


</math>


<math>w \leq 2x




</math>
</math>


Using GAMS, the solution is z= -24, x=6, y=2.
<math>w \geq 10y + 2x - 20




'''GAMS code sample:'''


variable z;


positive variable x, y, w;
</math>


equations  obj, c1, c2, c3, c4, c5 ;
<math>w\leq x^{U}y+xy^{L}-x^{U}y^{L}</math>


obj..    z =e= -w -2*x ;
<math>w \leq 10*y + x*0 - 10*0


c1..     w =l= 12 ;


c2..     w =g= 0;


c3..     w =g= 6*y +3*x -18;


c4..     w =l= 6*y;
</math>


c5..     w =l= 3*x;
<math>w \leq 10y


x.up = 10;


x.lo =0;    


y.up = 2;  


y.lo = 0;       
</math>
 
<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>


model course5800 /all/;
<math>w \leq x*2 + 0*y -0*2


option mip = baron;


option optcr = 0;


solve course5800 minimizing z using mip ;
</math>


== '''Application''' ==
<math>w \leq 2x
Bilinear expressions are the most common non-convex components in mathematical formulations modeling problems in: <sup>5</sup>


Chemical engineering <sup>9, 10, 11, 12</sup>


Process network problems<sup>13</sup> (Quesada & Grossmann, 1995)
</math>


Water networks<sup>14</sup> (Bagajewicz, 2000)                                                            
Using GAMS to solve the reformulated problem, the solution is z= -76.2, x=10, y=1.8.


Pooling and blending<sup>15</sup> (Haverly, 1978)
== Applications ==
Bilinear functions occur in numerous engineering and natural science applications where McCormick Envelopes can be utilized. 


Supply Chain and Transportation <sup>16, 10, 11, 12</sup>
For example, an application involves the modeling of dynamic biological processes based on experimental data<sup>2</sup>.  The challenge for this model is establishing model parameter values that align or calibrate the model response with observed data.  These model parameter values can be estimated using optimization techniques, including McCormick Envelopes, to minimize the difference between observed and simulated data. 


Energy Systems <sup>17 18 19 20</sup>
Another application involves the optimization of financial objectives and risk management for energy conversion for a large scale operation such as a college campus or a municipality<sup>6</sup>.  This operation involves flexibility of energy sources and several facets of uncertainty involved with pricing. This model uses McCormick Envelopes to optimize the bilinear nonconvex components. 


== '''Conclusion''' ==
A third application involves the optimized efficiency and reliability of the operation of the electricity grid.  Optimal power flow (OPF) and unit commitment (UC) are two optimization problems that support the electricity market operations<sup>7</sup>. McCormick Envelopes are used to strengthen the second-order cone (SOC) relaxation of the alternate current optimal power flow (ACOPF)<sup>8</sup>.
McCormick Envelopes provide a relaxation technique for bi-linear non-convex nonlinear programming problems<sup>3</sup>. Since non-convex NLP are challenging to solve and may be time or computationally resource intensive, McCormick envelopes are relevant due to their recursive nature, which affords wide applicability and easy implementation computationally.  Furthermore, these relaxations are typically stronger than those resulting from convexification or linearization procedures<sup>4</sup>.
== Conclusion ==
Non-convex NLPs are challenging to solve and may require a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution.  McCormick Envelopes provide a relaxation technique for bilinear non-convex nonlinear programming problems.  McCormick Envelopes provide a straightforward technique of replacing each bilinear term with a new variable and adding four constraints. Due to the recursive nature of this technique, it may be applied to a wide variety of engineering and scientific applications involving bilinear terms.  


== '''References''' ==
== References ==
# Castro, Pedro. "A Tighter Piecewise McCormick     Relaxation for Bilinear Problems." (n.d.): n. pag. 3 June 2014. Web.    6 June 2015. <<nowiki>http://minlp.cheme.cmu.edu/2014/papers/castro.pdf</nowiki>
# G. P. McCormick, "Computability of Global Solutions To Factorable Nonconvex Solutions: Part I: Convex Underestimating Problems," ''Mathematical Programming,'' vol. 10, pp. 147-175, 1976.  
# You, F (2021). Notes for a lecture on Mixed Integer    Non-Linear Programming (MINLP). Archives for SYSEN 5800 Computational    Optimization (2021FA), Cornell University, Ithaca, NY.
# A. Miro, C. Pozo, G. Guillen-Gosalbez, J. Egea and L. Jimenez, "Deterministic global optimization algorithm based on outer approximation for the parameter estimation of nonlinear dynamic biological systems," ''BMC Bioinformatics,'' vol. 13, 2012.
# Dombrowski, J. (2015, June 7). Northwestern University    Open Text Book on Process Optimization, McCormick Envelopes Retrieved from    <nowiki>https://optimization.mccormick.northwestern.edu/index.php/McCormick_envelopes</nowiki>
# J. K. Scott, M. D. Stuber and P. I. Barton, "Generalized McCormick Relaxations," ''Journal of Global Optimization,'' vol. 51, pp. 569-606, 2011.
# McCormick, Garth P.  Computability of Global Solutions To Factorable Nonconvex Solutions: Part I: Convex Underestimating Problems
# H. Hijazi, "[https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwjSr7eu8K70AhVYmHIEHUJzCVsQFnoECAIQAQ&url=http%3A%2F%2Fwww.optimization-online.org%2FDB_FILE%2F2015%2F03%2F4841.pdf&usg=AOvVaw1xf9B1f-EPw0mG1LOqRfm9 Perspective Envelopes for Bilinear Functions"]
# Scott, J. K. Stuber, M. D. & Barton, P. I. (2011). Generalized McCormick Relaxations. Journal of Global Optimization, Vol. 51, Issue 4, 569-606 doi: 10.1007/s10898-011-9664-7
# P. Castro, "Tightening piecewise McCormick relaxations for bilinear problems," ''Computers & Chemical Engineering'', vol. 72, pp. 300-311, 2015.
# Hijazi, H., Perspective Envelopes for Bilinear Functions, unpublished manuscript, The Australian National University, Canberra, Australia 4841.pdf
# J. Kantor and P. Mousaw, "A class of bilinear models for the optimization of energy conversion networks," ''Chemical Engineering Science,'' vol. 67'','' pp. 131-138, 2012.
# Androulakis, I., Maranas, C., Floudas, C.: alphabb: A global optimization method for general constrained nonconvex problems. Journal of Global Optimization 7(4), 337{363 (1995)
# Jeremy Lin; Fernando H. Magnago, "Optimal Power Flow," in Electricity Markets: Theories and Applications , IEEE, 2017, pp.147-171, doi: 10.1002/9781119179382.ch6.
# Smith, E., Pantelides, C.: A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex fMINLPsg. Computers & Chemical Engineering 23(4), 457 { 478 (1999)
#B. Michael, A. Castillo, J. Watson and C. Laird, "Strengthened SOCP Relaxations for ACOPF with McCormick Envelopes and Bounds Tightening," ''Computer Aided Chemical Engineering,'' vol. 44'','' pp. 1555-1560, 2018.
# Geunes, J., Pardalos, P.: Supply chain optimization, vol. 98. Springer Science & BusinessMedia (2006)
#
# Nahapetyan, A.: Bilinear programming: applications in the supply chain management bilinear programming: Applications in the supply chain management. In: C.A. Floudas, P.M. Pardalos (eds.) Encyclopedia of Optimization, pp. 282{288. Springer US (2009)
# Nahapetyan, A.G., Pardalos, P.M.: A bilinear reduction based algorithm for solving capacitated multi-item dynamic pricing problems. Computers & Operations Research 35(5), 1601 { 1612 (2008). Part Special Issue: Algorithms and Computational Methods in Feasibility and Infeasibility
# Rebennack, S., Nahapetyan, A., Pardalos, P.: Bilinear modeling solution approach for_xed charge network ow problems. Optimization Letters 3(3), 347{355 (2009)
# Quesada, Ignacio & Grossmann, Ignacio. (1995). A Global Optimization Algorithm for Linear Fractional and Bilinear Programs. Journal of Global Optimization. 6. 39-76. 10.1007/BF01106605.
# Bagajewicz, 2000
# Haverly, 1978
# Geunes, J., Pardalos, P.: Supply chain optimization, vol. 98. Springer Science & Business Media (2006) 
# Co_rin, C., Hijazi, H., Van Hentenryck, P., Lehmann, K.: Primal and dual bounds for optimal transmission switching. Proceedings of the 18th Power Syst. Computation Conf., Wroclaw Poland, PSCC (2014)
# Gemine, Q., Ernst, D., Louveaux, Q., Corn_elusse, B.: Relaxations for multi-period optimal power ow problems with discrete decision variables. Proceedings of the 18th Power Syst. Computation Conf., Wroclaw, Poland, PSCC 2014 (2014)
# Hijazi, H., Corin, C., Van Hentenryck, P.: Convex Quadratic Relaxations for Mixed-Integer Nonlinear Programs in Power Systems. NICTA Technical Report (2014)
# Hijazi, H., Thiebaux, S.: Optimal AC distribution systems reconfiguration. Proceedings of the 18th Power Syst. Computation Conf., Wroclaw, Poland, PSCC 2014 (2014)  <br />

Latest revision as of 07:21, 12 December 2021

Author: Susan Urban (SYSEN 5800 Fall 2021)

Introduction

The McCormick Envelope, originally developed by Dr. Garth McCormick, is a type of convex relaxation used for the optimization of bilinear non-linear programming (NLP) problems1. Optimization of these non-convex functions f(x) is challenging since they may have multiple locally optimal solutions or no solution. It can take a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution2. Different techniques are used to address this challenge depending on the characteristics of the problem.

Theory, Methodology and Algorithmic Discussions

Figure 1: Relationships between the given function, concave over-estimators, convex under-estimators, a concave envelope, and a convex envelope.

As McCormick noted, McCormick Envelopes are based on the key assumption that convex and concave envelopes can be constructed for the given function1. The concave envelope, and respectively the convex envelope, is the concave over-estimator and convex under-estimator for the given function providing the tightest fit to the given function1. The envelope surrounds the given function, like an envelope encloses a letter, and limits the feasible solution space the most in comparison to all other concave over-estimators and convex under-estimators. Multiple concave over-estimators and multiple convex under-estimators may exist but there is only one concave envelope and one convex envelope for a given function and domain. Figure 1 depicts the relationship between the given function f(x), multiple concave over-estimators, multiple convex under-estimators, a convex envelope, and a concave envelope.

Each bilinear term is replaced with a new variable and four sets of constraints are added1. The non-linear programming is converted to a relaxed convex linear programming (LP) which can be more easily solved.

The LP solution gives a lower (L) bound and any feasible solution to the problem gives an upper (U) bound.

As noted by Scott et al, McCormick envelopes are effective since they are recursive, can be applied to a variety of applications, and are typically stronger than those resulting from convexification or linearization procedures3.

The following is a derivation of the McCormick Envelopes for a given bilinear function1:

where are   upper  and   lower  bound  values  for   and , respectively.

a and b are both positive resulting in a positive product

substituting w=xy and reformulating the inequality produces

Following the same sequence of steps, the remaining inequalities are produced:



The under-estimators of the function are represented by:

The over-estimators of the function are represented by:

The following shows the relaxation of a non-convex problem using McCormick Envelopes:

The original non-convex problem:

Replacing , we obtain a relaxed, convex problem using McCormick Envelopes:

Similar steps are taken to derive the McCormick Envelopes for given functions with different formats e.g., exy.

Good lower and upper bounds focus and minimize the feasible solution space; they reduce the number of iterations to find the optimal solution.

Piecewise McCormick Relaxation

As discussed by Hazaji, global optimization solvers focus initially on optimizing the lower and upper bounds, and when necessary, focus on domain partitioning4. By dividing the domain of a given variable into partitions or smaller regions, the solver is able to tailor and further tighten the convex relaxations of each partition. This strategy is known as the Piecewise McCormick relaxation5.

Example: Numerical

For the given problem,


Substituting these values into the original problem and the McCormick Envelopes, the problem is reformulated:

Using GAMS to solve the reformulated problem, the solution is z= -76.2, x=10, y=1.8.

Applications

Bilinear functions occur in numerous engineering and natural science applications where McCormick Envelopes can be utilized.

For example, an application involves the modeling of dynamic biological processes based on experimental data2. The challenge for this model is establishing model parameter values that align or calibrate the model response with observed data. These model parameter values can be estimated using optimization techniques, including McCormick Envelopes, to minimize the difference between observed and simulated data.

Another application involves the optimization of financial objectives and risk management for energy conversion for a large scale operation such as a college campus or a municipality6. This operation involves flexibility of energy sources and several facets of uncertainty involved with pricing. This model uses McCormick Envelopes to optimize the bilinear nonconvex components.

A third application involves the optimized efficiency and reliability of the operation of the electricity grid. Optimal power flow (OPF) and unit commitment (UC) are two optimization problems that support the electricity market operations7. McCormick Envelopes are used to strengthen the second-order cone (SOC) relaxation of the alternate current optimal power flow (ACOPF)8.

Conclusion

Non-convex NLPs are challenging to solve and may require a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution. McCormick Envelopes provide a relaxation technique for bilinear non-convex nonlinear programming problems. McCormick Envelopes provide a straightforward technique of replacing each bilinear term with a new variable and adding four constraints. Due to the recursive nature of this technique, it may be applied to a wide variety of engineering and scientific applications involving bilinear terms.

References

  1. G. P. McCormick, "Computability of Global Solutions To Factorable Nonconvex Solutions: Part I: Convex Underestimating Problems," Mathematical Programming, vol. 10, pp. 147-175, 1976.
  2. A. Miro, C. Pozo, G. Guillen-Gosalbez, J. Egea and L. Jimenez, "Deterministic global optimization algorithm based on outer approximation for the parameter estimation of nonlinear dynamic biological systems," BMC Bioinformatics, vol. 13, 2012.
  3. J. K. Scott, M. D. Stuber and P. I. Barton, "Generalized McCormick Relaxations," Journal of Global Optimization, vol. 51, pp. 569-606, 2011.
  4. H. Hijazi, "Perspective Envelopes for Bilinear Functions"
  5. P. Castro, "Tightening piecewise McCormick relaxations for bilinear problems," Computers & Chemical Engineering, vol. 72, pp. 300-311, 2015.
  6. J. Kantor and P. Mousaw, "A class of bilinear models for the optimization of energy conversion networks," Chemical Engineering Science, vol. 67, pp. 131-138, 2012.
  7. Jeremy Lin; Fernando H. Magnago, "Optimal Power Flow," in Electricity Markets: Theories and Applications , IEEE, 2017, pp.147-171, doi: 10.1002/9781119179382.ch6.
  8. B. Michael, A. Castillo, J. Watson and C. Laird, "Strengthened SOCP Relaxations for ACOPF with McCormick Envelopes and Bounds Tightening," Computer Aided Chemical Engineering, vol. 44, pp. 1555-1560, 2018.
Retrieved from "https://optimization.cbe.cornell.edu/index.php?title=McCormick_envelopes&oldid=5169"