TY - GEN A1 - Borndörfer, Ralf A1 - Buwaya, Julia A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - Network Spot Checking Games: Theory and Application to Toll Enforcing in Transportation Networks N2 - We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. In an SC game, the pure strategies of network users correspond to paths in a graph, and the pure strategies of the inspectors are subset of edges to be controlled. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways. T3 - ZIB-Report - 14-07 KW - Game Theory KW - Stackelberg Equilibrium KW - Security Games KW - Mixed Integer Programming KW - Price of Anarchy Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-47139 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Buwaya, Julia A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach N2 - We present a game-theoretic approach to optimize the strategies of toll enforcement on a motorway network. In contrast to previous approaches, we consider a network with an arbitrary topology, and we handle the fact that users may choose their Origin-Destination path; in particular they may take a detour to avoid sections with a high control rate. We show that a Nash equilibrium can be computed with an LP (although the game is not zero-sum), and we give a MIP for the computation of a Stackelberg equilibrium. Experimental results based on an application to the enforcement of a truck toll on German motorways are presented. T3 - ZIB-Report - 12-47 KW - Stackelberg Equilibrium KW - Game Theory KW - Mixed Integer Programming Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17401 SN - 1438-0064 ER - TY - GEN A1 - Fügenschuh, Armin A1 - van Veldhuizen, Roel A1 - Vierhaus, Ingmar T1 - Production Planning for Non-Cooperating Companies with Nonlinear Optimization N2 - We consider a production planning problem where two competing companies are selling their items on a common market. Moreover, the raw material used in the production is a limited non-renewable resource. The revenue per item sold depends on the total amount of items produced by both players. If they collaborate they could apply a production strategy that leads to the highest combined revenue. Usually the formation of such syndicates is prohibited by law; hence we assume that one company does not know how much the other company will produce. We formulate the problem for company A to find an optimal production plan without information on the strategy of company B as a nonlinear mathematical optimization problem. In its naive formulation the model is too large, making its solution practically impossible. After a reformulation we find a much smaller model, which we solve by spatial branch-and-cut methods and linear programming. We discuss the practical implications of our solutions. T3 - ZIB-Report - 13-25 KW - Non-Cooperative Two-Person Games; Mixed-Integer Nonlinear Optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18163 UR - http://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/4026 SN - 1438-0064 ER - TY - GEN A1 - Harks, Tobias T1 - Nash Equilibria in Online Sequential Routing Games N2 - In this paper, we study the efficiency of Nash equilibria for a sequence of nonatomic routing games. We assume that the games are played consecutively in time in an online fashion: by the time of playing game $i$, future games $i+1,\dots,n$ are not known, and, once players of game $i$ are in equilibrium, their corresponding strategies and costs remain fixed. Given a sequence of games, the cost for the sequence of Nash equilibria is defined as the sum of the cost of each game. We analyze the efficiency of a sequence of Nash equilibria in terms of competitive analysis arising in the online optimization field. Our main result states that the online algorithm $\sl {SeqNash}$ consisting of the sequence of Nash equilibria is $\frac{4n}{2+n}$-competitive for affine linear latency functions. For $n=1$, this result contains the bound on the price of anarchy of $\frac{4}{3}$ for affine linear latency functions of Roughgarden and Tardos [2002] as a special case. Furthermore, we analyze a problem variant with a modified cost function that reflects the total congestion cost, when all games have been played. In this case, we prove an upper bound of $\frac{4n}{2+n}$ on the competitive ratio of $\sl {SeqNash}$. We further prove a lower bound of $\frac{3n-2}{n}$ of $\sl {SeqNash}$ showing that for $n=2$ our upper bound is tight. T3 - ZIB-Report - 06-43 KW - Congestion Game KW - Online Optimization KW - Nash equilibria Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9376 ER - TY - THES A1 - Harks, Tobias T1 - Multicommodity Routing Problems-Selfish Behavior and Online Aspects- N2 - In this thesis, we study multicommodity routing problems in networks, in which commodities have to be routed from source to destination nodes. Such problems model for instance the traffic flows in street networks, data flows in the Internet, or production flows in factories. In most of these applications, the quality of a flow depends on load dependent cost functions on the edges of the given network. The total cost of a flow is usually defined as the sum of the arc cost of the network. An optimal flow minimizes this cost. A main focus of this thesis is to investigate online multicommodity routing problems in networks, in which commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes (fractionally) each commodity by minimizing a convex cost function that depends on the previously routed flow. We present a competitive analysis of this algorithm and prove upper bounds of (d+1)^(d+1) for polynomial price functions with nonnegative coefficients and maximum degree d. For networks with two nodes and parallel arcs, we show that this algorithm returns an optimal solution. Without restrictions on the price functions and network, no algorithm is competitive. We also investigate a variant in which the demands have to be routed unsplittably. In this case, it is NP-hard to compute the offline optimum. Furthermore, we study selfish routing problems (network games). In a network game, players route demand in a network with minimum cost. In this setting, we study the quality of Nash equilibria compared to the the system optimum (price of anarchy) in network games with nonatomic and atomic players and spittable flow. As a main result, we prove upper bounds on the price of anarchy for polynomial latency functions with nonnegative coefficients and maximum degree d, which improve upon the previous best ones. N2 - Diese Arbeit befasst sich mit Mehrgüterflussproblemen, in denen Güter mit einer bestimmten Rate durch ein gegebenes Netzwerk geleitet werden müssen. Mithilfe von Mehrgüterflussproblemen können zum Beispiel Verkehrsflüsse in Strassenverkehrsnetzen oder im Internet modelliert werden. In diesen Anwendungen wird die Effizienz von Routenzuweisungen für Güter durch lastabhängige Kostenfunktionen auf den Kanten eines gegebenen Netzwerks definiert. Die Gesamtkosten eines Mehrgüterflüsses sind durch die Summe der Kosten auf den Kanten definiert. Ein optimaler Mehrgüterfluss minimiert diese Gesamtkosten. Ein wesentlicher Bestandteil dieser Arbeit ist die Untersuchung sogenannter Online Algorithmen, die Routen für bekannte Güternachfragen berechnen, ohne vollständiges Wissen über zukünftige Güternachfragen zu haben. Es konnte ein Online Algorithmus gefunden werden, dessen Gesamtkosten für polynomielle Kostenfunktionen mit endlichem Grad nicht beliebig von denen einer optimalen Lösung abweichen. Für die Berechung einer optimalen Lösung müssen alle Güternachfragen a priori vorliegen. Dieses Gütekriterium gilt unabhängig von der gewählten Netzwerktopologie oder der Eingabesequenz von Gütern. Desweiteren befasst sich diese Arbeit mit der Effizienz egoistischer Routenwahl einzelner Nutzer verglichen zu einer optimalen Routenwahl. Egoistisches Verhalten von Nutzern kann mithilfe von nichtkooperativer Spieltheorie untersucht werden. Nutzer werden als strategisch agierende Spieler betrachtet, die ihren Profit maximieren. Als Standardwerkzeug zur Analyse solcher Spiele hat sich das Konzept des Nash Gleichgewichts bewährt. Das Nash Gleichweicht beschreibt eine stabile Strategieverteilung der Spieler, in der kein Spieler einen höheren Profit erzielen kann, wenn er einseitig seine Strategie ändert. Als Hauptergebnis dieser Arbeit konnte für polynomielle Kostenfunktionen mit endlichem Grad gezeigt werden, dass die Gesamtkosten eines Nash Gleichgewichts für sogennante atomare Spieler, die einen diskreten Anteil der gesamten Güternachfrage kontrollieren, nicht beliebig von den Gesamtkosten einer optimalen Lösung abweichen. In this thesis, we study multicommodity routing problems in networks, in which commodities have to be routed from source to destination nodes. Such problems model for instance the traffic flows in street networks, data flows in the Internet, or production flows in factories. In most of these applications, the quality of a flow depends on load dependent cost functions on the edges of the given network. The total cost of a flow is usually defined as the sum of the arc cost of the network. An optimal flow minimizes this cost. A main focus of this thesis is to investigate online multicommodity routing problems in networks, in which commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes (fractionally) each commodity by minimizing a convex cost function that depends on the previously routed flow. We present a competitive analysis of this algorithm and prove upper bounds of (d+1)^(d+1) for polynomial price functions with nonnegative coefficients and maximum degree d. For networks with two nodes and parallel arcs, we show that this algorithm returns an optimal solution. Without restrictions on the price functions and network, no algorithm is competitive. We also investigate a variant in which the demands have to be routed unsplittably. In this case, it is NP-hard to compute the offline optimum. Furthermore, we study selfish routing problems (network games). In a network game, players route demand in a network with minimum cost. In this setting, we study the quality of Nash equilibria compared to the the system optimum (price of anarchy) in network games with nonatomic and atomic players and spittable flow. As a main result, we prove upper bounds on the price of anarchy for polynomial latency functions with nonnegative coefficients and maximum degree d, which improve upon the previous best ones. KW - Mehrgueterflussprobleme KW - Online Optimierung KW - Algorithmische Spieltheorie. KW - Multicommodity Flow KW - Online Optimization KW - Algorithmic Game Theory Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10426 SN - 3867273596 ER - TY - GEN A1 - Hennig, Kai A1 - Schwarz, Robert T1 - Using Bilevel Optimization to find Severe Transport Situations in Gas Transmission Networks N2 - In the context of gas transmission in decoupled entry-exit systems, many approaches to determine the network capacity are based on the evaluation of realistic and severe transport situations. In this paper, we review the Reference Point Method, which is an algorithm used in practice to generate a set of scenarios using the so-called transport moment as a measure for severity. We introduce a new algorithm for finding severe transport situations that considers an actual routing of the flow through the network and is designed to handle issues arising from cyclic structures in a more dynamical manner. Further, in order to better approximate the physics of gas, an alternative, potential based flow formulation is proposed. The report concludes with a case study based on data from the benchmark library GasLib. T3 - ZIB-Report - 16-68 KW - bilevel optimization KW - gas networks KW - network flow Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61519 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - The Price of Spite in Spot-checking games N2 - We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways. T3 - ZIB-Report - 14-38 Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52775 SN - 1438-0064 ER - TY - GEN A1 - Scheumann, René A1 - Vierhaus, Ingmar A1 - Chang, Ya-Ju A1 - Fügenschuh, Armin A1 - Finkbeiner, Matthias T1 - Identification of trade-offs for sustainable manufacturing of a Bamboo Bike by System Dynamics N2 - We develop a generic System Dynamic model to simulate the production, machines, employees, waste, and capital flows of a manufacturing company. In a second step, this model is specialised by defining suit-able input data to represent a bicycle manufacturing company in a developing country. We monitor a set of sustainability indicators to understand the social, environmental and economic impact of the company, and to estimate managerial decisions to be taken in order to improve on these criteria. We show that the social and environmental situation can be improved over time without sacrificing the economic success of the company's business. T3 - ZIB-Report - 13-32 KW - System Dynamics KW - Modelling KW - Life Cycle Sustainability Assessment KW - Sustainability Indicators Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18895 ER - TY - GEN A1 - Vierhaus, Ingmar A1 - Fügenschuh, Armin A1 - Gottwald, Robert Lion A1 - Grösser, Stefan N. T1 - Modern Nonlinear Optimization Techniques for an Optimal Control of System Dynamics Models N2 - We study System Dynamics models with several free parameters that can be altered by the user. We assume that the user's goal is to achieve a certain dynamic behavior of the model by varying these parameters. In order to the find best possible combination of parameter settings, several automatic parameter tuning methods are described in the literature and readily available within existing System Dynamic software packages. We give a survey on the available techniques in the market and describe their theoretical background. Some of these methods are already six decades old, and meanwhile newer and more powerful optimization methods have emerged in the mathematical literature. One major obstacle for their direct use are tabled data in System Dynamics models, which are usually interpreted as piecewise linear functions. However, modern optimization methods usually require smooth functions which are twice continuously differentiable. We overcome this problem by a smooth spline interpolation of the tabled data. We use a test set of three complex System Dynamic models from the literature, describe their individual transition into optimization problems, and demonstrate the applicability of modern optimization algorithms to these System Dynamics Optimization problems. T3 - ZIB-Report - 14-08 KW - System Dynamics KW - Optimal Control KW - Nonlinear Optimization KW - Spline Interpolation Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-48159 SN - 1438-0064 ER -