 |
|
||||||||||
Ph.D. Theses
IFOR Events
Seminar:
'Optimization & Applications' (see information & program)
Feb 18 - May 27, 2013
Structural Robustness in Combinatorial Optimization
| Abstract | David Adjiashvili |
|
The need to model the presence of uncertainty in systematic decision making situations has sprung the development of two main fields in optimization theory, stochastic optimization and robust optimization. Stochastic optimization models the uncertainty underlying the input data using probability distributions, and asks to optimize a certain stochastic quantity, such as the expected value. The main shortcomings of stochastic optimization is the need to assume certain stochastic knowledge about the possible realizations of input data, as well as the implicit assumption that the optimization needs to be performed many times, in order for the optimized stochastic quantity to be meaningful. On the other hand, robust optimization assumes the presence of an adversary that controls the materialized input data, and chooses it so as to minimize the decision makers' utility. This approach does away with the aforementioned shortcomings, but it has one of its own. In particular, robust optimization often gives overly conservative solutions. In many situations, however, this level of conservatism is appropriate, while in other situations it can be regulated. In a nutshell, this thesis studies robust combinatorial optimization problems. In its heart is a study of several new robust counterparts for combinatorial problems. Unlike many existing such models, which model uncertainty in the form of unknown costs of resources, our models try to capture the uncertainty present in the underlying combinatorial structure. In other words, the present thesis studies the effect of structural uncertainty on classical combinatorial optimization problems. Concretely, we assume that an adversary is able to remove a certain subset of resources, such as edges in a graph, after the nominal solution was chosen. The nominal solution is feasible if for any materialization of an admissible failure scenario, the required structural property of the solution (e.g. containing an s-t path, or comprising a connected graph) is maintained. More... |
Logical Interaction Networks in Biology: Theory and Application
| Author | Kathrin Ballerstein |
| Abstract |
This thesis deals with a general modeling framework for large-scale biological systems which is, on the one hand, applied to various practical instances, and on the other hand, strictly formalized and mathematically analyzed with respect to its complexity and structure. For the biological application initially an overview of existing analytic methods for biological systems is presented, and the proposed modeling framework is classified in this context. The framework is based on logical implication formulas. It allows for the verification of a biological model, the prediction of its response to prescribed stimuli, as well as the identification of possible intervention strategies for diseases or failure modes. This basic model is afterwards extended into two directions: First, timing information of reactions in the biological unit are incorporated. This generalization additionally enables to detect possible unknown timing information or inconsistencies that arise due to modeling errors. Besides this, it provides a method to consistently integrate the logical models of related biological units into one model. Second, the purely binary basic framework is enhanced by including a fine discretization of a biological component's activity level. This permits to express different effects depending on different levels of activity of one component, and therefore the predictions of the model become more sophisticated. More... |
First-Order Methods in Large-Scale Semidefinite Optimization
| Author | Michael Bürgisser |
| Abstract |
Semidefinite Optimization has attracted the attention of many researchers over the last twenty years. It has nowadays a huge variety of applications in such different fields as Control, Structural Design, Statistics, or in the relaxation of hard combinatorial problems. In this thesis, we focus on the practical tractability of large-scale semidefinite optimization problems. From a theoretical point of view, these problems can be solved by polynomial-time Interior-Point methods approximately. The complexity estimate of Interior-Point methods grows logarithmically in the inverse of the solution accuracy, but with the order 3.5 in both the matrix size and the number of constraints. The later property prohibits the resolution of large-scale problems in practice. In this thesis, we present new approaches based on advanced First-Order methods such as Smoothing Techniques and Mirror-Prox algorithms for solving structured large-scale semidefinite optimization problems up to a moderate accuracy. These methods require a very specific problem format. However, generic semidefinite optimization problems do not comply with these requirements. In a preliminary step, we recast slightly structured semidefinite optimization problems in an alternative form to which these methods are applicable, namely as matrix saddle-point problems. The final methods have a complexity result that depends linearly in both the number of constraints and the inverse of the target accuracy. More... |
Algorithms for railway traffic management in complex central station areas
| Author |
Martin Fuchsberger |
| Abstract |
This thesis addresses the problem of managing dense railway traffic in a complex central station area by providing ongoing decision support to the dispatcher. For this purpose a closed-loop discrete-time control framework is developed, in which a model predictive controller provides decision support in the form of disposition schedules. The model predictive controller assumes that the railway network topology, the timetable, the connections and a forecast of future train movements are given. The controller's time-critical task is to provide the dispatcher with a conflict-free disposition schedule, which assigns a travel path and a start time to each train movement inside the considered time horizon and additionally, minimizes the delays and broken connections that could occur at the central station. More... |
Conflict-free Vehicle Routing with an Application to Personal Rapid Transit
| Author | Kaspar Schüpbach |
| Abstract |
This thesis investigates the conflict-free routing of vehicles through a track network, a problem frequently encountered in many applications in transportation and logistics. The most common routing approach for conflict-free routing problems in various settings is a sequential one, where requests are greedily served one after the other in a quickest way without interfering with previously routed vehicles. There is a need for a better theoretical understanding as guarantees on the quality of the routings are often missing. Conflict-free vehicle routing also is of inherent interest as a sister problem of the well-studied packet routing problem. More... |
Maximal Lattice-Free Polyhedra in Mixed-Integer Cutting Plane Theory
| Author | Christian Wagner |
| Abstract |
Wagner's thesis deals with the generation, evaluation, and analysis of cutting planes for mixed-integer linear programs (MILP's). Such optimization problems involve finitely many variables, some of which are required to be integer. The aim is to maximize or minimize a linear objective function over a set of finitely many linear equations and inequalities. Many industrial problems can be formulated as MILP's. The presence of both, discrete and continuous variables, makes it difficult to solve MILP's algorithmically. The currently available algorithms fail to solve many real-life problems in acceptable time or can only provide heuristic solutions. As a consequence, there is an ongoing interest in novel solution techniques. A standard approach to solve MILP's is to apply cutting plane methods. Here, the underlying MILP is used to construct a sequence of linear programs whose formulations are improved by successively adding linear constraints – so-called cutting planes – until one of the linear programs has an optimal solution which satisfies the integrality conditions on the integer constrained variables. For many combinatorial problems, it is possible to immediately deduce several families of cutting planes by exploiting the inherent combinatorial structure of the problem. However, for general MILP's, no structural properties can be used. The generation of cutting planes must rather be based on the objective function and the given, unstructured set of linear equations and inequalities. On the one hand, this makes the derivation of strong cutting planes for general MILP's more difficult than the derivation of cutting planes for structured problems. On the other hand, for this very reason, the analysis of cutting plane generation for general MILP's becomes mathematically interesting. More... |
Strategic Resource Management for Power Grid Operators
| Author | Michael Guarisco |
| Abstract |
The liberalization of electricity markets has led to an increased cost pressure on power grid operators. As they are also responsible for the reliable supply of electricity, power grid operators aim to optimally balance the opposing objectives of cost and quality of supply. One main aspect of the quality of supply is the continuity of supply, i.e., the availability of electricity to consumers. The continuity of supply strongly depends on the restoration time after incidents in the power grid, which is directly influenced by the availability of (human) resources performing the restoration work. Power grid operators thus try to find an organization of resources that guarantees a high quality of supply at minimum cost. This thesis focuses on strategic resource management for the restoration work after incidents in the power grid. Two models are presented for analyzing the effects of a limited availability of resources on the continuity of supply. The restoration times in both models endogenously depend on the resources currently available. More... |
Market Design for Emission Trading Schemes
| Author |
Max Fehr |
| Abstract |
Emission trading schemes are regulatory frameworks designed to reduce and to control pollution level by creation of economic incentives for responsible emission sources. Currently, there are several systems of this type in operation, with the European Union Emission Trading Scheme (EU ETS) as the largest multi-national mandatory mechanism for trading of carbon dioxide allowances. This thesis is concerned with the mathematical analysis of cap-and-trade schemes and other emissions regulations. We review the existing quantitative analysis on the subject and introduce some of the mathematical challenges posed by the implementation of the new phase of the European Union Emissions Trading Scheme as well as the cap-and-trade schemes touted by the US, Canada, Australia and Japan. From a theoretical point of view, the main thrust of the thesis is the introduction of a new mathematical framework for competitive equilibrium, in which a broad range of emission regulations can be analyzed. From a practical point of view, particular focus is given to the design and numerical analysis of new cap-and-trade schemes for the control and the reduction of atmospheric pollution. We develop tools intended to help policy makers and regulators understand the pros and cons of different regulations. More ... |
Algorithmic decision support for train scheduling in a large and highly utilised railway network
| Author | Gabrio Caimi |
| Abstract |
This thesis addresses the general problem of constructing train schedules, in particular for large and highly utilised railway networks. Commercial requirements for the timetable are assumed to be given, and the task is to provide detailed conflict-free track paths for each train that fulfil these requirements. In the thesis, a comprehensive approach from the commercial description of intended train services to a conflict-free detailed schedule for a whole day is developed. The methodology follows a divide-and-conquer strategy based on three description levels: the service intention, the macroscopic timetable, and the microscopic schedule. The levels are interfaced in such a way that planners have the possibility of intervening into the specifications on every level, and enabling a feedback loops for testing different alternative scenarios. More ... |
Finding Approximate Solutions for Large Scale Linear Programs
| Author | Vania Dos Santos Eleuterio |
| Abstract |
Linear Programming is one of the most frequently applied tools for modeling and solving real world optimization problems. Nonetheless, most commercially available solvers are often incapable of dealing with large problem sizes, e.g.~millions of variables or hundreds of thousands of constraints, arising in modern applications. To cope, researchers have applied decomposition methods, in particular Lagrange relaxation. In this thesis, we investigate new methods for solving Lagrange relaxations and consequently the Linear Program approximately both from a theoretical as well as a numerical point of view. More ... |
Combinatorial Methods for Analyzing Network Security and Reliability
| Author | Rico Zenklusen |
| Abstract |
The main focus in most classical network optimization problems lies on performability. In these problems one usually does not consider the possibility that arcs or vertices may be removed from the given network due to failures or other reasons. However, many systems with an underlying network structure are not perfectly reliable and it is often of high interest to consider network models in settings where arcs and vertices may be removed. Unfortunately, relatively little is known about classical network optimization problems in a failure-prone setting. This thesis deals with classical combinatorial optimization problems on networks in settings where arcs and vertices may be subject to removal. It contains results on four topics to be presented next. In all problems we consider, the arcs and vertices that are removed, are all removed simultaneously. More ... |
Generalized Newton-type methods for nonsmooth equations in optimization and complementarity problems
| Author | Stephan Bütikofer |
| Abstract |
Several problems in variational analysis for e.g. necessary optimality conditions for nonlinear programs, solutions of variational inequalities with explicit equality/inequality constraints and nonlinear complementarity problems, can be analyzed and solved by reformulating the original problem as an equation or generalized equation (inclusion). However, even if the original problem is completely described by smooth functions, nonsmoothness of the resulting equation may appear in a very natural way. This requires methods, which may handle nonsmoothness. The focus of this work is on equations defined by locally Lipschitz functions having a special structure, the so called generalized Kojima functions. This structure is suitable to describe and compute standard generalized (directional) derivatives and to develop generalized Newton-type methods (so called nonsmooth Newton methods) for solving the related Lipschitz equation. This work is divided in three parts: The identification of a suited local nonsmooth Newton method, the globalization of this method and the application and numerical testing of the globalized method. More ... |
| Hydro-Electric Power Plant Dispatch-Planning – Multi-Stage Stochastic Programming with Time-Consistent Constraints on Risk | |
| Author | Martin Densing |
| Abstract |
The principal topic is the optimal operation of a hydro-electric pumped storage plant under uncertainty. The uncertainty stems from the water inflow and from the fluctuations of prices at a spot market, on which the electricity is traded. The model of the plant is formulated as a multi-stage stochastic linear programming problem. A coherent and time-consistent risk-adjusted value is incorporated in a multi-period constraint on risk. More ... |
| Modeling, Pricing and Risk Management of Power Derivatives | |
| Author | Martina Wilhelm |
| Abstract |
Deregulation of energy markets has necessitated the adoption of risk management techniques in the power industry. The launched liberalization and therewith the uncertainty involved in gas, fuel and electrical power prices requires an efficient management of production facilities and financial contracts. Thereby derivatives build essential instruments to exchange volume as well as price risks. However, the valuation of financial derivatives in power markets has proven to be particularly challenging. The fact that electrical power is not physically storable eliminates the direct application of the no-arbitrage methodology from financial mathematics. Consequently, new approaches are required to value even the simplest derivative products in electricity markets. That is, modeling arbitrage-free electricity price dynamics turns out to be the crucial step towards fair pricing of financial products in power markets. More ... |
| Capacity Management and Contract Engineering | |
| Author | Philippe Schiltknecht |
|
Abstract |
For the last few years, traditional markets have been affected by rising competition and increasing dynamics. This trend exposes many companies to new uncertainties and risks. To deal with these challenges it is necessary to increase adaptiveness and reactivity and to act proactively. This «mobility» in general is referred to as flexibility. The dissertation at hand focuses on the identification, valuation and comparison of different flexibilities for the business sector Exclusive Synthesis at Lonza Group Ltd. (LES) and discusses their dependencies and interactions. More ... |
| Valuation of Flexibility for Power Portfolios - A Dynamic Risk Engineering Approach | |
| Author | Jörg Doege |
| Abstract |
Liberalization of power markets in Europe has completely changed the environment for companies active in those markets. Despite the advantages of deregulation, players today are facing the problem of market power resulting from congestions on transmission lines. This fact, combined with the instorability of electricity makes pricing of contracts difficult. It has been observed that prices for contracts such as for virtual storages vary with the method being used for valution. The reason is that the replication of those contracts is not risk free - the risk of the underlying cannot be fully hedged and consequently hedging has to be seen as an action necessary to reduce risk. More ... |
| Stability of Timetables and Train Routings through Station Regions | |
| Author | Thomas Herrmann |
| Abstract |
During the last few years, railway traffic has increased considerably; moreover, it is expected that railroad transportation will further grow for both, passenger and freight transportation. These developments create needs to optimize both the utilization of the existing infrastructure and the coordination tasks inside the railroad company. Thanks to developments in computer science, optimization techniques, and intelligent resource management, railway schedules with increased frequencies can be generated nowadays. Especially near main stations railway operators expect the capacity bottlenecks of the railway system, since there main train lines are intersecting. Tight timetables, however, are exposed to train delays to a greater extent than less dense schedules. The thesis at hand describes stability measures of timetables and the highly related topic of the search for train routings within station regions. As the quality of service should not suffer when introducing new train services, the question of the stability of a timetable is of crucial interest while designing denser timetables. Unforeseen events may require partial modifications of the plans in real-time and therefore re-scheduling procedures should be already taken into account when designing a new timetable. Moreover, re-scheduling procedures should be as easy to implement as possible. Fundamentally, the timetable's ability to absorb some disturbances trades off against full exploitation of available capacity. With the help of evaluation functions, timetables can be examined regarding their likelihood to fail, their sensitivity against disruptions of the schedule, or their efficiency to recover from deviations. Separating the problem of train routings in exact topologies from the saturation of the available capacity and the generation of a timetable in an aggregated topology results in a two level approach. On the upper level a timetable for an intended train service is generated using an aggregated topology. The task on this level is to develop a timetable whose periodicity is as small as possible in order to use the network to full capacity while respecting safety restrictions and the intention of the train service. On the lower level, exact topologies are used in order to decide feasibility of the previously generated, tentative timetables and to analyze the derived schedules. As this thesis mainly deals with stability of timetables, it is consistently assumed that a timetable for the aggregated topology is available. More ... |
| Capacity of Railways in Station Areas using Petri Nets | |
| Author | Dan Burkolter |
| Abstract |
This thesis studies the assessment of available track capacity within a station region. The question is of particular interest as railway operators expect that capacity bottlenecks of the overall railway network will mainly arise in the vicinity of stations which lie at the intersection of the main train lines. However, estimating capacity of a station region is much more taxing than assessing capacity on stretches in between. This is due to the fact that within stations many switches exist, which are in place to ensure that trains can reach any destination. As a consequence, a train may have hundreds of possible routes. Usually, sections with more than two parallel tracks exist such that simply assigning one track to each direction will not suffice. Therefore, train routing has a major impact on capacity utilisation. The developed method states available capacity by constructing a dense schedule where capacity is defined as the time needed to provide a given train service intention on the track topology considered. Additionally, a measure for the stability of a timetable is introduced. Thus, timetables are made comparable according to their capacity utilisation and stability. A two level model is introduced in order to separate choosing train routings from determining the train sequence. On the top level, an aggregated topology is used in which it is assumed that switch regions have unlimited capacity. The task on the aggregated level is to fix the train sequence on stretches between switch regions such that the resulting cycle time of the timetable is minimised. On the lower modelling level, exact topologies of the switch regions are used in order to determine feasibility of the previously derived tentative timetable. More ... |
| Towards Adaptive Management Systems in Manufacturing: An Agent-Supported Approach | |
| Author | Jens Henoch |
| Abstract |
Owing to changing customer demands and expectations, a shift from build-to-forecast to build-to-order production for competitive reasons often becomes necessary in manufacturing. Management systems as a vital part of manufacturing systems have to master these new requirements, i.e. management systems have to cope with complexity and uncertainty. The motivation for this study is based on the observation that a rigid centralized approach to manufacturing planning and control is no longer appropriate. Therefore, this dissertation promotes an agent-based approach as a means of supporting operationally human-centered management systems towards an adaptive and flexible conduct, nowadays essential in manufacturing. The core of this thesis presents a modeling and simulation framework integrating concepts of the fields of management cybernetics, production logistics management, artificial intelligence, and object-oriented concurrent programming. As such, the work is at the crossroads of these fields. The framework features three modeling levels. The resulting models can be verified separately utilizing simulation. Physical layout considerations-such as the selection of machines to be utilized-are mapped on the physical level. Operational issues are addressed at the logical level, meaning that instructions are given on how to operate a physical system. Organizational structures and task responsibilities regarding the operations are modeled on the management level. The organizations being mapped on the management level of this framework are multi-agent systems providing means for management systems in their striving to improve their adaptiveness to the situational conditionalities of the shop-floor. More ... |
| Hedging Strategy and Electricity Contract Engineering | |
| Author |
Gustaf Unger |
| Abstract |
This thesis studies risk management in the electricity market in general and the interaction between physical production and electricity contracts in particular. From a risk management point of view, a power portfolio differs substantially from a traditional financial portfolio. Electricity is non-storable, which together with the marginal production cost characteristics creates jumps in the spot price. The return of a power portfolio is hence typically heavy-tailed, and a risk measure, such as CVaR, that captures this heavy-taildness is needed. To be able to compare production and contracts on a unified basis, we identify the set of contracts that corresponds to each power plant. These contracts build up a replicating portfolio of the power plant. This engineering of contracts allows us to risk manage these often complex contracts, through production. Further, a producing electricity company can through a simple absence of arbitrage argument assess these contracts by studying the costs associated with the corresponding power plant. Flexible production units, such as a gas turbine, relate to options whereas inflexible units, such as a nuclear plant, relate to futures. More ... |
| A Graph Theoretical Approach for Reconstruction and Generation of Oriented Matroids | |
| Author | Lukas Finschi |
| Abstract |
This thesis studies the reconstruction and generation of oriented matroids. Oriented matroids are a combinatorial abstraction of discrete geometric objects such as point configurations or hyperplane arrangements. Both problems, reconstruction and generation, address fundamental questions of representing and constructing (classes of) oriented matroids. The representations which are discussed in this thesis are based on graphs that are defined by the oriented matroids, namely tope graphs and cocircuit graphs. The first part of this thesis studies properties of these graphs and the question as to what extent oriented matroids are determined by these graphs. In the second part, these graph representations are used for the design of generation methods which produce complete lists of oriented matroids of given number of elements and given rank. These generation methods are used in the third part for the construction of a catalog of oriented matroids and of complete listings of the combinatorial types of point configurations and hyperplane arrangements. More ... |
| A Continuous Relaxation Based Heuristic for a Class of Constrained Semi-Assignment Problems | |
| Author | Michael Burkard |
| Abstract |
The constrained semi-assignment problem (C-SAP) is a generalization of the Pseudo-Boolean Optimization problem, where the Boolean variables are replaced by discrete decision variables. Additionally, constraints are given by a set of clauses (similar to those of the Satisfiability problem) which prohibit certain assignments. The C-SAP occurs frequently in real-world applications, but also many combinatorial optimization problems can be formulated in this setting. Since the C-SAP is an NP-hard problem, it cannot be expected that the global optimum can be determined efficiently. For this reason one goal of this work was the development of a heuristic which can be used efficiently for some of those C-SAP instances, for which local search methods are doomed to failure due to their myopia. The newly developed fixed point heuristic (FPH) of this thesis generalizes a method of Cochand for the Generalized Maximum Satisfiability problem such that it can also be applied to constrained maximization problems such as the C-SAP. We will show with the example of the point feature label placement problem that FPH determines also for real-world problems fast good approximate solutions. More ... |
| Managementsysteme für die Shop-Floor Logistik: Eine Modellbasierte Gestaltungsmethodik | |
| Author | Philip Moscoso |
| Abstract |
This thesis describes a model-based methodology for the design of logistic management systems on a shop floor. The methodology comprises a heuristic design procedure and a modeling framework. Together they provide models and principles as well as tools and procedures for this design task. In the face of today's turbulent business environment, the logistic management of the shop floor has become a decisive issue for production companies towards theirsuccess. It determines several factors (e.g. delivery time) that contribute considerably to customer satisfaction. At the same time these factors can bemeasured quite fast and objectively, so over the short-term effects of interventions can be evaluated fairly directly. Until now, the logistic management of the shop floor has been considered primarily as a planning and control task. Thus, the instruments used were generally conceived for systematically anticipating any possible logistical disturbances on the shop floor. Confronted with the practical limits of this aim, the necessity of a new understanding of the shop floor logistics is increasingly becoming a topic in industrial practice and academic research. More ... |
| Computing Economic Equilibria and its Application to International Trade of CO2 Permits: An Agent-Based Approach | |
| Author | Benno Büeler |
| Abstract |
Since Adam Smith postulated the `invisible hand' 200 years ago, economists have had an ambivalent position towards competitive economic equilibria. On the one hand it is the fundamental paradigm of the market economy system and intuitively easy to understand. On the other hand its formal treatment poses considerable dificulties. The first proof of existence for certain models was possible only in the 1930's; but the algorithmic treatment of even simple models has often proved to be hard due to the need of an accurate insight into the concrete model-structure which can be hard to obtain. There are various ways to formalize equilibria; in this work equilibria are formalized through the reaction of economic agents to price signals. Here `agent' is used to denote different things, depending on the context: a consumer, a producer, a whole economic sector, or a geographic unit like a country, etcetera. The `reaction' of an agent is defined as the net selling (supply minus demand, export minus import) which is determined by price. The summing of the reaction of all agents is called (market) excess. More ... |
| Maximum Loss for Measurement of Market Risk | |
| Author | Gerold Studer |
| Abstract |
Effective risk management requires adequate risk measurement. A basic problem herein is the quantification of market risk: what is the overall effect on a portfolio's value if the market rates change? To answer this question, two fundamental diffculties have to be managed: first, market rates behave randomly and are correlated. Second, portfolio structures are high-dimensional and typically nonlinear. The established risk measurement techniques can be divided into two categories. The purely stochastic approaches are based on the portfolio's pro,t and loss (P&L) distribution. The most popular method in this class is Value-at-Risk (VaR), which typically represents the 1 or 5 percent quantile of the P&L distribution. The Maximum Loss (ML) methodology is a member of the second category, where risk is quantified by the value of some worst case scenario. Many of these worst case based measures examine a finite set of scenarios and do not take account of correlations (e.g. stress testing). More ... |
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information
