Tailor your curves after your costume: Supply-following demand in smart grids through the Adwords problem

In deregulated energy markets, consumers-ranging from households to data centers-have access to multiple offers, often through multiple suppliers and energy carriers (i.e. electric, thermal) or through local generation, such as renewable energy sources and energy storage. Ideally, supply should match demand, leading to a balanced power grid, but this is challenging in practice: while some generation sources can be planned in advance (e.g. utility offers), others can be planned to a limited degree or cannot be planned altogether (e.g. storage and renewable energy sources respectively). In this context, we focus on how to address systematically this complex resource allocation problem in the presence of multiple actors. In this work, utilizing a proposed modeling of the energy dispatch problem as an online scheduling problem, we model supply-following demand in terms of the Adwords problem, in order to provide algorithmic solutions of measurable quality. Building on earlier work in the literature, we extend the Adwords problem to incorporate load credit (i.e. storage) and we present and analyze online algorithms that can schedule demand, given availability constraints on supply, with guaranteed competitive ratio. In systems where individual demands are small compared to supply, we prove a (1-1/e)-competitive ratio. We also extend the Adwords problem to utilize dynamic budgets, with application in cases where the above assumption does not hold, and present an algorithm with a 1 2-competitive ratio. We also provide examples of algorithmic performance in real world scenarios, by utilizing long term, fine-grained data from a pilot project in Sweden by a major utility company and in collaboration with the local government authority, while taking into account renewable generation on site