A MPCC-NLP Approach for an Electric Power Market Problem

Affiliation(s)

School of Business Studies, Viana do Castelo Polytechnic Institute, Portugal.

Department of Production and Systems, University of Minho, Portugal.

School of Business Studies, Viana do Castelo Polytechnic Institute, Portugal.

Department of Production and Systems, University of Minho, Portugal.

ABSTRACT

The electric power market is changing-it has passed from a regulated market, where the government of each country had the control of prices, to a deregulated market economy. Each company competes in order to get more cli.e.nts and maximize its profits. This market is represented by a Stackelberg game with two firms, leader and follower, and the leader anticipates the reaction of the follower. The problem is formulated as a Mathematical Program with Complementarity Constraints (MPCC). It is shown that the constraint qualifications usually assumed to prove convergence of standard algorithms fail to hold for MPCC. To circumvent this, a reformulation for a nonlinear problem (NLP) is proposed. Numerical tests using the NEOS server platform are presented.

The electric power market is changing-it has passed from a regulated market, where the government of each country had the control of prices, to a deregulated market economy. Each company competes in order to get more cli.e.nts and maximize its profits. This market is represented by a Stackelberg game with two firms, leader and follower, and the leader anticipates the reaction of the follower. The problem is formulated as a Mathematical Program with Complementarity Constraints (MPCC). It is shown that the constraint qualifications usually assumed to prove convergence of standard algorithms fail to hold for MPCC. To circumvent this, a reformulation for a nonlinear problem (NLP) is proposed. Numerical tests using the NEOS server platform are presented.

KEYWORDS

Electric Power, Stackelberg Game, Nonlinear Programming, Complementarity Constrained Optimization

Electric Power, Stackelberg Game, Nonlinear Programming, Complementarity Constrained Optimization

Cite this paper

nullH. Rodrigues, M. Monteiro and A. Vaz, "A MPCC-NLP Approach for an Electric Power Market Problem,"*Smart Grid and Renewable Energy*, Vol. 1 No. 1, 2010, pp. 54-61. doi: 10.4236/sgre.2010.11009.

nullH. Rodrigues, M. Monteiro and A. Vaz, "A MPCC-NLP Approach for an Electric Power Market Problem,"

References

[1] M. Willrich, “Electricity Transmission Policy for America: Enabling a Smart Grid, End to End,” The Electricity Journal, Vol. 22, No. 10, 2009, pp. 77-82.

[2] “Third Benchmarking Report on the Implementation of the Internal Electricity and Gas Markets,” Tech Republic 1, Commission Draft Staff Paper, March 2004.

[3] B. F. Hobbs and F. A. M. Rijkers, “Strategic Generation with Conjectured Transmission Price Responses in a Mixed Transmission Pricing System,” IEEE Transmissions on Power Systems, Vol. 19, No. 2, 2004, pp. 707-879.

[4] Y. Smeers, “How Well Can Measure Market Power in Restructured Electricity Systems,” Tech Republic, University Catholique De Louvain, November 2004.

[5] S. A. Gabriel and F. U. Leuthold, “Solving Discretely- Constrained MPEC Problems with Applications in Electric Power Markets,” Energy Economics, Vol. 32, 2010, pp. 3-14.

[6] M. Crappe, “Electric Power Systems,” Wiley-ISTE, 2009.

[7] C. B. Metzler, “Complementarity Models of Competitive Oligopolistic Electric Power Generation Markets,” Master’s Thesis, The Johns Hopkins University, 2000.

[8] Z.-Q. Luo, J.-S. Pang and D. Ralph, “Mathematical Programs with Equilibrium Constraints,” Cambridge University Press, Cambridge, 1996.

[9] L. N. Vicente and P. H. Calamai, “Bilevel and Multilevel Programming: a Bibliography Review,” Journal of Global Optimization, Vol. 5, 1994, pp. 291-306.

[10] S. Dempe, “Annotated Bibliography on Bilevel Program- ming and Mathematical Programs with Equilibrium Con- straints,” Optimization, Vol. 52, No. 3, 2003, pp. 333-359.

[11] M. C. Ferris and J. S. Pang, “Engineering and Economic applications of Complementarity Problems,” SIAM Review, Vol. 39, No. 4, 1997, pp. 669-713.

[12] M. F. Ferris and F. Tin-Loi, “Limit Analysis of Frictional Block Assemblies as a Mathematical Program with Com- plementarity Constraints,” International Journal of Mech- anical Sciences, Vol. 43, 2001, pp. 209-224.

[13] J. S. Pang, “Complementarity Problems,” In: Publishers, K.A., Ed., Handbook in Global Optimization, R. Horst and P. Pardalos, Boston, 1994.

[14] J. F. Rodrigues, “Obstacle Problems in Mathematics Phy- Sics,” Elsevier Publishing Company, Amsterdam, 1987.

[15] M. C. Ferris and F. Tin-Loi, “On the Solution of a Minimum Weight Elastoplastic Problem Involving Dis- placement and Complementarity Constraints,” Computer Methods in Applied Mechanics and Engineering, Vol. 174, 1999, pp. 107-120.

[16] K. P. Oh and P. K. Goenka, “The Elastohydrodynamic Solution of Journal Bearings under Dynamic Loading,” Transactions of ASME, Vol. 107 ,1985, pp. 389-395.

[17] A. U. Raghunathan and L. T. Biegler, “Mathematical Pro- grams with Equilibrium Constraints (Mpecs) in Process Engineering,” Tech Republic, CMU Chemical Engine- ering November 2002.

[18] O. Drissi-Kaitouni and J. Lundgren, “Bilivel Origin-Dest- ination Matrix Estimation Using a Descent Approach,” Tech Republic LITH-MAT-R-1992-49, Linköping Institute of Technology, Department of Mathematics, Sweden, 1992.

[19] M. Stohr, “Nonsmooth Trust Region Methods and their Applications to Mathematical Programs with Equilibrium Constraints,” Shaker Verlag, Aachen, 2000.

[20] C. Ballard, D. Fullerton, J. B. Shoven and J. Whalley, “A General Equilibrium Modelfor Tax Policy Evaluation,” National Bureau of Economic Research Monograph, Chicago, 1985.

[21] H. Ehtamo and T. Raivio, “On Aapplied Nonlinear and Bilevel Programming for Pursuit-Evasion Games,” Journal of Optimization Theory and Applications, Vol. 108, 2001, pp. 65-96.

[22] J. V. Outrata, “On Necessary Optimal Conditions for Stackelberg Problems,” Journal of Optimization Theory and Applications, Vol. 76, 1993, pp. 305-320.

[23] J. C. Carbone, C. Helm and T. F. Rutherford, “Coalition formation and International Trade in Greenhouse Gas Emission Rights,” October 2003.

[24] G. Hibino, M. Kainuma and Y. Matsuoka, “Two-Level Mathematical Programming for Analysing Subsidy Options to Reduce Greenhouse-Gas Emissions,” Tech Republic, Laxenburg ,1996.

[25] M. Kocvara and J. V. Outrata, “Optimization Problems with Equilibrium Constraints and Their Numerical Solution,” Mathematical Programs, Series B, Vol. 101, 2004, pp. 119-149.

[26] H. S. Rodrigues and M. T. Monteiro, “Solving Mathe- matical Program with Complementarity Constraints (MPCC) with Nonlinear Solvers,” Recent Advances in Optimization, Lectures Notes in Economics and Mathe- matical Systems.

[27] J. F. Bard, “Convex Two-Level Optimization,” Mathema- tical Programming, Vol. 40, No. 1, 1988, pp. 15-27.

[28] J. Outrata, M. Kocvara and J. Zowe, “Nonsmooth App- roach to Optimization Problems with Equilibrium Cons- traints,” Kluwer Academic Publishers, Dordrecht, 1998.

[29] M. C. Ferris, S. P. Dirkse and A. Meeraus, “Mathematical Programs with Equilibrium Constraints: Automatic Reformulation and Solution via Constrained Optimi- zation,” Tech Republic, Oxford University Computing Laboratory, July 2002.

[30] H. Scheel and S. Scholtes, “Mathematical Programs with Complementarity Constraints: Stationarity, Optimality and Sensitivity,” Mathematics of Operations Research, Vol. 25, 2000, pp. 1-22.

[31] S. Scholtes, “Convergence Properties of a Regularization Scheme for Mathematical Programs with Complementarity Constraints,” SIAM Journal Optmization, Vol. 11, No. 4, 2001, pp. 918-936.

[32] B. F. Hobbs, C. B. Metzler and J.-S. Pang, “Strategic Gaming Analysis for Electric Power Systems: An MPEC Approach,” IEEE Transactions on Power Systems, Vol. 15,No. 2, 2000, pp. 638-645.

[33] V. Krishna and V. C. Ramesh, “Intelligent agents in Neg- otIations in Market Games, Part 2: Application,” IEEE Transactions on Power Systems Vol. 13, No. 3, 1998, pp. 1109-1114.

[34] O. Alsa and B. Scott, “Optimal Load Flow with Steady- State Security,” IEEE Transactions on Power Systems, Vol. 93, No. 3, 1973, pp. 745-751.

[35] S. Leyffer, Macmpec, 2010. www.mcs.nl.gov/leyffer/ macmpec

[36] Lancelot, 2010. www.numerical.rl.ac.uk/lancelot/blurb.html

[37] H. Benson, A. Sen, D. Shano and R. Vanderbei, “Interior- Point Algorithms Penalty Methods and Equilibrium Prob- lems,” Tech Republic, Operations Research and Financial Engineering Princeton University, October 2003.

[38] NEOS, 2010. www-neos.mcs.ang.gov/neos

[1] M. Willrich, “Electricity Transmission Policy for America: Enabling a Smart Grid, End to End,” The Electricity Journal, Vol. 22, No. 10, 2009, pp. 77-82.

[2] “Third Benchmarking Report on the Implementation of the Internal Electricity and Gas Markets,” Tech Republic 1, Commission Draft Staff Paper, March 2004.

[3] B. F. Hobbs and F. A. M. Rijkers, “Strategic Generation with Conjectured Transmission Price Responses in a Mixed Transmission Pricing System,” IEEE Transmissions on Power Systems, Vol. 19, No. 2, 2004, pp. 707-879.

[4] Y. Smeers, “How Well Can Measure Market Power in Restructured Electricity Systems,” Tech Republic, University Catholique De Louvain, November 2004.

[5] S. A. Gabriel and F. U. Leuthold, “Solving Discretely- Constrained MPEC Problems with Applications in Electric Power Markets,” Energy Economics, Vol. 32, 2010, pp. 3-14.

[6] M. Crappe, “Electric Power Systems,” Wiley-ISTE, 2009.

[7] C. B. Metzler, “Complementarity Models of Competitive Oligopolistic Electric Power Generation Markets,” Master’s Thesis, The Johns Hopkins University, 2000.

[8] Z.-Q. Luo, J.-S. Pang and D. Ralph, “Mathematical Programs with Equilibrium Constraints,” Cambridge University Press, Cambridge, 1996.

[9] L. N. Vicente and P. H. Calamai, “Bilevel and Multilevel Programming: a Bibliography Review,” Journal of Global Optimization, Vol. 5, 1994, pp. 291-306.

[10] S. Dempe, “Annotated Bibliography on Bilevel Program- ming and Mathematical Programs with Equilibrium Con- straints,” Optimization, Vol. 52, No. 3, 2003, pp. 333-359.

[11] M. C. Ferris and J. S. Pang, “Engineering and Economic applications of Complementarity Problems,” SIAM Review, Vol. 39, No. 4, 1997, pp. 669-713.

[12] M. F. Ferris and F. Tin-Loi, “Limit Analysis of Frictional Block Assemblies as a Mathematical Program with Com- plementarity Constraints,” International Journal of Mech- anical Sciences, Vol. 43, 2001, pp. 209-224.

[13] J. S. Pang, “Complementarity Problems,” In: Publishers, K.A., Ed., Handbook in Global Optimization, R. Horst and P. Pardalos, Boston, 1994.

[14] J. F. Rodrigues, “Obstacle Problems in Mathematics Phy- Sics,” Elsevier Publishing Company, Amsterdam, 1987.

[15] M. C. Ferris and F. Tin-Loi, “On the Solution of a Minimum Weight Elastoplastic Problem Involving Dis- placement and Complementarity Constraints,” Computer Methods in Applied Mechanics and Engineering, Vol. 174, 1999, pp. 107-120.

[16] K. P. Oh and P. K. Goenka, “The Elastohydrodynamic Solution of Journal Bearings under Dynamic Loading,” Transactions of ASME, Vol. 107 ,1985, pp. 389-395.

[17] A. U. Raghunathan and L. T. Biegler, “Mathematical Pro- grams with Equilibrium Constraints (Mpecs) in Process Engineering,” Tech Republic, CMU Chemical Engine- ering November 2002.

