publications and preprints

A unified approach to inverse robust optimization problems

A variety of approaches has been developed to deal with uncertain optimization problems. Often, they start with a given set of uncertainties and then try to minimize the influence of these uncertainties. The reverse view is to first set a budget for the price one is willing to pay and then find the most robust solution. In this article, we aim to unify these inverse approaches to robustness. We provide a general problem definition and a proof of the existence of its solution. We study properties of this solution such as closedness, convexity, and boundedness. We also provide a comparison with existing robustness concepts such as the stability radius, the resilience radius, and the robust feasibility radius. We show that the general definition unifies these approaches. We conclude with an example that demonstrates the flexibility of the introduced concept.

Berthold, H., Heller, T., Seidel, T. (2024)

Link to article (journal): Mathematical Methods of Operations Research

robust optimization, inverse optimization, inverse robust optimization, robustness, concepts

Algorithms and complexity for the almost equal maximum flow problem

In the equal maximum flow problem (EMFP), we aim for a maximum flow where we require the same flow value on all arcs in some given subsets of the arc set, so called homologous arc sets. In this article, we study the closely related almost equal maximum flow problems (AEMFP) where the flow values on arcs of one homologous arc set differ at most by the valuation of a so called deviation function. We prove that the integer AEMFP is in general NP-complete, and show that even the problem of finding a fractional maximum flow in the case of convex deviation functions is also NP-complete. This is in contrast to the EMFP, which is polynomial time solvable in the fractional case. Additionally, we provide inapproximability results for the integral AEMFP. For the (fractional) concave AEMFP we state a strongly polynomial algorithm for the linear and concave piecewise polynomial deviation function case for a fixed number of homologous sets using a parametric search approach.

Haese, R., Heller, T., Krumke, S.O. (2024)

Link to article (journal): Networks

maximum flow, complexity, network flows, equal maximum flow problem, almost equal maximum flow problem

Optimizing the marketing of flexibility for a virtual battery in day-ahead and balancing markets: A rolling horizon case study

Industrial electricity consumers with flexible demand can profit from adjusting their load to short-term prices or by providing balancing services to the grid. Markets which support this kind of short-term position adjustment are the day-ahead market and balancing markets. We propose a formulation for a combined optimization model that computes an optimal distribution of flexibility between the balancing and day-ahead markets. The optimal solution also includes the specific bids for the day-ahead and balancing markets. Besides the expected profits of each market and their different rules for bidding, our model also takes their different roles in a continuous marketing of flexibility into account. To prevent overrating short-term profits we introduce a variable penalty term that adds a cost to unfavorable load schedules. We evaluate the optimization model in a rolling horizon case study based on the setting of a virtual battery at TRIMET Aluminum SE, which is derived from a flexible aluminum electrolysis process. For such a battery we compute a daily optimal split of flexibility and trading decisions based on data in the period 04/2021–03/2022. We show that the optimal split is more profitable than using only one market or a fixed split between the markets.

Finhold, E., Gärtner, C., Grindel, R., Heller, T., Leithäuser, N., Röger, E., Schirra, F. (2023)

Link to article (journal): Applied Energy

optimization, flexibility, virtual battery, day-ahead market, balancing market

p-median location interdiction on trees

In p-median location interdiction the aim is to find a subset of edges in a graph, such that the objective value of the p-median problem in the same graph without the selected edges is as large as possible. We prove that this problem is NP-hard even on acyclic graphs. Restricting the problem to trees with unit lengths on the edges, unit interdiction costs, and a single edge interdiction, we provide an algorithm which solves the problem in polynomial time. Furthermore, we investigate path graphs with unit and arbitrary lengths. For the former case, we present an algorithm, where multiple edges can get interdicted. Furthermore, for the latter case, we present a method to compute an optimal solution for one interdiction step which can also be extended to multiple interdicted edges.

