Document Open Access Logo

Online Energy Storage Management: an Algorithmic Approach

Authors Anthony Kim, Vahid Liaghat, Junjie Qin, Amin Saberi

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.12.pdf
  • Filesize: 0.61 MB
  • 23 pages

Document Identifiers

Author Details

Anthony Kim
Vahid Liaghat
Junjie Qin
Amin Saberi

Cite As Get BibTex

Anthony Kim, Vahid Liaghat, Junjie Qin, and Amin Saberi. Online Energy Storage Management: an Algorithmic Approach. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 12:1-12:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.12

Abstract

Motivated by the importance of energy storage networks in smart grids, we provide an algorithmic study of the online energy storage management problem in a network setting, the first to the best of our knowledge. Given online power supplies, either entirely renewable supplies or those in combination with traditional supplies, we want to route power from the supplies to demands  using storage units subject to a decay factor. Our goal is to maximize the total utility of satisfied demands less the total production cost of routed power. We model renewable supplies with the zero production cost function and traditional supplies with convex production cost functions. For two natural storage unit settings, private and public, we design poly-logarithmic competitive algorithms in the network flow model using the dual fitting and online primal dual methods for convex problems. Furthermore, we show strong hardness results for more general settings of the problem. Our techniques may be of independent interest in other routing and storage management problems.

Subject Classification

