Modern exchange trading systems facilitate the market participants to electronically submit detailed information about their buy and sell preferences. With the help of so-called combinatorial orders, they can buy or sell several different items at once.

Tradable items are, for instance, company shares, futures contracts, electricity, or natural gas. The most basic combinatorial order is the fill-or-kill order in stock exchanges. This order is either executed entirely or not executed at all. That is, the participant either buys or sells all requested or offered items at once or none of them. Combinatorial orders are also available in electricity exchanges (e.g., block orders) and in futures exchanges (e.g., futures combination order).

An exchange usually determines a single price for each class of tradable items. For example, one price is determined for futures contracts of type A and a further price is determined for futures contracts of type B. In the absence of combinatorial orders, these prices can be determined separately. However, if participants submit combinatorial orders that comprise futures contracts of type A and B, then the prices must be determined simultaneously. This is necessary in order to make the prices for combinatorial orders consistent with the ones of the underlying futures contracts.

The first part of this work presents general modeling techniques and algorithms. For instance, we present a framework model for auctions in which the prices for several classes of items are determined simultaneously. Roughly speaking, we perform several auctions in parallel and integrate the combinatorial orders in such a way that they couple the parallel auctions among each other. For a certain class of combinatorial auctions this work provides model formulations that are solvable in polynomial time (e.g., the futures opening auction). For the general case, where the problem is NP-hard, we provide model formulations and algorithms which are fast enough such that they can be used in practice (e.g., in the European day-ahead electricity auction).

In the second part of this work, we present specific auction models for futures opening auctions, European day-ahead electricity auctions, and European natural gas auctions. Thereby we apply our general models and algorithms, go into problem specific details, and perform numerical tests on real-world instances.

Moderne Börsenhandelssysteme ermöglichen es den Marktteilnehmern, ihre Kauf- und Verkaufspräferenzen in detaillierter Form elektronisch zu übermitteln. Mit Hilfe von sogenannten kombinatorischen Geboten können beispielsweise mehrere verschiedene Güter simultan gekauft oder verkauft werden.

Handelbare Güter sind zum Beispiel Aktien, Futures-Kontrakte, Strom oder Erdgas. Das einfachste kombinatorische Gebot ist die sogenannte Fill-or-kill-Order an der Wertpapierbörse. Dieses Gebot wird entweder vollständig oder gar nicht ausgeführt. Das bedeutet, dass ein Teilnehmer entweder alle nachgefragten oder angebotenen Wertpapiere am Stück kauft oder verkauft, oder kein einziges. Kombinatorische Gebote werden auch an Strombörsen (z.B. das Blockgebot) und Terminbörsen (z.B. die Futures-Kombinationsorder) angeboten.

Normalerweise bestimmt eine Börse einen Preis für jede Klasse von handelbaren Gütern. Zum Beispiel wird ein Preis für Futures-Kontrakte vom Typ A und ein Preis für Futures-Kontrakte vom Typ B ermittelt. Falls keine kombinatorischen Gebote abgegeben wurden, dann sind die Preise voneinander unabhängig und können separat bestimmt werden. Falls jedoch kombinatorische Gebote abgegeben wurden, die sowohl Futures-Kontrakte vom Typ A als auch vom Typ B beinhalten, dann müssen die Preise simultan berechnet werden. Dies ist notwendig, damit die Preise für die kombinatorischen Gebote konsistent zu den Preisen der zugrundeliegenden Futures-Kontrakte sind.

Im ersten Teil dieser Arbeit stellen wir allgemeine Modellierungstechniken und Algorithmen vor. Unter anderem präsentieren wir allgemeine Rahmenmodelle für Auktionen, bei denen die Preise für mehrere Klassen von handelbaren Gütern simultan berechnet werden. Grob gesagt werden mehrere Auktionen parallel durchgeführt und dabei die kombinatorischen Gebote so eingebunden, so dass die Auktionen untereinander gekoppelt werden. Für bestimmte Klassen von kombinatorischen Auktionen präsentieren wir Modellformulierungen, die in polynomieller Zeit gelöst werden können (z.B. die Futures-Eröffnungsauktionen). Für den allgemeinen Fall, in dem das Auktionsproblem NP-schwer ist, stellen wir Modellformulierungen und Algorithmen vor, die schnell genug sind, um in der Praxis verwendet werden zu können (z.B. in europäischen day-ahead Strommarktauktionen).

Im zweiten Teil dieser Arbeit werden spezielle Auktionsmodelle für Futures-Eröffnungsauktionen, europäische day-ahead Stromauktionen und europäische Erdgasauktionen vorgestellt. Dabei wenden wir unsere allgemeinen Modelle und Algorithmen an, gehen auf problemspezifische Details ein und führen numerische Tests mit Probleminstanzen aus der Praxis durch.