Leiß, L., Heller, T., Schäfer, L.E., Streicher, M., Ruzika, S. (2023)

Link to article (journal): Arxiv Preprint

p-median location problem, location interdiction problem, tree graphs, polynomial time algorithm

On the potential of arbitrage trading on the German intraday power market

Pair trading on the German intraday power market is a commonly used risk-averse, heuristic trading strategy. However, due to myopic decision-making and a lack of foresight, the profit obtained is far from optimal. By comparing this strategy with the ex post optimal solution (ie, a strategy with perfect foresight), we show on a set of 15 selected days from 2020 to 2022 that the predictive information lets us generate on average more than five times as much profit by excessively buying and selling the same contracts for a trading interval of five minutes. Another problem with pair trading in practice is the possibility of unbalanced auction wins. We show that an unbiased loss of up to 10% has a negligible impact on the obtained profit. In contrast, we also show the value of frequent optimization updates by simulating strategies with only sporadic participation in the market. While this is hardly beneficial for the pair trading strategy, the ex post optimal profit increases on average by 30% when the time between two trades is halved.

Finhold, E., Heller, T., Leithäuser, N. (2023)

Link to article (journal): Journal of Energy Markets

arbitrage trading, intraday power market, pair trading, ex post optimal solution

A Heuristic Bicriteria Scheduling Approach for a Flooring Production Planning Problem

We consider a scheduling problem motivated by a particular process step in the production of rubber flooring. In this step, a set of given jobs of different colors has to pass through a heated pressure roller, one job at a time. Since different jobs require different process temperatures, and heating up the machine is expensive, we want to minimize the total temperature change. On the other hand, we aim at minimizing the alternations between bright and dark colors to minimize cleaning effort. We provide an efficient heuristic for finding all job sequences that are Pareto optimal with respect to the two objectives.

Leib, D., Finhold, E., Heller, T. (2022)

Link to article (journal): Lecture Notes in Operations Research

single machine scheduling, flooring production planning, heuristic bicriteria approach

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.

Finhold, E., Heller, T., Krumke, S.O., Leithäuser, N. (2022)

Link to article (journal): Lecture Notes in Operations Research

minimum cost flow, day-ahead trading, bicriteria optimization, almost equal flow

Considering Short and Long Term Fairness in Recurrent Auctions with an Application to Collaborative Rostering

Collaborative duty rostering can increase the satisfaction of employees in healthcare. For the acceptance of a final rostering, a fair selection of included wishes is essential. As in rostering problems various constraints must be respected, it is generally not possible to accept all bids (wishes for a single free time slot) in a planning period and fairness is important. In this paper we present a weighted Vickrey-Clarke-Groves (VCG) mechanism approach where past auction results are incorporated by a fairness factor and where the underlying winner determination problem is given by a hitting set problem (HSP). We present numerical results of simulation runs over several planning periods.

Heller, T., Velten, S. (2022)

Link to article (journal): Lecture Notes in Operations Research

recurrent auctions, collaborative rostering, weighted Vickrey-Clarke-Groves mechanism, hitting set problem

On Reward-Penalty-Selection Games

The Reward-Penalty-Selection Problem (RPSP) can be seen as a combination of the Set Cover Problem (SCP) and the Hitting Set Problem (HSP). Given a set of elements, a set of reward sets, and a set of penalty sets, one tries to find a subset of elements such that as many reward sets as possible are covered, i.e. all elements are contained in the subset, and at the same time as few penalty sets as possible are hit, i.e. the intersection of the subset with the penalty set is non-empty. In this paper we define a cooperative game based on the RPSP where the elements of the RPSP are the players. We prove structural results and show that RPS games are convex, superadditive and totally balanced. Furthermore, the Shapley value can be computed in polynomial time. In addition to that, we provide a characterization of the core elements as a feasible flow in a network graph depending on the instance of the underlying RPSP. By using this characterization, a core element can be computed efficiently.