Keywords
  • Online Algorithms
  • Competitive Analysis
  • Routing
  • Storage
  • Approximation Algorithms
  • Power Control

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rajeev Alur, Sampath Kannan, Kevin Tian, and Yifei Yuan. On the complexity of shortest path problems on discounted cost graphs. In Proceedings of the 7th International Conference on Language and Automata Theory and Applications, LATA'13, pages 44-55, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. URL: http://dx.doi.org/10.1007/978-3-642-37064-9_6.
  2. James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, and Orli Waarts. On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM, 44(3):486-504, May 1997. URL: http://dx.doi.org/10.1145/258128.258201.
  3. B. Awerbuch, Y. Azar, and S. Plotkin. Throughput-competitive online routing. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, FOCS'93, pages 32-40, 1993. Google Scholar
  4. Yossi Azar, Ilan Reuven Cohen, and Debmalya Panigrahi. Online covering with convex objectives and applications. arXiv:1412.3507, Dec 2014. URL: http://arxiv.org/abs/1412.3507.
  5. Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, and Kunal Talwar. Secretary problems: Weights and discounts. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'09, pages 1245-1254, Philadelphia, PA, USA, 2009. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1496770.1496905.
  6. M.E. Baran and F.F. Wu. Network reconfiguration in distribution systems for loss reduction and load balancing. IEEE Transactions on Power Delivery, 4(2):1401-1407, apr 1989. URL: http://dx.doi.org/10.1109/61.25627.
  7. Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jeż, Dorian Nogneng, and Jiří Sgall. Better approximation bounds for the joint replenishment problem. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'14, pages 42-54. SIAM, 2014. URL: http://dl.acm.org/citation.cfm?id=2634074.2634078.
  8. E. Bitar, R. Rajagopal, P. Khargonekar, and K. Poolla. The Role of Co-Located Storage for Wind Power Producers in Conventional Electricity Markets. In Proc. of American Control Conference (ACC), pages 3886-3891, 2011. Google Scholar
  9. E. Bitar and Yunjian Xu. On incentive compatibility of deadline differentiated pricing for deferrable demand. In Decision and Control (CDC), 2013 IEEE 52nd Annual Conference on, pages 5620-5627, Dec 2013. URL: http://dx.doi.org/10.1109/CDC.2013.6760775.
  10. N. Buchbinder, T. Kimbrelt, R. Levi, K. Makarychev, and M. Sviridenko. Online make-to-order joint replenishment model: Primal dual competitive algorithms. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'08, pages 952-961, Philadelphia, PA, USA, 2008. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1347082.1347186.
  11. Niv Buchbinder, Shahar Chen, Anupam Gupta, Viswanath Nagarajan, and Joseph (Seffi) Naor. Online convex covering and packing problems. arXiv:1412.8347, Dec 2014. URL: http://arxiv.org/abs/1412.8347.
  12. Niv Buchbinder and Joseph (Seffi) Naor. Improved bounds for online routing and packing via a primal-dual approach. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS'06, pages 293-304, Washington, DC, USA, 2006. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2006.39.
  13. California Independent System Operator. Annual Report on Market Issues and Performance, 2014. URL: http://www.caiso.com/Documents/2014AnnualReport_MarketIssues_Performance.pdf.
  14. T-H. Hubert Chan, Zhiyi Huang, and Ning Kang. Online convex covering and packing problems. arXiv:1502.01802, Apr 2015. URL: http://arxiv.org/abs/1502.01802.
  15. Chi-Kin Chau, Guanglin Zhang, and Minghua Chen. Cost Minimizing Online Algorithms for Energy Storage Management with Worst-case Guarantee. IEEE Transactions on Smart Grid, nov 2015. URL: http://arxiv.org/abs/1511.07559,
  16. In-Koo Cho. Competitive equilibrium in a radial network. RAND Journal of Economics, pages 438-460, 2003. Google Scholar
  17. Paul Denholm, Erik Ela, Brendan Kirby, and Michael Milligan. The role of energy storage with renewable electricity generation. Technical Report NREL/TP-6A2-47187, National Renewable Energy Laboratory, January 2010. Google Scholar
  18. Nikhil R. Devanur and Kamal Jain. Online matching with concave returns. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC'12, pages 137-144, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2213977.2213992.
  19. European Commission. Energy Roadmap 2050, 2011. URL: https://ec.europa.eu/energy/en/topics/energy-strategy/2050-energy-strategy.
  20. J Duncan Glover, Mulukutla Sarma, and Thomas Overbye. Power System Analysis &Design, Fifth Edition. Cengage Learning, 2012. Google Scholar
  21. L. Huang, J. Walrand, and K. Ramchandran. Optimal Demand Response with Energy Storage Management. In Proc. of IEEE Third International Conference on Smart Grid Communications (SmartGridComm), pages 61-66, 2012. URL: http://dx.doi.org/10.1109/SmartGridComm.2012.6485960.
  22. Zhiyi Huang and Anthony Kim. Welfare maximization with production costs: A primal dual approach. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'15, pages 59-72. SIAM, 2015. URL: http://dl.acm.org/citation.cfm?id=2722129.2722135.
  23. Mark Z. Jacobson, Mark A. Delucchi, Guillaume Bazouin, Zack A. F. Bauer, Christa C. Heavey, Emma Fisher, Sean B. Morris, Diniana J. Y. Piekutowski, Taylor A. Vencill, and Tim W. Yeskoo. 100% clean and renewable wind, water, and sunlight (WWS) all-sector energy roadmaps for the 50 United States. Energy Environ. Sci., 8(7):2093-2117, Jul 2015. URL: http://dx.doi.org/10.1039/C5EE01283J.
  24. Thomas Kesselheim, Robert Kleinberg, and Eva Tardos. Smooth online mechanisms: A game-theoretic problem in renewable energy markets. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC'15, pages 203-220, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2764468.2764487.
  25. Frank Kreikebaum, Debrup Das, Yi Yang, Frank Lambert, and Deepak Divan. Smart Wires — A distributed, low-cost solution for controlling power flows and monitoring transmission lines. In 2010 IEEE PES Innovative Smart Grid Technologies Conference Europe (ISGT Europe), pages 1-8. IEEE, oct 2010. URL: http://dx.doi.org/10.1109/ISGTEUROPE.2010.5638853.
  26. Retsef Levi, Robin O. Roundy, and David B. Shmoys. Primal-dual algorithms for deterministic inventory problems. Math. Oper. Res., 31(2):267-284, February 2006. URL: http://dx.doi.org/10.1287/moor.1050.0178.
  27. David Lindley. The energy storage problem. Nature, 463(7), January 2010. Google Scholar
  28. S. H. Low. Convex Relaxation of Optimal Power Flow, Part I: Formulations and Equivalence. ArXiv e-prints, May 2014. URL: http://arxiv.org/abs/1405.0766.
  29. S. H. Low. Convex Relaxation of Optimal Power Flow, Part II: Exactness. ArXiv e-prints, May 2014. URL: http://arxiv.org/abs/1405.0766.
  30. Lian Lu, Jinlong Tu, Chi-Kin Chau, Minghua Chen, and Xiaojun Lin. Online energy generation scheduling for microgrids with intermittent energy sources and co-generation. ACM SIGMETRICS Performance Evaluation Review, 41(1):53, jun 2013. URL: http://dl.acm.org/citation.cfm?id=2494232.2465551, URL: http://dx.doi.org/10.1145/2494232.2465551.
  31. Viswanath Nagarajan and Cong Shi. Approximation algorithms for inventory problems with submodular or routing costs. arXiv:1504.06560, April 2015. URL: http://arxiv.org/abs/1504.06560.
  32. National Renewable Energy Laboratory. The Value of Energy Storage for Grid Applications, 2013. URL: http://www.nrel.gov/docs/fy13osti/58465.pdf.
  33. Julia Pahl and Stefan Voß. Integrating deterioration and lifetime constraints in production and supply chain planning: A survey. European Journal of Operational Research, 238(3):654-674, 2014. URL: http://dx.doi.org/10.1016/j.ejor.2014.01.060.
  34. J. Qin, R. Sevlian, D. Varodayan, and R. Rajagopal. Optimal Electric Energy Storage Operation. In Proc. of IEEE Power and Energy Society General Meeting, pages 1-6, 2012. URL: http://dx.doi.org/10.1109/PESGM.2012.6345242.
  35. J. Qin, H. I. Su, and R. Rajagopal. Storage in Risk Limiting Dispatch: Control and Approximation. In Proc. of American Control Conference (ACC), pages 4202-4208, 2013. Google Scholar
  36. Junjie Qin, Yinlam Chow, Jiyan Yang, and Ram Rajagopal. Distributed Online Modified Greedy Algorithm for Networked Storage Operation under Uncertainty. Smart Grid, IEEE Transactions on, PP(99):1, jun 2014. URL: http://arxiv.org/abs/1406.4615, http://arxiv.org/abs/1406.4615, URL: http://dx.doi.org/10.1109/TSG.2015.2422780.
  37. SB-350 Clean Energy and Pollution Reduction Act of 2015, 2015. URL: https://leginfo.legislature.ca.gov/faces/billNavClient.xhtml?bill_id=201520160SB350.
  38. Brian Stott, Jorge Jardim, and Ongun Alsaç. Dc power flow revisited. Power Systems, IEEE Transactions on, 24(3):1290-1300, 2009. Google Scholar
  39. H. I. Su and A. El Gamal. Modeling and Analysis of the Role of Energy Storage for Renewable Integration: Power Balancing. IEEE Transactions on Power Systems, 28(4):4109-4117, 2013. URL: http://dx.doi.org/10.1109/TPWRS.2013.2266667.
  40. Kevin D. Wayne. Generalized maximum flow algorithms. PhD thesis, Cornell University, 1999. Google Scholar
  41. L. Xie, Y. Gu, A. Eskandari, and M. Ehsani. Fast MPC-Based Coordination of Wind Power and Battery Energy Storage Systems. Journal of Energy Engineering, 138(2):43-53, 2012. URL: http://dx.doi.org/10.1061/(ASCE)EY.1943-7897.0000071.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact