Skip to main content
Erschienen in: Energy Systems 1/2015

01.03.2015 | Original Paper

On integer programming models for the multi-channel PMU placement problem and their solution

verfasst von: Neng Fan, Jean-Paul Watson

Erschienen in: Energy Systems | Ausgabe 1/2015

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Phasor Measurement Units (PMUs) are starting to see increased deployment, enabling accurate measurement of power grid electrical properties to determine system health. Due to the costs associated with PMU acquisition and maintenance, it is practically important to place the minimum number of PMUs in order to achieve system complete observability. In this paper, we consider a variety of optimization models for the PMU placement problem that addresses more realistic assumptions than simple infinite-capacity placement models. Specifically, instead of assuming that a PMU can sense all lines incident to the bus at which it is placed, we impose the more realistic assumption that PMUs have restricted channel capacity, with per-unit cost given as a function of channel capacity. The optimization objective is then to minimize the total cost of placed PMUs, in contrast to their number. Further, we leverage the zero-injection bus properties to reduce the quantity and cost of placed PMUs. In formulating our optimization models, we identify a close relationship between the PMU placement problem (PPP) and a classic combinatorial problem, the set cover problem (SCP). If channel capacity limits are ignored, there is a close relationship between the PPP and the dominating set problem (DSP), a special case of the SCP. Similarly, when measurement redundancy is imposed as a design requirement, there is a close relationship between the PPP and the set multi-cover problem (SMCP), a generalized version of the SCP. These connections to well-studied combinational problems are not well-known in the power systems literature, and can be leveraged to improve solution algorithms. We demonstrate that more realistic, high-fidelity PPP optimization models can be solved to optimality using commercial integer programing solvers such as CPLEX. Specifically, run-times for all test cases, ranging from IEEE 14-bus to 300-bus test systems, are less than a second. This result indicates that the size of system that can be analyzed using state-of-the-art solvers is considerable. Further, our results call into question the need for problem-specific heuristic solution algorithms for the PPP, many of which have been proposed over the past decade. Finally, we analyze cost versus performance tradeoffs using our PPP optimization models on various IEEE test systems.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A.: Domination in graphs applied to electric power networks. SIAM J. Disc. Math. 15, 519–529 (2002)CrossRefMATHMathSciNet Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A.: Domination in graphs applied to electric power networks. SIAM J. Disc. Math. 15, 519–529 (2002)CrossRefMATHMathSciNet
3.
Zurück zum Zitat Gyllstrom, D., Rosensweig, E., Kurose, J.: Max observability PMU placement with cross-validation. pp. 2011–014. UMass Technical, Report (2011) Gyllstrom, D., Rosensweig, E., Kurose, J.: Max observability PMU placement with cross-validation. pp. 2011–014. UMass Technical, Report (2011)
4.
Zurück zum Zitat Aminifar, F., Fotuhi-Firuzabad, M., Shahidehpour, M., Khodaei, A.: Observability enchcement by optimal placement considering random power system outages. Energy Syst. 2, 25–65 (2011)CrossRef Aminifar, F., Fotuhi-Firuzabad, M., Shahidehpour, M., Khodaei, A.: Observability enchcement by optimal placement considering random power system outages. Energy Syst. 2, 25–65 (2011)CrossRef
5.
Zurück zum Zitat Xu B., Abur, A.: Observability analysis and measurement placement for systems with PMUs. Proc. IEEE PES Conf. Expo. vol. 2, pp. 943–946 (2004) Xu B., Abur, A.: Observability analysis and measurement placement for systems with PMUs. Proc. IEEE PES Conf. Expo. vol. 2, pp. 943–946 (2004)
6.
Zurück zum Zitat Dua, D., Dambhare, S., Gajbhiye, R.K., Soman, S.A.: Optimal multistate scheduling of PMU placement: an ILP approach. IEEE Trans. Power Deliv. 23, 1812–1820 (2008)CrossRef Dua, D., Dambhare, S., Gajbhiye, R.K., Soman, S.A.: Optimal multistate scheduling of PMU placement: an ILP approach. IEEE Trans. Power Deliv. 23, 1812–1820 (2008)CrossRef
7.
Zurück zum Zitat Gou, B.: Generalized integer linear programming formulation for optimal PMU placement. IEEE Trans. Power Syst. 23, 1099–1104 (2008)CrossRefMathSciNet Gou, B.: Generalized integer linear programming formulation for optimal PMU placement. IEEE Trans. Power Syst. 23, 1099–1104 (2008)CrossRefMathSciNet
8.
Zurück zum Zitat Chakrabarti, S., Kyriakides, E., Eliades, D.G.: Placement of synchronized measurements for power system observability. IEEE Trans. Power Deliv. 24, 12–19 (2009)CrossRef Chakrabarti, S., Kyriakides, E., Eliades, D.G.: Placement of synchronized measurements for power system observability. IEEE Trans. Power Deliv. 24, 12–19 (2009)CrossRef
9.
Zurück zum Zitat Aminifar, F., Khodaei, A., Fotuhi-Firuzabad, M., Shahidehpour, M.: Contingency-constrained PMU placement in power networks. IEEE Trans. Power Syst. 25, 516–523 (2010)CrossRef Aminifar, F., Khodaei, A., Fotuhi-Firuzabad, M., Shahidehpour, M.: Contingency-constrained PMU placement in power networks. IEEE Trans. Power Syst. 25, 516–523 (2010)CrossRef
10.
Zurück zum Zitat Aminifar, F., Fotuhi-Firuzabad, M., Shahidehpour, M., Safdarian, A.: Impact of WAMS malfunction on power system reliability assessment. IEEE Trans. Smart Grid 3(3), 1302–1309 (2012)CrossRef Aminifar, F., Fotuhi-Firuzabad, M., Shahidehpour, M., Safdarian, A.: Impact of WAMS malfunction on power system reliability assessment. IEEE Trans. Smart Grid 3(3), 1302–1309 (2012)CrossRef
11.
Zurück zum Zitat Aminifar, F., Fotuhi-Firuzabad, M., Safdarian, A.: Optimal PMU placement based on probabilistic cost/benefit analysis. IEEE Trans. Power Syst. 28(1), 566–567 (2013)CrossRef Aminifar, F., Fotuhi-Firuzabad, M., Safdarian, A.: Optimal PMU placement based on probabilistic cost/benefit analysis. IEEE Trans. Power Syst. 28(1), 566–567 (2013)CrossRef
12.
Zurück zum Zitat Aminifar, F., Fotuhi-Firuzabad, M., Safdarian, A., Shahidehpour, M.: Observability of hybrid AC/DC power systems with variable-cost PMUs. IEEE Trans. Power Deliv. 29(1), 345–352 (2014)CrossRef Aminifar, F., Fotuhi-Firuzabad, M., Safdarian, A., Shahidehpour, M.: Observability of hybrid AC/DC power systems with variable-cost PMUs. IEEE Trans. Power Deliv. 29(1), 345–352 (2014)CrossRef
13.
Zurück zum Zitat Zhao, Z., Makram, E.B.: Optimal PMU placement considering number of analog channels. In: North American Power Symposium (NAPS), pp. 1–5, Boston, MA, USA, 4–6 Aug (2011) Zhao, Z., Makram, E.B.: Optimal PMU placement considering number of analog channels. In: North American Power Symposium (NAPS), pp. 1–5, Boston, MA, USA, 4–6 Aug (2011)
14.
Zurück zum Zitat Emami, R., Abur, A.: Robust measurement design by placing synchronized phasor measurements on network branches. IEEE Trans. Power Syst. 25, 38–43 (2010)CrossRef Emami, R., Abur, A.: Robust measurement design by placing synchronized phasor measurements on network branches. IEEE Trans. Power Syst. 25, 38–43 (2010)CrossRef
15.
Zurück zum Zitat Emami, R.: Enchacement of network monitoring and security analysis using phasor measurement units. Electrical Engineering Dissertations, Northeastern University (2011) Emami, R.: Enchacement of network monitoring and security analysis using phasor measurement units. Electrical Engineering Dissertations, Northeastern University (2011)
16.
Zurück zum Zitat Korkali, M.: Strategic and robust deployment of synchronized phasor measurement units with restricted channel capacity. Master Thesis, Northeastern University (2010) Korkali, M.: Strategic and robust deployment of synchronized phasor measurement units with restricted channel capacity. Master Thesis, Northeastern University (2010)
17.
Zurück zum Zitat Korkali, M., Abur, A.: Placement of PMUs with channel limits. Proc IEEE PES Power Eng Soc Gen Meet 1, 1–4 (2009) Korkali, M., Abur, A.: Placement of PMUs with channel limits. Proc IEEE PES Power Eng Soc Gen Meet 1, 1–4 (2009)
18.
Zurück zum Zitat Korkali, M., Abur, A.: Impact of network sparsity on strategic placement of phasor measurement units with fixed channel capacity. In: Proceedings of 2010 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 3445–3448, Paris, France, May 30–June 2 (2010) Korkali, M., Abur, A.: Impact of network sparsity on strategic placement of phasor measurement units with fixed channel capacity. In: Proceedings of 2010 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 3445–3448, Paris, France, May 30–June 2 (2010)
19.
Zurück zum Zitat Kumar, R., Rao, V.S.: Optimal placement of PMUs with limited number of channels. In: Proceedings of the North American Power Symposium (NAPS), pp. 1–7, Boston, MA, USA, August 4–6 (2011) Kumar, R., Rao, V.S.: Optimal placement of PMUs with limited number of channels. In: Proceedings of the North American Power Symposium (NAPS), pp. 1–7, Boston, MA, USA, August 4–6 (2011)
20.
Zurück zum Zitat Hurtgen, M., Praks, P., Maun, J.-C., Zajac, P.: Measurement placement algorithms for state estimation when the number of phasor measurements by each PMU is limited. 43rd International Universities Power Engineering Conference (UPEC 2008), pp. 1–5, Padova, Italy, September 1–4 (2008) Hurtgen, M., Praks, P., Maun, J.-C., Zajac, P.: Measurement placement algorithms for state estimation when the number of phasor measurements by each PMU is limited. 43rd International Universities Power Engineering Conference (UPEC 2008), pp. 1–5, Padova, Italy, September 1–4 (2008)
21.
Zurück zum Zitat Najafabadi, A. M., Alouani, A. T.: Optimal PMU placement algorithm with minimum measurement channels. In: Proceedings of IEEE Southeastern Conference, pp. 153–157, Nashville, TN, USA, March 17–20 (2011) Najafabadi, A. M., Alouani, A. T.: Optimal PMU placement algorithm with minimum measurement channels. In: Proceedings of IEEE Southeastern Conference, pp. 153–157, Nashville, TN, USA, March 17–20 (2011)
22.
Zurück zum Zitat Cook, S.: The complexity of theorem proving procedures. Proc. the third annual ACM symposium on Theory of computing, pp. 151–158 (1971) Cook, S.: The complexity of theorem proving procedures. Proc. the third annual ACM symposium on Theory of computing, pp. 151–158 (1971)
23.
Zurück zum Zitat Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Compututer Computations, pp. 85–103. Plenum, New York (1972)CrossRef Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Compututer Computations, pp. 85–103. Plenum, New York (1972)CrossRef
24.
Zurück zum Zitat Vazirani, V.: Approximation algorithms. Springer, Berlin/Heidelberg (2001) Vazirani, V.: Approximation algorithms. Springer, Berlin/Heidelberg (2001)
25.
Zurück zum Zitat Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness, W. H. Freeman, pp. 190, problem GT2 (1979) Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness, W. H. Freeman, pp. 190, problem GT2 (1979)
26.
Zurück zum Zitat Berman, P., DasGupta, B., Sontag, E.: Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. Discret Appl Math 155(6–7), 733–749 (2007)CrossRefMATHMathSciNet Berman, P., DasGupta, B., Sontag, E.: Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. Discret Appl Math 155(6–7), 733–749 (2007)CrossRefMATHMathSciNet
Metadaten
Titel
On integer programming models for the multi-channel PMU placement problem and their solution
verfasst von
Neng Fan
Jean-Paul Watson
Publikationsdatum
01.03.2015
Verlag
Springer Berlin Heidelberg
Erschienen in
Energy Systems / Ausgabe 1/2015
Print ISSN: 1868-3967
Elektronische ISSN: 1868-3975
DOI
https://doi.org/10.1007/s12667-014-0132-6

Weitere Artikel der Ausgabe 1/2015

Energy Systems 1/2015 Zur Ausgabe