Gräf, N., Heller, T., Krumke, S.O. (2022)

Link to article (journal): Arxiv Preprint

reward-penalty-selection problem, cooperative game, convex game, superadditive game, totally balanced game, Shapley value, core elements

An Optimal Bidding Model to Market Flexibility on the Balancing Electricity Markets

In order to stabilize short-term fluctuations in the network frequency, flexibility is offered on balancing electricity markets. With the reformation of the German balancing markets and the opportunity to market secondary balancing energy independently of capacity, short-term flexibilities can now be traded more easily. In this paper, we describe a robust optimization problem for marketing balancing power in these markets. Starting from forecasts on acceptance probabilities and activation durations estimated from historical values, we compute price-quantity pairs that define bids placed on the reserve markets. We present a backtesting study over the period 04/2021 to 11/2021 and, thus, evaluate the potential of flexibility marketing on the secondary control markets.

Gärtner, C., Röger, E., Heller, T. (2022)

Link to article (journal): Energy

balancing electricity markets, flexibility marketing, robust optimization

Optimal trading of flexible power consumption on the day-ahead market

As power generators shift from inert power plants to more volatile renewable sources of electricity, variable loads allow energy intensive businesses to monetize their flexibility in the electricity market. In the aluminum industry, engineering innovations have enabled such flexibility. A virtual battery can balance changing power inflows over a period of a few days. We have modeled the optimization problem of when and how to use this flexibility on the day-ahead energy market based on hourly price forecasts as a linear program. Besides the expected revenue, we also consider technical costs which occur in an unsteady energy schedule. In order to account for realistic trading settings, we embed the optimization problem in a daily rolling horizon planning framework. In this work, we generalize the specific planning problem to a broader range of applications and analyze the main influences on a profitable trading strategy. For a typical parametrization, we present a constructive heuristic that does not require an LP-Solver.

Leithäuser, N., Heller, T., Finhold, E., Schirra, F. (2021)

Link to article (journal): Lecture Notes in Operations Research

day-ahead market, flexibility trading, linear programming, rolling horizon planning

The Reward-Penalty-Selection Problem

The Set Cover Problem (SCP) and the Hitting Set Problem (HSP) are well-studied optimization problems. In this paper we introduce the Reward-Penalty-Selection Problem (RPSP) which can be understood as a combination of the SCP and the HSP where the objectives of both problems are contrary to each other. Applications of the RPSP can be found in the context of combinatorial exchanges in order to solve the corresponding winner determination problem. We give complexity results for the minimization and the maximization problem as well as for several variants with additional restrictions. Further, we provide an algorithm that runs in polynomial time for the special case of laminar sets and a dynamic programming approach for the case where the instance can be represented by a tree or a graph with bounded tree-width. We further present a graph theoretical generalization of this problem and results regarding its complexity.

Heller, T., Krumke, S.O., Küfer, K.-H. (2021)

Link to article (journal): Arxiv Preprint

set cover problem, hitting set problem, complexity results, polynomial time algorithm, dynamic programming

2.5-Connectivity: Unique Components, Critical Graphs, and Applications

If a biconnected graph stays connected after the removal of an arbitrary vertex and an arbitrary edge, then it is called 2.5-connected. We prove that every biconnected graph has a canonical decomposition into 2.5-connected components. These components are arranged in a tree-structure. We also discuss the connection between 2.5-connected components and triconnected components and use this to present a linear time algorithm which computes the 2.5-connected components of a graph. We show that every critical 2.5-connected graph other than K4 can be obtained from critical 2.5-connected graphs of smaller order using simple graph operations. Furthermore, we demonstrate applications of 2.5-connected components in the context of cycle decompositions and cycle packings.

Heinrich, I., Heller, T., Schmidt, E., Streicher, M. (2020)

Link to article (journal): Lecture Notes in Computer Science

graph theory, 2.5-connectivity, unique components, critical graphs