[18] O. Drissi-Kaitouni and J. Lundgren, “Bilivel Origin-Dest- ination Matrix Estimation Using a Descent Approach,” Tech Republic LITH-MAT-R-1992-49, Linköping Institute of Technology, Department of Mathematics, Sweden, 1992.

[19] M. Stohr, “Nonsmooth Trust Region Methods and their Applications to Mathematical Programs with Equilibrium Constraints,” Shaker Verlag, Aachen, 2000.

[20] C. Ballard, D. Fullerton, J. B. Shoven and J. Whalley, “A General Equilibrium Modelfor Tax Policy Evaluation,” National Bureau of Economic Research Monograph, Chicago, 1985.

[21] H. Ehtamo and T. Raivio, “On Aapplied Nonlinear and Bilevel Programming for Pursuit-Evasion Games,” Journal of Optimization Theory and Applications, Vol. 108, 2001, pp. 65-96.

[22] J. V. Outrata, “On Necessary Optimal Conditions for Stackelberg Problems,” Journal of Optimization Theory and Applications, Vol. 76, 1993, pp. 305-320.

[23] J. C. Carbone, C. Helm and T. F. Rutherford, “Coalition formation and International Trade in Greenhouse Gas Emission Rights,” October 2003.

[24] G. Hibino, M. Kainuma and Y. Matsuoka, “Two-Level Mathematical Programming for Analysing Subsidy Options to Reduce Greenhouse-Gas Emissions,” Tech Republic, Laxenburg ,1996.

[25] M. Kocvara and J. V. Outrata, “Optimization Problems with Equilibrium Constraints and Their Numerical Solution,” Mathematical Programs, Series B, Vol. 101, 2004, pp. 119-149.

[26] H. S. Rodrigues and M. T. Monteiro, “Solving Mathe- matical Program with Complementarity Constraints (MPCC) with Nonlinear Solvers,” Recent Advances in Optimization, Lectures Notes in Economics and Mathe- matical Systems.

[27] J. F. Bard, “Convex Two-Level Optimization,” Mathema- tical Programming, Vol. 40, No. 1, 1988, pp. 15-27.

[28] J. Outrata, M. Kocvara and J. Zowe, “Nonsmooth App- roach to Optimization Problems with Equilibrium Cons- traints,” Kluwer Academic Publishers, Dordrecht, 1998.

[29] M. C. Ferris, S. P. Dirkse and A. Meeraus, “Mathematical Programs with Equilibrium Constraints: Automatic Reformulation and Solution via Constrained Optimi- zation,” Tech Republic, Oxford University Computing Laboratory, July 2002.

[30] H. Scheel and S. Scholtes, “Mathematical Programs with Complementarity Constraints: Stationarity, Optimality and Sensitivity,” Mathematics of Operations Research, Vol. 25, 2000, pp. 1-22.

[31] S. Scholtes, “Convergence Properties of a Regularization Scheme for Mathematical Programs with Complementarity Constraints,” SIAM Journal Optmization, Vol. 11, No. 4, 2001, pp. 918-936.

[32] B. F. Hobbs, C. B. Metzler and J.-S. Pang, “Strategic Gaming Analysis for Electric Power Systems: An MPEC Approach,” IEEE Transactions on Power Systems, Vol. 15,No. 2, 2000, pp. 638-645.

[33] V. Krishna and V. C. Ramesh, “Intelligent agents in Neg- otIations in Market Games, Part 2: Application,” IEEE Transactions on Power Systems Vol. 13, No. 3, 1998, pp. 1109-1114.

[34] O. Alsa and B. Scott, “Optimal Load Flow with Steady- State Security,” IEEE Transactions on Power Systems, Vol. 93, No. 3, 1973, pp. 745-751.

[35] S. Leyffer, Macmpec, 2010. www.mcs.nl.gov/leyffer/ macmpec

[36] Lancelot, 2010. www.numerical.rl.ac.uk/lancelot/blurb.html

[37] H. Benson, A. Sen, D. Shano and R. Vanderbei, “Interior- Point Algorithms Penalty Methods and Equilibrium Prob- lems,” Tech Republic, Operations Research and Financial Engineering Princeton University, October 2003.

[38] NEOS, 2010. www-neos.mcs.ang.gov/neos