A Bicriteria Almost Equal Minimum Cost Flow Model for Day-Ahead Trading

As the share of renewable energy and therefore the fluctuation in power generation increases, using a battery to market the power saved/used by a flexible process becomes more and more important and attractive. The charging and discharging process of a battery can be modeled as a flow model in a time-expanded graph. We model the costs for this process as edge costs between nodes that correspond to consecutive points in time. An optimal battery strategy be obtained by computing a minimum cost flow in the given network. If the charging and discharging of a battery takes place as a coupled process of a production process, a steady and even charging and discharging is often important. In this paper, we describe a bicriteria flow model based on the Almost-Equal-Minimum Cost Flow Problem (AEMCFP) in which both trading profits and a steady flow of energy are considered as the two objectives. In the AEMCFP one is given additional sets of edges on which the flow values differ at most by a given constant. We obtain a strongly polynomial algorithm based on a parametric search approach. Furthermore, we present a case study for bidding on the German day ahead market.