Combinatorial Optimization for Smart Power Grids

Rapid penetration of renewable energy based Distributed Energy Resources (DER) has the potential to exacerbate the challenges inherent in grid frequency and voltage regulation. However, their real time controllability can be leveraged to not only mitigate such challenges, but improve the economics and quality of grid operations.

A plethora of scheduling algorithms have been developed for fast and efficient scheduling of these renewable energy based Distributed Energy Resources (DER). These algorithms schedule the complex - real and reactive power injected into (or drawn from) the grid by the DERs under various cost objective functions and grid constraints. However, a vast majority of such algorithms assume the feasible range of power injections to be continuous. In reality, the control options available for several DERs form a discrete space. This implies that the feasible range of power injections also forms a discrete space. This makes DER scheduling an NP-hard problem. Integer/Mixed Integer program based algorithms, which guarantee optimality in the objective value, have been developed. But these are prohibitively expensive in terms of computational time requirements. On the other hand, fast heuristic based solutions have also been developed. But as they do not provide any guarantee on the optimality of the objective, or on satisfying the constraints, they are unreliable for grid operations.

The objective of this research is to develop polynomial runtime complexity approximation algorithms to perform cost optimal supply demand matching in smart grids targeting various objective functions and constraints such as cost minimization, fairness, network constraints etc. Using both theoretical analysis and practical evaluations, we show that our supply demand matching algorithms provide solutions which are close to optimal in a small amount of time.

Approximation Algorithm Techniques used: Dynamic Programming Rounding based FPTAS, Greedy Sub-modularity based algorithm, Linear Programming Rounding based Constant Factor Approximation Algorithm, Two-state stochastic optimization based approximation algorithm

Publications

  • Sanmukh R. Kuppannagari, Rajgopal Kannan and Viktor K. Prasanna, Approximate Scheduling of DERs with Discrete Complex Injections, Tenth ACM International Conference on Future Energy Systems (ACM e-Energy), June 2019.
  • Ajitesh Srivastava, Sanmukh R. Kuppannagari, Rajgopal Kannan and Viktor K. Prasanna, Minimizing Cost of Smart Grid Operations by Scheduling Mobile Energy Storage Systems, IEEE Letters of the Computer Society, 2019
  • Athanasios A. Rompokos, Sanmukh R. Kuppannagari, Dominik Engel and Viktor K. Prasanna, Minimizing Cost of Load Matching in Multiple Micro-Grids Using MESS, 6th IEEE Conference on Technologies for Sustainability, November 2018.
  • Sanmukh R. Kuppannagari, Rajgopal Kannan and Viktor K. Prasanna, Optimal Discrete Net Load Balancing in Smart Grids with High PV Penetration, ACM Transactions on Sensor Networks (TOSN) 14.3-4 (2018): 24, 2018.
  • Sanmukh R. Kuppannagari, Rajgopal Kannan and Viktor K. Prasanna, Risk Aware Net Load Bal- ancing in Micro Grids with High DER Penetration, The Ninth Conference on Innovative Smart Grid Technology (ISGT 2018), February 2018.
  • Sanmukh R. Kuppannagari, Rajgopal Kannan and Viktor K. Prasanna, NO-LESS: Near OptimaL CurtailmEnt Strategy Selection for Net Load Balancing in Micro Grids, The Ninth Conference on Innovative Smart Grid Technology (ISGT 2018), February 2018.
  • Sanmukh R. Kuppannagari, Rajgopal Kannan and Viktor K. Prasanna, Optimal Net Load Balancing in Smart Grids with High PV Penetration, The 4th ACM International Conference on Systems for Energy-Efficient Built Environments (BuildSys 2017), November 2017.
  • Sanmukh R. Kuppannagari, Rajgopal Kannan, Charalampos Chelmis and Viktor K. Prasanna, Imple- mentation of Learning-Based Dynamic Demand Response on a Campus Micro-grid, 25th International Joint Conference on Artificial Intelligence, IJCAI-16 Demo Track, July 2016.
  • Sanmukh R. Kuppannagari, Rajgopal Kannan, Charalampos Chelmis, Arash S. Tehrani, and Viktor K. Prasanna, Optimal Customer Targeting for Sustainable Demand Response in Smart Grids, Interna- tional Conference on Computational Science, 2016.
  • Sanmukh R. Kuppannagari, Rajgopal Kannan and Viktor K. Prasanna, An ILP based Algorithm for Optimal Customer Selection for Demand Response in SmartGrids, 2015 International Symposium on Big Data and Data Science (CSCI-ISBD), December 2015.