Difference between revisions of "McCormick envelopes"

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
m
Line 115: Line 115:
 
</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} \geq 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} \geq 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>
  
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 bounds are essential to focus and minimize the feasible solution space and to reduce the number of iterations to find the optimal solution"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>
  
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,
+
As discussed by Hazaji<sup>6</sup>, global optimization solvers implement bound contraction techniques and once the boundary is optimized, domain partitioning may become necessary. Spatial branch and bound schemes<sup>7,8</sup>  are among the most effective partitioning methods in global optimization.  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.
 
 
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.
 
  
 
== '''Example: Numerical''' ==
 
== '''Example: Numerical''' ==
Line 140: Line 138:
  
 
<math>0 \leq y \leq 2</math>
 
<math>0 \leq y \leq 2</math>
 +
  
  
 
<math>Let\  w = xy  
 
<math>Let\  w = xy  
 
</math>
 
</math>
 +
  
  
Line 173: Line 173:
  
 
Using GAMS, the solution is z= -24, x=6, y=2.
 
Using GAMS, the solution is z= -24, x=6, y=2.
 +
  
  
Line 212: Line 213:
  
 
== '''Application''' ==
 
== '''Application''' ==
Bilinear expressions are the most common non-convex components in mathematical formulations modeling problems in: <sup>5</sup>
+
Bilinear expressions are the most common non-convex components in mathematical formulations modeling problems in: <sup>6</sup>
  
 
Chemical engineering <sup>9, 10, 11, 12</sup>
 
Chemical engineering <sup>9, 10, 11, 12</sup>
  
Process network problems<sup>13</sup> (Quesada & Grossmann, 1995)
+
Process network problems<sup>13</sup>  
  
Water networks<sup>14</sup> (Bagajewicz, 2000)                                                              
+
Water networks<sup>14</sup>                                                            
  
 
Pooling and blending<sup>15</sup> (Haverly, 1978)
 
Pooling and blending<sup>15</sup> (Haverly, 1978)
Line 235: Line 236:
 
# McCormick, Garth P.  Computability of Global Solutions To Factorable Nonconvex Solutions: Part I: Convex Underestimating Problems
 
# McCormick, Garth P.  Computability of Global Solutions To Factorable Nonconvex Solutions: Part I: Convex Underestimating Problems
 
# 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
 
# 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
# Hijazi, H., Perspective Envelopes for Bilinear Functions, unpublished manuscript, The Australian National University, Canberra, Australia 4841.pdf
+
# Hijazi, H., Perspective Envelopes for Bilinear Functions, unpublished manuscript, retrieved from: [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]
 
# 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)
 
# 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)
 
# 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)  
 
# 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)  
Line 243: Line 244:
 
# Rebennack, S., Nahapetyan, A., Pardalos, P.: Bilinear modeling solution approach for_xed charge network ow problems. Optimization Letters 3(3), 347{355 (2009)  
 
# 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.
 
# 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
+
# Bagajewicz, 2000. A review of recent design procedures for water networks in refineries and process plants. Computers and Chemical Engineering 24.
 
# Haverly, 1978
 
# Haverly, 1978
 
# Geunes, J., Pardalos, P.: Supply chain optimization, vol. 98. Springer Science & Business Media (2006)   
 
# Geunes, J., Pardalos, P.: Supply chain optimization, vol. 98. Springer Science & Business Media (2006)   

Revision as of 11:49, 23 November 2021

Author: Susan Urban (smu29) (SYSEN 5800 Fall 2021)

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 feasible solution. According to Castro1, "Gradient based solvers [are] unable to certify optimality". Different techniques are used to address this challenge depending on the characteristics of the problem. One technique used is convex envelopes2:

Given a non-convex function f(x), g(x) is a convex envelope of f(x) for X S if:

·      g(x) is convex under-estimator of f(x)

·      g(x)>=h(x) for all convex under-estimators h(x)

McCormick Envelopes

In particular, for bilinear (e.g., x*y, x+y) non-linear programming (NLP) problems3, the McCormick Envelope4 is a type of convex relaxation used for optimization.  

In case of an NLP, a linear programming (LP) relaxation is derived by replacing each bilinear term with a new variable and adding four sets of constraints. In the case of a mixed-integer linear programming (MINLP), a MILP relaxation is derived. This strategy is known as McCormick relaxation.

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:2

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





The under-estimators of the function are represented by:


The over-estimators of the function are represented by:

Example: Convex Relaxation

The following shows the relaxation of a non-convex problem:2

Original non-convex problem:

Replacing

we obtain a relaxed, convex problem:

Good bounds are essential to focus and minimize the feasible solution space and to reduce the number of iterations to find the optimal solution. "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."2

As discussed by Hazaji6, global optimization solvers implement bound contraction techniques and once the boundary is optimized, domain partitioning may become necessary. Spatial branch and bound schemes7,8 are among the most effective partitioning methods in global optimization. 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.

Example: Numerical



Using GAMS, the solution is z= -24, x=6, y=2.


GAMS code sample:

variable z;

positive variable x, y, w;

equations  obj, c1, c2, c3, c4, c5 ;

obj..    z =e= -w -2*x ;

c1..     w =l= 12 ;

c2..     w =g= 0;

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

c4..     w =l= 6*y;

c5..     w =l= 3*x;

x.up = 10;

x.lo =0;    

y.up = 2;  

y.lo = 0;       

model course5800 /all/;

option mip = baron;

option optcr = 0;

solve course5800 minimizing z using mip ;

Application

Bilinear expressions are the most common non-convex components in mathematical formulations modeling problems in: 6

Chemical engineering 9, 10, 11, 12

Process network problems13

Water networks14                                                          

Pooling and blending15 (Haverly, 1978)

Supply Chain and Transportation 16, 10, 11, 12

Energy Systems 17 18 19 20

Conclusion

McCormick Envelopes provide a relaxation technique for bi-linear non-convex nonlinear programming problems3. 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 procedures4.

References

  1. Castro, Pedro. "A Tighter Piecewise McCormick Relaxation for Bilinear Problems." (n.d.): n. pag. 3 June 2014. Web. 6 June 2015. <http://minlp.cheme.cmu.edu/2014/papers/castro.pdf
  2. 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.
  3. Dombrowski, J. (2015, June 7). Northwestern University Open Text Book on Process Optimization, McCormick Envelopes Retrieved from https://optimization.mccormick.northwestern.edu/index.php/McCormick_envelopes
  4. McCormick, Garth P.  Computability of Global Solutions To Factorable Nonconvex Solutions: Part I: Convex Underestimating Problems
  5. 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
  6. Hijazi, H., Perspective Envelopes for Bilinear Functions, unpublished manuscript, retrieved from: Perspective Envelopes for Bilinear Functions
  7. 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)
  8. 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)
  9. Geunes, J., Pardalos, P.: Supply chain optimization, vol. 98. Springer Science & BusinessMedia (2006)
  10. 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)
  11. 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
  12. Rebennack, S., Nahapetyan, A., Pardalos, P.: Bilinear modeling solution approach for_xed charge network ow problems. Optimization Letters 3(3), 347{355 (2009)
  13. 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.
  14. Bagajewicz, 2000. A review of recent design procedures for water networks in refineries and process plants. Computers and Chemical Engineering 24.
  15. Haverly, 1978
  16. Geunes, J., Pardalos, P.: Supply chain optimization, vol. 98. Springer Science & Business Media (2006)
  17. 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)
  18. 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)
  19. Hijazi, H., Corin, C., Van Hentenryck, P.: Convex Quadratic Relaxations for Mixed-Integer Nonlinear Programs in Power Systems. NICTA Technical Report (2014)
  20. Hijazi, H., Thiebaux, S.: Optimal AC distribution systems reconfiguration. Proceedings of the 18th Power Syst. Computation Conf., Wroclaw, Poland, PSCC 2014 (2014)