For both computer networks and cyber-physical systems, the problem inputs are often time-varying, and the decisions much be constantly updated to match the changing inputs. However, making changes to decisions usually incur significant additional cost. For example, changing the placement and sizing of virtualized functions in network function virtualization (NFV) can disrupt the processing of the network traffic. Similarly, there are limits on how fast the power output of large electricity generators can change. Thus, one often faces a challenging tradeoff between a decision that is best for the current input and a decision that can work well for future inputs. These problems thus call for the careful design of ``online algorithms,'' which make decisions based only on currently available inputs, but can also do well under future uncertainty. Our group has made advances for online algorithms in several thrusts.
We have studied competitive online algorithms in a micro-grid setting for managing uncertainty both in the flexible demand and in the renewable supply. There are two key novelties. First, note that online algorithms in the typical CS literature often assume absolutely no information about the future. As a result, although they may be shown to attain the smallest possible worst-case competitive ratio compared to the offline solution, in power systems such competitive results are often quite pessimistic because they fail to exploit any partial future information. In contrast, we proposed new models to capture partial future information through (possibly inaccurate) forecasts, and we developed a powerful computational approach that can produce online algorithms with greatly-improved competitive ratios. Second, a common dilemma for online algorithm design is that online algorithms with good competitive ratios may exhibit poor average-case performance. we developed a novel ``Algorithm robustification'' procedure that can take any online algorithm with reasonable average-case performance, and convert it into one with both the optimal competitive ratio and good average-case performance.
Selected publications:
Selected publications:
We have also studied robust and efficient control at the Independent System Operator (ISO) and the utility-company levels. Here, the stake is even higher because the power grid in an entire area may be jeopardized if any of the physical constraints in the system are not met. Our work below has jointly considered both the reliability assessment commitment (RAC) and the real-time dispatch problems for an ISO. We developed ``maximally robust algorithms'' that can provably ensure grid safety, whenever there exists any other algorithm that can ensure grid safety under a given level of future uncertainty. Our on-going work will study how to attain similar types of robustness guarantees under more sophisticated settings with energy storage, demand response, and market/incentive mechanisms.
Selected publications: