Doctoral Theses
Abstract
Combinatorics is a branch of mathematics that focuses on the study of discrete objects. It involves counting, arranging, and classifying objects, but it encompasses much more than that. The interplay between structure and randomness, the emergence of unexpected patterns, and the hidden symmetries underlying various problems all contribute to the captivating nature of combinatorics.
Combinatorics continually surprises and challenges us, from the elusive search for Hamilton cycles in graphs to the discovery of new Ramsey-type phenomena in random graphs. Its applications are far-reaching and can be found in computer science, biology, physics, cryptography, and many other fields.
A rich class of problems within combinatorics is concerned with embed-ding graphs into other (host) graphs which have a certain property. In general, one is given a graph H and a graph property P, and the question is whether every graph G with property P contains H as an (induced) subgraph. In Extremal combinatorics, we are in particular concerned with finding the weakest possible property P within a class of properties, which force the existence of H as a subgraph. At the heart of the problem is understanding the various structural aspects of the host graph which are forced by the given property, and focusing on those which are crucial for embedding the desired target graph H. ....
Abstract
This thesis studies online selection problems, with a particular focus on designing constant-competitive algorithms that require less prior information than existing ones. In particular, we present two such algorithms: one for a variant of the matroid secretary problem and the other in the online contention resolution context.
The first setting considered in this thesis is based on the matroid secretary problem (MSP). In MSP, elements of a weighted matroid are revealed one by one and the goal is to pick some of them, so that the selection forms an independent set of as large weight as possible. This setting is motivated by applications in online mechanism design and generalizes the classical secretary problem. It was conjectured that, similar to the classical secretary, there exists an algorithm that is constant-competitive for any matroid constraint. Despite the long line of work dedicated to the problem, so far constant competitive ratio has been attained only for certain classes of matroids and for some variations of MSP. One example is the random assignment model (RAMSP), where an adversary fixes a number of weights equal to the ground set size of the matroid, which then get assigned randomly to the elements of the ground set. However, the two known constant-competitive algorithms for this setting, one by Soto (2013) and the other by Oveis Gharan and Vondrák (2013), crucially rely on knowing the full matroid upfront. Lifting this requirement was left as an open question by the aforementioned authors, as there are good arguments for why such assumptions on prior information should be avoided. In this thesis, we present a constant-competitive algorithm for RAMSP that only needs to know the cardinality of the underlying matroid upfront, making RAMSP the first known MSP variant admitting such an algorithm.
The second part of the thesis is concerned with random order online contention resolution schemes (ROCRS), which are structured online rounding algorithms with numerous applications and links to other well-known online selection problems. We are specifically interested in ROCRS subject to a matroid constraint, since it is one of the most studied constraint families in the context of contention resolution schemes (CRS) and due to connections to the matroid secretary conjecture. In terms of prior information, most previously known ROCRS rely on knowing both the fractional point to be rounded and the matroid in advance. Since this requirement may limit the scope of application of CRS, one may ask whether good algorithms exist in the absence of prior knowledge. Fu, Lu, Tang, Turkieltaub, Wu, Wu, and Zhang (2022) shed some light on this question by proving that no strong (i.e., constant-selectable) online or even offline contention resolution scheme exists if the fractional point is unknown, not even for graphic matroids. In contrast, we consider a setting where the components of the fractional point are revealed online one by one and provide a simple constant-selectable ROCRS for graphic matroids that only requires to know the size of the ground set in advance. Moreover, our procedure works in a more general setting where the algorithm is allowed to sample a random constant fraction of the elements and then receives all the remaining (non-sampled) elements in adversarial order.
Abstract
As more and more decisions are made in an automated fashion, there has been a surge of interest in incorporating fairness aspects into algorithms by design. In this thesis, we investigate how this can be achieved for clustering algorithms.
In a typical clustering problem, we are given a set of data points which we seek to group into so-called clusters according to problem-specific constraints. Common tasks involving clustering include, for example, finding the most central locations for new facilities and summarizing data by identifying representatives that best explain the data.
While clustering algorithms have been the subject of both theoretical and applied research for decades, the added fairness aspect has led to new algorithmic challenges that require novel approaches.
This thesis contributes to this research thrust by presenting several techniques that leverage structural insights resulting in new, improved, and fair clustering algo-rithms.
The fair clustering problems we study include the Robust Matroid Center problem as well as the γ-Colorful k-Center problem and its generalizations. In each case, we present techniques that lead to new approximation algorithms that overcome barriers to prior methods.
In particular, our results include a combinatorial 5-approximation algorithm for Robust Matroid Center, improving upon previous combinatorial algorithms for this problem while using a significantly simpler technique. For the γ-Colorful k-Center problem, our technique gives a 4-approximation algorithm, resolving an open ques-tion by Bandyapadhyay, Inamdar, Pai, and Varadarajan about the existence of con-stant-factor approximations for this problem. Finally, in the context of the more general γ-Colorful F-Supplier problems, a corollary of our technique is a 2O(γ)-approximation algorithm for γ-Colorful Matorid Supplier for linear matroids. We also generalize a method of Jia, Sheeth, and Svensson for colorful k-Center prob-lems, yielding a 7-approximation algorithm for γ-Colorful Knapsack Supplier.
We consider the Connectivity Augmentation Problem (CAP), a classical problem in the area of Survivable Network Design. It is about increasing the edge-connectivity of a graph by one unit in the cheapest possible way. More precisely, given a k-edge-connected graph G = (V, E) and a set of extra edges, the task is to find a minimum cardinality subset of extra edges whose addition to G makes the graph (k + 1)-edge-connected. If k is odd, the problem is known to reduce to the Tree Augmentation Problem (TAP)—i.e., G is a spanning tree—for which significant progress has been achieved recently, leading to approximation factors below 1.5 (the best factor prior to the work from this thesis was 1.458, obtained by Grandoni, Kalaitzis, and Zenklusen (STOC 2018).) However, advances on TAP did not carry over to CAP. Indeed, only very recently, Byrka, Grandoni, and Ameli (STOC 2020) managed to obtain the first approximation factor below 2 for CAP by presenting a 1.91-approximation algorithm based on a method that is disjoint from recent advances for TAP.
In this thesis, we first bridge the gap between TAP and CAP, by presenting techniques that allow for leveraging insights and methods from TAP to approach CAP. We then introduce a new way to get approximation factors below 1.5, based on a new analysis technique that we call stack analysis. Through these ingredients, we obtain a 1.393-approximation algorithm for CAP (and therefore for TAP), corresponding to the currently best approximation result for both problems in a unified way.
We then improve this factor for the well-known special case of leaf-to-leaf instances, presenting a new and arguably simple matching-based method. Combining our work with prior techniques, we readily obtain a (4/3 + ε)-approximation for Leaf-to-Leaf CAP by returning the better of our solution and one of an existing method. Prior to our work, a 4/3-guarantee was only known for Leaf-to-Leaf TAP instances on trees of height 2. Moreover, when combining this technique with the stack analysis approach, we can further improve the approximation factor to 1.29, obtaining for the first time a factor below 4/3 for a nontrivial class of CAP instances.
Let $A\in\mathbb{Z}^{m\times n}$ with $\rank (A)=m$, $b\in\mathbb{Z}^m$ and $c\in\mathbb{Z}^n$. Set $\Delta_m :=\max\{|\det (B)|\colon\newline B\text{ is}$ $\text{an }m\times m\text{ submatrix of }A \}$. We consider integer linear programming problems in standard form $\max \{ c^\intercal x\colon Ax=b,~x\in\mathbb{Z}_{\geq 0}^n \}$ (IP) and its linear relaxation $\max \{ c^\intercal x\colon Ax=b,~x\in\mathbb{R}_{\geq 0}^n \}$ (LP). In this thesis, we study the concept of \textit{proximity}, i.e., we describe the $\ell_1$-distance of an (LP)-optimal vertex solution to its closest (IP)-optimal solution. Firstly, we establish the first proximity bound which is polynomial in $m$ and $\Delta_m$. Secondly, we determine exactly how many different columns $A$ can have in terms of $m$ and $\Delta_m$ if $\Delta_m \leq 2$ or $m\leq 2$. Moreover, we establish the first upper bound on the number of different columns of $A$ which is polynomial in $m$ and $\Delta_m$. This implies the first proximity bound for integer programming problems in standard form with upper bounds which is polynomial in $m$ and $\Delta_m$. Thirdly, for $c\equiv 0$ and a given vertex solution $x^*$ to (LP), we introduce a new parameter $f(x^*)\in\mathbb{Z}_{\geq 1}\cup\{\infty \}$ in terms of which we derive a proximity bound of $(f(x^*)+1)\Delta_m$, which is essentially tight for $f(x^*)\leq m$. Our analysis also yields an efficient feasibility test for (IP) if $f(x^* )$ is constant. Fourthly, in the case $m=2$, we provide an essentially tight proximity bound of $3\Delta_m$ for all but finitely many $b$ if the vertex solution to (LP) corresponds to a prime determinant. Finally, we provide an algorithm that solves (IP) efficiently if $A$ possesses at most three different $m\times m$ subdeterminants in absolute value.
In this thesis, we study discrete combinatorial optimization problems with congruency constraints and present new techniques for dealing with such constraint types.
Strong motivation for studying congruency constraints comes from a long-standing open question in Integer Programming whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable.
An important special case thereof are congruency-constrained integer programs
min { <c,x> : Tx ≤ b, <γ, x> ≡ r (mod m), x ∈ Z^n }
with a totally unimodular constraint matrix T.
Such problems have been shown to be polynomial-time solvable for m = 2, which led to an efficient algorithm for integer programs with bimodular constraint matrices, i.e., full-rank matrices whose n by n subdeterminants are bounded by two in absolute value.
Whereas these advances heavily relied on existing results on well-known combinatorial minimum cut and circulation problems with parity constraints, new approaches are needed beyond the bimodular case, i.e., m > 2.
We make first progress in this direction through several new techniques. In particular, we show how to efficiently decide feasibility of congruency-constrained integer programs with a totally unimodular constraint matrix for m = 3.
Furthermore, for general m, our techniques also allow for identifying flat directions of infeasible problems, and deducing bounds on the proximity between solutions of the problem and its relaxation.
In the second part of this thesis, we study a generalization of the aforementioned parity-constrained minimum cut problems (and therefore also a generalization of other well-known variants of minimum cut problems such as global minimum cuts and minimum s-t cuts), namely congruency-constrained minimum cuts, where we consider cuts whose number of vertices is congruent to r modulo m, for some integers r and m.
We develop a new contraction technique inspired by Karger's celebrated contraction algorithm for minimum cuts, which, together with further insights, leads to a polynomial time randomized approximation scheme for congruency-constrained minimum cuts for any constant modulus m. Instead of contracting edges of the original graph, we use splitting-off techniques to create an auxiliary graph on a smaller vertex set, which is used for performing random edge contractions. This way, a well-structured distribution of candidate pairs of vertices to be contracted is obtained, where the involved pairs are generally not connected by an edge.
As a byproduct, our technique reveals new structural insights into near-minimum odd cuts, and, more generally, near-minimum congruency-constrained cuts.
Finally, we present results on finding a spanning tree subject to constraints on the edges in a family of cuts forming a laminar family of small width. Especially in the context of the Traveling Salesman Problem (TSP), new techniques for finding spanning trees with well-defined properties, and in particular, trees satisfying parity constraints on a chain of cuts, have been crucial in pushing a the analysis of a certain class of approximation algorithms.
Our main contribution is a new dynamic programming approach where the value of a table entry does not only depend on the values of previous table entries, as it is usually the case, but also on a specific representative solution saved together with each table entry. This allows for handling a broad range of constraint types, including a relaxation of congruency constraints, or upper and lower bounds on the number of edges in each cut.
Concretely, we present a quasi-polynomial time algorithm for the Minimum Chain-Constrained Spanning Tree Problem with an essentially best possible guarantee.
Furthermore, we show how parity constraints as used in the context of (path) TSP and a generalization thereof can be handled, and discuss implications in this context.
This thesis is concerned with integer linear optimization problems under the additional assumption that the subdeterminants of the constraint matrix are bounded or exhibit a specific structure. The contribution to this topic is threefold. The first part of the dissertation presents a structural result, a new upper bound on the number of distinct rows of a matrix with bounded subdeterminants. Formally, we show that a matrix A∈ℤ^{m×n} of full column rank and with distinct rows whose largest n×n subdeterminant is at most Δ in absolute value satisfies m≤Δ^{log log Δ+2}⋅n^2+1 if Δ>1 and m≤n^2+n+1 if Δ=1, respectively. The latter case is an immediate consequence of a bound for totally unimodular matrices by Heller [Pacific J. of Math., 7 (1957), pp. 1351-1364]. As a corollary we obtain the same bound on m for an arbitrary integral matrix with distinct rows whose largest subdeterminant is at most Δ in absolute value. The second part of this thesis introduces the following generalization of unimodular matrices: A matrix A∈ℤ^{m×n} is {a,b,c}-modular if the set of n×n subdeterminants of A in absolute value is {a,b,c}, where a ≥ b ≥ c ≥ 0. Given that a and b satisfy certain conditions, we show that any {a,b,0}-modular matrix can be brought into a block structure using row permutations and elementary column operations. Based on this decomposition we construct an algorithm which efficiently recognizes {a,b,c}-modular matrices unless the input matrix possesses a duplicative relation, that is, it admits nonzero n×n subdeterminants k1 and k2 satisfying 2⋅|k1|=|k2|. This is an extension of the classic recognition algorithm for totally unimodular matrices. The third part of the thesis focuses on strictly 3-modular polyhedra, i.e., polyhedra of the form {x∈ℝ^n:Ax≤b} where A∈ℤ^{m×n} has full column rank, its n×n subdeterminants are elements of {0,±3}, and b∈ℤ^m. We show that any integer infeasible strictly 3-modular polyhedron admits a flat direction of width at most 3, independently of its dimension.
We consider linear optimization problems in standard form. We study the special case that the (n-times-n) sub-determinants of the (m-times-n) constraint matrix are, in absolute value, bounded by a constant. This thesis presents results for several special cases which indicate that such integer optimization problems are poly-time solvable. Veselov and Chirkov [41] found an efficient algorithm for this problem in the bimodular case, that is, if the sub-determinants are bounded by 2, under the additional assumption all such sub-determinants are non-zero. We generalize this result by providing a strongly-polynomial algorithm for the bimodular case. This is based on solving an odd-parity constrained TU problem. Furthermore, we consider the strictly 3-modular case when (n-times-n)-sub-determinants are 0, 3 or -3. We give an equivalent TU-description with one congruence constraint. We show, for important special cases, how to decide feasibility, and that the underlying TU-problem admits a flat direction of width 1 if it is infeasible. Finally, we conclude by giving a Python implementation of the core ingredients of our bimodular optimization algorithm.
In this dissertation, we discuss several topics in the context of mixed integer linear programming in variable dimension, both from a theoretical and a practical point of view.
Lying in the intersection of Mathematics and Computer Science, this problem has rich theory and a wide variety of applications. However, many questions in integer linear programming are computationally intractable or known to be NP-hard.
Much of the research in integer linear programming is driven by the goal of utilizing positive complexity results from fixed dimensional problems to related problems in variable dimension.
In the first part of the thesis, we study a reformulation of integer linear programs by means of mixed integer linear programs with fewer integer variables. Our reformulations capture the underlying algebraic and geometric structure of the problem. Our modeling decision is influenced by the ability to solve mixed integer linear programs efficiently when only few integer variables are present. This leads to mixed integer formulations that can express the set of feasible solutions more elegantly than solely linear inequality descriptions.
Many real-world problems that are modeled by integer linear programs have a combinatorial flavor where a feasible solution can be constructed by selecting elements from a given ground set.
In the second part of the thesis, we study such classes of integer linear optimization problems under a time aspect. For some applications, resources to construct a final feasible solution are not available immediately, but the solution can only be constructed step by step in an incremental fashion. Our target is to find a feasible solution for the global optimization problem that is also reasonably good in the intermediate time steps. In order to get such solutions we construct objective functions that punish the violation of the constraints of the global problem in intermediate steps. We show that many of the problems studied inherit the NP-hardness from the related global problem. On the other hand, polynomially solvable cases are identified.
Driven by the application of base station placement for drone supervision, in a third part of the thesis algorithms and complexity results for a geometric covering problem are studied. Techniques from different areas of mathematical optimization and theoretical computer science are combined to solve a new version of a well-known terrain guarding problem.
This thesis considers the constrained submodular function maximization problem (CSFMAX). The property of diminishing marginal returns, which is captured by submodular functions, is observed in numerous relevant maximization problems. CSFMAX problems therefore arise naturally in a wide variety of settings—from sensor placement to machine learning—and have attracted considerable interest during recent years. This thesis aims to contribute towards a better understanding of CSFMAX problems by looking at these problems from different viewpoints. The techniques we introduce lead to simplifications, generalizations, and improvements of existing results.
In the first part of this thesis, we consider relaxation and rounding approaches which became a standard and extremely versatile tool for CSFMAX. One of the most common rounding techniques in this context are contention resolution schemes. Such schemes round a fractional point by first rounding each coordinate independently, and then dropping some elements to reach a feasible set. Also the step where elements are dropped is typically randomized. This leads to a second source of randomization within the procedure, which can complicate the analysis. We suggest a different, polyhedral viewpoint to design contention resolution schemes, which avoids to deal explicitly with the randomization in the second step. This is achieved by focusing on the marginals of a dropping procedure. Apart from avoiding one source of randomization, our viewpoint allows for employing polyhedral techniques. Both can significantly simplify the construction and analysis of contention resolution schemes.
We show how, through our framework, one can obtain an optimal monotone contention resolution scheme for bipartite matchings. So far, only very few results are known about optimality of contention resolution schemes. Our contention resolution scheme for the bipartite case also improves the lower bound on the correlation gap for bipartite matchings.
Furthermore, we derive a monotone contention resolution scheme for general matchings that significantly improves over the previously best one. At the same time, our scheme implies that the currently best lower bound on the correlation gap for general matchings is not tight by yielding a lower bound which is slightly higher.
Our results lead to improved approximation factors for various CSFMAX problems over a combination of matching constraints with further constraints.
Motivated by previous results showing interesting connections between linear and submodular maximization, we further investigate the relation between these two problems in the second part of this thesis. In linear programming, the ubiquitous simplex algorithm is based on the fact that any local optimum with respect to the polyhedral neighborhood is also a global optimum. We show that a similar result carries over to submodular maximization. In particular, every local optimum of a monotone CSFMAX problem yields a 1/2-approximation, and we also present an appropriate extension to the non-monotone setting. However, reaching a local optimum quickly is a non-trivial task. Moreover, we describe a fast and very general local search procedure that applies to a wide range of constraint families, and unifies as well as extends previous methods. In our framework, we match known approximation guarantees while disentangling and simplifying previous approaches. Moreover, despite its generality, we are able to show that our local search procedure is slightly faster than previous specialized methods.
Furthermore, we resolve the open question whether a linear optimization oracle may be enough to obtain strong approximation algorithms for submodular maximization. We show that this is not the case by providing an example of a constraint family for which it is hard to get a good approximation for submodular maximization when using only polynomially many linear optimizaiton oracle calls for the same constraints. From previous work, it follows that the hardness we prove is tight up to logarithmic factors.
The problem of optimizing multivariate scalar polynomial functions over mixed-integer points in polyhedra is a generalization of the well known Linear Programming (LP) problem. While LP problems have been shown to be polynomially solvable, their extension to mixed-integer points, known as Mixed-Integer Linear Programming (MILP), is NP-hard. However, if the number of integer variables is fixed, MILP is polynomially solvable.
We develop algorithms for (mixed-)integer programming problems with a fixed number of variables for several classes of objective functions that are polynomials of fixed degree at least two, with some additional assumptions. With this, we are able to provide new complexity results for the given classes of problems.
The first result deals with minimizing cubic polynomials over the integer points of a polyhedron in dimension two. We show that this
problem is solvable in time polynomial in the input size by providing an explicit algorithm, thus extending a previous result that showed this for quadratic polynomials. We prove this for both bounded and unbounded polyhedra.
The second result deals with minimizing homogeneous polynomials over the integer points of a polyhedron in dimension two. We provide an algorithm for solving this problem in time polynomial in the input size if the degree of the polynomial is fixed and the polyhedron is bounded. This result still holds when the function is the translation of a homogeneous function, even when the resulting function is not homogeneous and the translation vector is not known. We also show that if the polyhedron is unbounded, then a solution of minimal size to this problem can have exponential size in the input size.
The third result deals with minimizing quadratic polynomials over the mixed-integer points of polyhedra in fixed dimension. We show that this problem is solvable in time that is polynomial in the size of the input and the maximum absolute values of the matrices defining the constraints and the objective function. We also combine this with previous results to derive a similar result for quadratic functions defined by a low-rank matrix in variable dimension.
The fourth result also deals with minimizing quadratic polynomials over the integer points of a polyhedron in fixed dimension. We present a fully polynomial-time approximation scheme (FPTAS) for this problem when the objective function is homogeneous and the matrix defining it has at most one positive or at most one negative eigenvalue.
This thesis addresses problems that arise in protection models for optimal inhibition of harmful diffusion processes in networks. Specifically, we study the Firefighter problem, introduced two decades ago by Hartnell [59], a variant of it, known as Resource Minimization for Fire Containment (RMFC), and the Multilevel Critical Node problem (MCN), which is a new model introduced in this thesis.
The Firefighter problem and the RMFC problem have attracted considerable attention in the last decades, but despite progresses on several fronts, the approximability of these problems is still badly understood. This is the case even when the underlying graph is a tree, which is one of the moststudied graph structures in this context and the focus of the first part of this thesis. Prior to this work, the best known approximation ratios were an O(1)-approximation for the Firefighter problem and an O(log n)-approximation for RMFC, both being LP-based and essentially matching the integrality gaps of two natural LP relaxations. We improve on both approximations by presenting a PTAS for the Firefighter problem and an O(1)-approximation for RMFC, both qualitatively matching the known hardness results. Our results are obtained through a combination of the known LPs with several new techniques, which allow for efficiently enumerating over super-constant size sets of constraints to strengthen the natural LPs.
In the second part of this thesis, we define the MCN problem as a combination of two different paradigms in the field of network protection. The first perspective looks at network safety from the point of view of prevention: for a given network, the goal is to modify its structure, in order to minimize its capacity to propagate failures. The second perspective consider blocking models. These problems have been proposed for scenarios where the attack has already taken place, in the spirit of the Firefighter problem. In this case, the harmful diffusion process is assumed to propagate through the network with particular dynamics that allow for adopting defensive reactions. The MCN problem combines these two perspectives, following the framework of the Defender-Attacker-Defender model, as introduced by Brown et al. [19]. In this thesis, we define the MCN problem, we devise an exact algorithm for it and we perform an experimental study, both on the performance and on the quality of the optimal solution in comparison to a simpler sequential model.
In this dissertation we discuss several approaches to solve integer and mixedinteger convex minimization problems. That is, we try to minimize a convex function over a convex set with the additional constraint that a small number variables must be integral.
The thesis consists of four parts.
In the first part we apply the Mirror-Descent Method from continuous convex optimization to the mixed-integer setting. The main feature of this method is that the number of iterations is independent of the dimension, however, this method relies on a strong oracle, the so called improvement oracle. We present an efficient realization of such an oracle for the case when only two variables are required to be integral.
The second part contains two alternative, short, and geometrically motivated proofs of the well known result that minimizing a convex function over the integral points of a bounded convex set is polynomial in fixed dimension. In particular, we present an oracle-polynomial algorithm that is based on a mixed-integer linear optimization oracle.
Then, in the third part, we extend the Method of Centers of Gravity to the integer and mixed-integer setting. The crucial step consists in replacing the points of center of gravity by more general center-points, allowing us to use measures other than the volume. We introduce the concepts of center-points and approximate center-points. For special instances we prove properties of the (approximate) center-points. In the integer setting and when the dimension is fixed, we present an algorithm to compute approximate center-points. Furthermore, we establish optimality certificates for (mixed-) integer minimization problems based on lattice free polyhedra and we present a algorithm
based on center-points that terminates with such an optimality certificate.
In the last part we consider a special class of, not necessarily convex, optimization problems in variable dimension. We aim to optimize f(Wx) over a set P \ Zn, where f is a non-linear function, P Rn is a polyhedron and W 2 Zdn. The dimension n may vary, however, we assume that the dimension d is fixed. We obtain an efficient transformation from the latter class of problems to integer linear problems. The core result is a representation theorem, characterizing the set W(P \ Zn), which can be seen as Frobenius
type theorem for polyhedra.
This thesis deals with new techniques to construct a strong convex relaxation for a mixed-integer nonlinear program (MINLP). While local optimization software can quickly identify promising operating points of MINLPs, the solution of the convex relaxation provides a global bound on the optimal value of the MINLP that can be used to evaluate the quality of the local solution. Certainly, the efficiency of this evaluation is strongly dependent on the quality of the convex relaxation.
Convex relaxations of general MINLP can be constructed by replacing each nonlinear function occurring in the model description by convex underestimating and concave overestimating functions. In this setting, it is desired to use the best possible convex underestimator and concave overestimator of a given function over an underlying domain -- the so-called convex and concave envelope, respectively. However, the computation of these envelopes can be extremely difficult so that analytical expressions for envelopes are only available for some classes of well-structured functions.
Another factor influencing the strength of the estimators is the size of the underlying domain: The smaller the domain, the better the quality of the estimators. In many applications the initial domains of the variables are chosen rather conservatively while tighter bounds are implicitly given by the constraint set of the MINLP. Thus, bound tightening techniques, which exploit the information of the constraint set, are an essential ingredient to improve the estimators and to accelerate global optimization algorithms.
The focus of this thesis lies on the development and computational analysis of new convex relaxations for MINLPs, especially for two applications from chemical engineering. In detail, we derive a new bound tightening technique for a general structure used for modeling chemical processes and provide different approaches to generate strong convex relaxations for various nonlinear functions.
Initially, we aim at the optimal design of hybrid distillation/melt-crystallization processes, a novel process configuration to separate a mixture into its component. A crucial part in the formal representation of this process as well as other separation processes is to model the mass conservation within the process. We exploit the analytical properties of the corresponding equation system to reduce the domains of the involved variables. Using the proposed technique, we can accelerate the computations for hybrid distillation/melt-crystallization processes significantly compared to standard software.
Then, we concentrate on the generation of convex relaxations for nonlinear functions. First, we exploit the existing theory for two interesting classes of bivariate functions. On the one hand, we elaborate, implement, and illustrate the strength of a cut-generation algorithm for bivariate functions which are convex or concave in each variable and for which the sign of the Hessian is the same over the entire domain. On the other hand, relaxation strategies for advanced equilibrium functions in chromatographic separation processes are analyzed and finally applied to completely describe the feasible separation regions of these processes.
Second, we suggest to derive the envelopes in an extended space to overcome the combinatorial difficulties involved in the computation of the convex envelope in the original space. In particular, we consider a class of functions accounting for a large amount of all nonlinearities in common benchmark libraries. These functions are component-wise concave in one part of the variables and convex in the other part of the variables. For this general class of functions the convex envelopes in the original variable space have not been discovered so far. We provide closed-form expressions for the extended formulation of their convex envelopes based on the simultaneous convexification with multilinear monomials. By construction, this approach does not only yield an extended formulation for the convex envelope of a function, but also a strong simultaneous relaxation of the function and the involved multilinear monomials. Several examples show that this simultaneous relaxation can be orders of magnitude better than the individual relaxation of the functions.
Finally, inspired by the strength and the computational impact of the simultaneous relaxation of a function and multilinear monomials, we further focus on the simultaneous convexification of several functions. In such an approach the relaxation of a MINLP involving several functions in the same variables is much tighter because the interdependence between the different functions is taken into account. We study the simultaneous convex hull of several functions for which we derive theoretical results concerning their inner and outer description by means of the rich theory of convex envelopes. Moreover, we apply these results to provide formulas for tight convex relaxations of several univariate convex functions.
Implementations of all convexification techniques are available as plugins for the open-source MINLP solver SCIP. The computational results of several case studies reveal the benefit of the proposed techniques compared to state of-the-art methods.
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.
Along these lines we define several new models of robust combinatorial optimization. The common feature of all these models is the assumption that the underlying combinatorial structure is an upper-ideal. This property ensures that all resulting robust counterparts addressed by this thesis are covering problems. On the one hand, this property is realistic from the point of view of many applications. On the other hand, it helps to control the quality of the robust solutions, thus making it less conservative than other robust models.
The focus of this thesis is put on the development of efficient exact and approximate algorithms for robust counterparts of classical combinatorial optimization problems. These results are complemented by corresponding complexity-theoretic results. A survey of the robust combinatorial optimization literature is also presented.
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.
On the mathematical side the logical framework and its extensions are derived and formalized. The basic model evolves to a special type of satisfiability problem (SAT) whose complexity is classified to be generally hard but mathematically easy subclasses are identified. The correspondence between SAT and integer programming is exploited and the underlying polyhedra are analyzed. Interestingly, the SAT problem allows for a wider class of polynomially solvable problems than its integer programming equivalent. Nevertheless, the computational results provided proof that the integer programming approach is computationally feasible. The basic SAT problem can additionally be translated into a bipartite digraph for which algorithms are adapted, and their practical use is discussed. Furthermore, for a special class of biological units a duality framework based on linear programming duality is derived, which completes the theory of such biological units.
The dynamic extension of the basic framework yields a related SAT problem that contains the original one as a special case, and is thus hard to solve as well. The focus for this extension is on the analysis of maximally feasible and minimally infeasible solutions of the extended SAT problem. Therefore, it is necessary to optimize over the set of solutions of the SAT problem which suggests to employ the equivalent integer programming approach. To enumerate all maximally feasible and minimally infeasible solutions the Joint Generation algorithm is utilized. To this end, a monotone reformulation of the extended SAT problem is derived that preserves the maximally feasible and minimally infeasible solutions, and at the same time significantly reduces the size of the description. In certain very restrictive cases the resulting integer optimization problems are even computationally tractable. Finally, the minimally infeasible solutions are completely characterized by means of graph structures in the original digraph, and an alternative method for computing all minimally infeasible solutions via polyhedral projection is obtained.
The discrete extension of the logical framework leads to a generalization of the SAT problem, the so called interval satisfiability problem. In this setting the variables are integer valued and associated intervals provide the set of values for which the expression becomes TRUE. To computationally determine feasible solutions, this problem is transformed to a system of polynomials which can be checked for feasibility by means of Hilbert's Nullstellensatz. Moreover, the general interval satisfiability problem is analyzed with respect to complexity and satisfiability. Concerning the computational complexity, it is shown to be generally hard even if assuming certain restrictions for the formulas. Concerning the satisfiability behavior the well known threshold phenomenon of classical random SAT, which has been observed for interval satisfiability, is examined and lower bounds on specific thresholds are identified.
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.
Smoothing Techniques constitute a two-stage procedure: we derive a smooth approximation of the objective function at first and apply an optimal First-Order method to the adapted problem afterwards. We present a refined version of this optimal First-Order method in this thesis. The worst-case complexity result for this modified scheme is of the same order as for the original method. However, numerical results show that this alternative scheme needs much less iterations than its original counterpart to find an approximate solution in practice. Using this refined version of the optimal First-Order method in Smoothing Techniques, we are able to solve randomly generated matrix saddle-point problems involving a hundred matrices of size 12'800 x 12'800 up to an absolute accuracy of 0.0012 in about four hours.
Smoothing Techniques and Mirror-Prox methods require the computation of one or two matrix exponentials at every iteration when applied to the matrix saddle-point problems obtained from the above transformation step. Using standard techniques, the efficiency estimate for the exponentiation of a symmetric matrix grows cubically in the size of the matrix. Clearly, this operation limits the class of problems that can be solved by Smoothing Techniques and Mirror-Prox methods in practice. We present a randomized Mirror-Prox method where we replace the exact matrix exponential by a stochastic approximation. This randomized method outperforms all its competitors with respect to the theoretical complexity estimate on a significant class of large-scale matrix saddle-point problems. Furthermore, we show numerical results where the randomized method needs only about 58% of the CPU time of the deterministic counterpart for solving approximately randomly generated matrix saddle-point problems with a hundred matrices of size 800 x 800.
As a side result of this thesis, we show that the Hedge algorithm - a method that is heavily used in Theoretical Computer Science - can be interpreted as a Dual Averaging scheme. The embedding of the Hedge algorithm in the framework of Dual Averaging schemes allows us to derive three new versions of this algorithm. The efficiency guarantees of these modified Hedge algorithms are at least as good as, sometimes even better than, the complexity estimates of the original method. We present numerical experiments where the refined methods significantly outperform their vanilla counterpart.
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.
Many models and algorithms for train dispatching have already been proposed in the literature, but only a few of them with successful application in practice. The few successful applications are either limited to a restricted area of switches, consider a simpler network topology or are based on heuristics that lack a quality assertion. Approaches that are not affected by any of these restrictions, have so far not be applied in daily operations mostly due to their computational complexity. The approach of this thesis for dispatching trains in a central railway station area is sufficiently fast in order to be used in a decision support system and in addition, provides a guarantee of quality.
The train dispatching problem is addressed in this thesis in three consecutive steps:
1. Alternative train paths, alternative departure times and speed profiles are combined and form a set of alternative, so-called blocking time stairways, which model essentially safety corridors for the train movements in the railway network.
2. A mathematical constrained assignment model is formulated as a binary linear program in which constraints preclude safety-related and operational conflicts between alternative blocking time stairways and thus, the choice for assigning a blocking time stairway to each train movement is limited.
3. A bi-objective function is added to the model to measure the quality of an assignment in terms of generated delays and broken connections at the central station. Finally, a commercial solver based on mathematical optimization techniques computes the best assignment.
The efficiency of this approach in terms of computation time depends on the formulation of the binary linear program. The formulation proposed in this thesis has considerably fewer variables as well as fewer and stronger constraints compared to previous formulations. The associated LP relaxation provides better bounds on objective values due to the stronger constraints, which in turn can be exploited by the solver and result in much shorter computation times.
A major aspect of this thesis was to showcase the viability of this framework in a comprehensive case study, so that industry will take this framework a step further towards its integration in practical operations. In close collaboration with the Swiss federal railways (SBB) the closed-loop discrete-time control system was simulated in a laboratory setting. In the simulation trains were dispatched over the course of a day in the central railway station area Berne, Switzerland. The closed-loop discrete-time control framework was successfully able to dispatch trains in a time interval of one minute. Nevertheless, the laboratory setting precluded a study of the qualitative impact that the closed-loop system would have on a physical railway system. The thesis outlines three additional important steps, which are required before a successful integration of this framework in practice becomes possible:
1. The framework is interfaced with a simulation environment that will be responsible for simulating the train movements in the physical railway system.
2. The dispatcher has to be incorporated in the close-loop system. A good platform for the interaction of the control system with the dispatcher is critical for a successful integration of the presented decision support system.
3. When the platform for the interaction between dispatcher and the control system can be successfully operated over a simulated physical railway system, the simulation can be replaced by the real world railway system.
It is obvious that the SBB strives for improved operational processes and thus supported this thesis. But it is quite remarkable that the SBB also supports the stepwise approach suggested by the thesis towards integrating decision support systems in their operational processes. As a consequence, the SBB started a new project in which the framework will be studied further by interfacing the closed-loop control system with a railway simulation software.
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 conflictfree 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.
In the first part, we present new theoretical results for the case of bidirectional networks. We consider a natural basic model for conflict-free routing of a set of k vehicles. Previously, no efficient algorithm is known with a sublinear (in k) approximation guarantee and without restrictions on the graph topology. We show that the conflict-free vehicle routing problem is hard to solve to optimality even on paths. Building on a sequential routing scheme, we present an algorithm for trees with makespan bounded by O(OPT) + k. Combining this result with ideas known from packet routing, we obtain a first efficient algorithm with sublinear approximation guarantee, namely an O(√k)-approximation. Additionally, a randomized algorithm leading to a makespan of O(polylog(k)) • OPT + k is presented that relies on tree embedding techniques applied to a compacted version of the graph to obtain an approximation guarantee independent of the graph size.
The second part is about routing in the Personal Rapid Transit (PRT) application. PRT is a public transportation mode in which small automated vehicles transport passengers on demand. Central control of the vehicles leads to interesting possibilities for optimized routings. Routing in PRT is an online problem where transit requests appear over time and where routing decisions need to be taken without knowledge of future requests. Further, the network in PRT is directed. The complexity of the routing problems together with the fact that routing algorithms for PRT essentially have to run in real-time often leads to the choice of a fast sequential scheme. The simplicity of such schemes stems from the property that a chosen route is never changed later. This is as well the main drawback of it, potentially leading to large detours. It is natural to ask how much one could gain by using a more adaptive routing strategy. This question is one of the core motivations of this second part.
We first suggest a variation to the routing model used in the first part which is suitable for PRT. We show that the routing problem remains hard in the directed setting. Further, we introduce a capacity notion for PRT networks and derive a bound for it. Computational results show that the capacity bound is close to the achievable throughput. It therefore is a useful quantity for estimating network capacity in PRT system design. We then introduce a new adaptive routing algorithm that repeatedly uses solutions to an LP as a guide to route vehicles. New requests are integrated into the LP as soon as they appear and the routing is reoptimized over all vehicles concurrently. We provide computational results that give evidence of the potential gains of an adaptive routing strategy. For this we compare the presented adaptive strategy to sequential routing and to a simple distributed routing strategy in a number of scenarios.
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.
In his thesis, Wagner presents an approach to generate cutting planes for a general MILP. The cutting planes are obtained from lattice-free polyhedra, that is polyhedra without interior integer point. Wagner's point of departure is an optimal solution of the linear programming relaxation of the underlying MILP. By considering multiple rows of an associated simplex tableau, a further relaxation is derived.
The first part of Wagner's thesis is dedicated to the analysis of this relaxation and it is shown how cutting planes for the general MILP can be deduced from the considered relaxation. It turns out that the generated cutting planes have a geometric interpretation in the space of the discrete variables. In particular, it is shown that the strongest cutting planes which can be derived from the considered relaxation correspond to maximal lattice-free polyhedra. As a result, problems on cutting planes are transferable into problems on maximal lattice-free polyhedra.
The second part of Wagner's thesis addresses the evaluation of the generated cutting planes. It is shown that the cutting planes which are important, are at the same time the cutting planes which are difficult to derive in the sense that they correspond to highly complex maximal lattice-free polyhedra. In addition, Wagner shows that under certain assumptions on the underlying system of linear equations and inequalities, the important cutting planes can be approximated with cutting planes which correspond to less complex maximal lattice-free polyhedra. A probabilistic model is used to complement the analysis. Moreover, Wagner gives a geometric interpretation of his results.
The third part of Wagner's thesis focuses on the analysis of lattice-free polyhedra. In particular, the class of lattice-free integral polyhedra is investigated, a class which is important within a cutting plane framework. Two different notions of maximality are introduced. Wagner distinguishes into the class of lattice-free integral polyhedra which are not properly contained in another lattice-free integral polyhedron, and the class of lattice-free integral polyhedra which are not properly contained in another lattice-free convex set. Both classes are analyzed, especially with respect to the properties of their representatives and the relation between the two classes. It is shown that both classes are of large cardinality and that they contain very large elements.
For the second as well as the third part of Wagner's thesis, statements about two-dimensional lattice-free convex sets are needed. For that reason, the fourth part of the thesis is devoted to the derivation of these results.
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.
The first model is a grid operation model that simulates in detail the resources' activities for restoration after incidents in all voltage levels. An assignment problem is repeatedly solved to decide which incidents are restored by the resources currently available. Results of the model include estimates of the non-availability of supply, which is an indirect measure of the continuity of supply, and of probability distributions of, e.g., the restoration time of incidents. By evaluating various key performance indicators, different organizations of resources can be analyzed and compared. New key performance indicators based on incidents without interruption of supply are suggested. Due to its applicability to real-world instances, the model provides a useful tool to support strategic decisions of power grid operators concerning resource management.
The second model is a component-based model for redundant power grids with exponential failure and repair rates. The repair, however, is only performed if a resource is available. The optimal assignment of resources to failures is determined by a Markov decision process that minimizes the average expected power not supplied over an infinite time horizon. To cope with the large number of states, an aggregated model is formulated that yields an upper bound on the base model. Even though the effects of a varying number of resources on the continuity of supply can be quantified, the observed effect is only marginal. The continuity of supply is determined much more by the redundancies in the power grid and the failure/repair rates than by the number of available resources. The results of the model confirm the high redundancy in meshed power grids and the very rare occurrence of failures.
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.
As some fundamental differences between regulations do not occur in a deterministic setting we propose a stochastic equilibrium model for an economy where firms produce goods to satisfy an inelastic demand and are endowed with permits in order to offset their pollution at compliance time and avoid having to pay a penalty. Thereby we consider risk neutral (as opposed to risk averse) firms with the aim to obtain stronger equivalence results between different emission regulations. Firms that can easily reduce emissions do so, while those for which it is harder buy permits from firms which anticipate they will not need all their permits, creating a financial market for pollution credits. Our equilibrium model elucidates the joint price formation mechanism for goods and pollution allowances, capturing most of the features of the first phase of the European Union Emissions Trading Scheme. We show existence of an equilibrium and show that its solution reduces to an optimal stochastic control problem. We also prove uniqueness of emission credit prices and characterize the equilibrium prices of goods as well as the optimal production and trading strategies of the firms.
Thereby it is shown that standard cap-and-trade schemes, designed in the spirit of the EU ETS are socially optimal (also in a stochastic setting!). However this does not imply that such schemes are inexpensive for consumers. In particular it is proven that standard cap-and-trade schemes increase consumer costs through a notable price increase for products, whose production causes pollution (for instance electrical power for EU ETS). This observation is evident, since the regulation shifts production towards cleaner, hence more expensive technologies, while the cost of pollution is factored into the prices of those products.
One of the main targets of this thesis is to quantify such effects as well as other qualitative properties of emission regulations in a realistic framework. To this end we use the Japanese electricity market to numerically simulate the equilibrium in different regulatory settings. For this market it turns out that on one hand reduction costs are astonishingly low while on the other hand it is shown that consumers burden exceeds by far the overall reduction costs, giving rise for huge windfall profits for electricity companies, which was also observed in EU ETS. Moreover we use this numerical illustration to show that even tax based regulations and standard cap-and-trade schemes with a 100% auction can fail to reduce windfall profits to a reasonable level.
This fact demonstrates the strong need for an improvement of generic cap-and-trade mechanisms. We show how to adapt the regulatory framework of an emission trading scheme in such a way that the final consumer costs are reasonably low, preserving the social optimality of the mechanism at the same time. The resulting relative and hybrid allocation schemes demonstrate that an apparently innocuous small change in the design can have a dramatic economic impact.
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.
Many models and algorithms for train scheduling have already been proposed in the literature, some of them with successful application in practice. However, they are either designed for large-scale problems, considering a simplified topology and safety system, or are detailed approaches, yet applicable only to a restricted area. This thesis combines both approaches for finding detailed schedules for large networks, partially relying known models and algorithms from the literature, adapted or extended, and partially developing totally new ideas and methods.
The starting point of the approach is the construction of an appropriate structure for describing the intended train services, including periodicity information. This partial periodic Service Intention (ppSI) contains the commercial offer that a railway company would like to tender to the customers during a day. The purpose of the ppSI is to have a formal framework in which potential commercial offers can be developed and described systematically. An important property of modern railway timetables is their periodic pattern, so that they are easy for the customers to memorise. In addition to this regularity, the introduction of irregular train services is necessary to cope with varying demand over the day. The developed ppSI can describe commercial railway offers with partial periodic structure in a compact form and can exploit these effectively in the train scheduling process.
The basic idea to handle the partial periodicity of the service intention is an equivalent projection onto a single period time, resulting in an augmented periodic problem. This augmented periodic timetabling problem is then solved first globally on an aggregated topology with a simplified safety model (macroscopic level), and subsequently, locally refined by considering more details of the railway infrastructure and train dynamics (microscopic level). Finally, the generated periodic conflict-free train schedule is rolled out over the complete day to create a production plan that fulfils all requirements that were initially specified in the service intention.
The macroscopic level focuses on global interdependencies over the entire network for generating the most important properties of the timetable and thus has to avoid dealing with large amounts of detailed information that is only locally relevant. According to the simplified topology model, safety constraints and train dynamics are also simplified. A well known model for this description level is the Periodic Event Scheduling Problem (PESP). In this thesis, an extension called Flexible Periodic Event Scheduling Problem (FPESP) is introduced and applied, allowing for time slots for each event instead of fixed times. Moreover, an extension of the FPESP model is proposed, the Flexbox model, which is a further generalisation of the FPESP that allows to make use of natural dependencies among events in the service intention. The resulting (flexible) macroscopic timetable is then used as input for the microscopic level.
The existence of an operable production plan for a given draft timetable has to be checked on the microscopic level by taking into account detailed information that is important for ensuring the schedule to be conflict-free, but which are not relevant for the global structure of the timetable and have therefore been neglected on the macroscopic level. The safety model on the microscopic level follows the way the interlocking system works. It computes the blocking times on each infrastructure element based on the signalling system and ensures that these blocking time intervals do not overlap. Moreover, the computed track paths must specify a speed profile that the train driver can follow, given a reasonable tolerance band. As the microscopic scheduling problem might become infeasible, the event time slots of the FPESP solution give more freedom, which is particularly crucial in bottleneck regions with dense traffic, where the solution on the macroscopic level with fixed times is often too restrictive.
The requested level of detail, together with dense traffic, leads to a enormous problem size. Therefore, a network separation approach is applied to divide the railway network into zones of manageable size by taking account of the network properties, distinguishing condensation and compensation zones. Condensation zones are usually situated near main stations, where the track topology is complex and many different routes exist. As such an area is expected to have a high traffic density, it is also a capacity bottleneck and trains are required to travel through with maximum allowed speed and thus without time reserves. Collisions are avoided by exploiting the various routing possibilities in the station area. Conversely, a compensation zone connects two or more condensation zones and consists of a simpler topology and less traffic density. Here, time reserves should be introduced to improve timetable stability. The choice of an appropriate speed profile is the most important degree of freedom to exploit in these compensation zones.
For both zones, a new model called Resource Tree Conflict Graph (RTCG) is developed for solving the microscopic scheduling problem. In this model, a set of scheduling alternatives for each train is computed first and stored in a compact way using a tree structure. In condensation zones, these alternatives are computed by looking at all routes through the topology as well as a discrete set of starting times for each train. In compensation zones, a reasonable set of alternative speed profiles for the few different routes is computed. Afterwards, constraints are derived that preclude conflicts between the alternatives on the involved resources. Based on a graph model, a resource-constrained integer multicommodity flow problem is formulated as an integer linear program. The model has considerably fewer and stronger constraints compared to previous formulations based on stable sets in conflict graphs, which leads to a much stronger LP relaxation and hence much shorter computation times. The RTCG model enables therefore large problems to be solved quickly. In the case of lack of feasibility in a zone on the microscopic level, a feedback strategy is applied to generate another macroscopic schedule according to the information obtained from the microscopic level.
The proposed multi-level approach is validated through some real-world test cases from Switzerland. Computational results are presented for all steps of the timetable generation process, and are compared with previous methods for evaluating their improvements.
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.
In the theoretical part, we consider two recently developed primal-dual optimization methods by Nesterov for approximately solving non-smooth convex optimization problems. The first method, called Primal-Dual Subgradient method, is a variation of the standard subgradient method, where the computed subgradients are used not only to create at each step a primal but also a dual solution. This method has a convergence rate of O(1/Є2) to reach an absolute accuracy of Є>0, which is the best possible rate for techniques based on subgradients. The second method, called Excessive Gap method, consists of a smoothing of the objective functions and the usage of optimal gradient schemes. It has a convergence rate of O(1/Є). Using this method, we design a polynomial time approximation scheme for the linear programming relaxation of the Uncapacitated Facility Location problem, which improves the running time dependence on Є from the previously known O(1/Є2) to O(1/Є).
Both methods depend on oracles for solving subproblems in each iteration. However, exact oracles are often unavailable. We examine the influence of approximate oracles on the overall convergence of the methods. We show that in order to obtain an overall absolute accuracy of Є, the Primal-Dual Subgradient method requires oracles with a theoretical accuracy of Є2. In contrast, the Excessive Gap method needs an oracle accuracy of Є5 suggesting that it is much less stable. However, we only assumed to know the absolute accuracy of the solution delivered by the oracles. Introducing other requirements may lead to an improvement of these results.
In the practical part of the thesis, we examine the application of the methods to the linear programming relaxation of the Uncapacitated Facility Location problem and the Static Traffic Assignment Problem, for which we had access to real world data. As expected by theory, the Excessive Gap method outperformed the Primal-Dual Subgradient method in solving the linear programming relaxation of the Uncapacitated Facility Location problem, for which exact oracles are available. Surprisingly, the Primal-Dual Subgradient method was much better than the Excessive Gap method in solving the Static Traffic Assignment Problem. This can be explained by the subproblems arising in the methods. In the Excessive Gap method, we have to solve Minimum Quadratic Cost Flow problems, which are much harder than the Shortest Paths computations arising in the Primal-Dual Subgradient method. For solving the Minimum Quadratic Cost Flow problem, we considered approximate oracles and we noticed that the Excessive Gap method demonstrated more stability than predicted by theory.
As we used a novel formulation of the Static Traffic Assignment problem developed by Nesterov and de Palma, we also compared the characteristics of the obtained traffic assignments to assignments obtained using the traditional Beckmann model. Results showed that the Nesterov and de Palma model better concentrates travel flows leading to more predictable congestions.
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.
The first problem we consider, is the problem of estimating s-t reliabilities in acyclic digraphs. As long as the reliability to estimate is not too small, a crude Monte-Carlo approach can be used to obtain a good estimate with high probability. However, this method needs a tremendous amount of time to deliver good estimates for very small reliabilities. Small reliabilities often have to be estimated in models where one is interested in rare events with a high impact. We suggest a method allowing to estimate very small s-t reliabilities in large acyclic digraphs and present structural conditions on the input network under which the proposed algorithm is an FPRAS.
The second problem that will be discussed is known as network flow interdiction and can be described as follows. In a given flow network one has to remove a subset of the arcs constrained to some budget such that the value of a maximum flow in the resulting network is minimized. Although this problem is known to be NP-hard in general, pseudo-polynomial algorithms are known for some special cases of planar instances. We present new approaches that allow to solve in pseudo-polynomial time a wider class of planar instances than previously possible. In particular, we present a method for incorporating the possibility of vertex removals and vertex capacities. Furthermore, an algorithm is presented that can solve a particular type of interdiction problem on networks with multiple sources and sinks. We also show a technique for converting a large class of pseudo-polynomial network flow interdiction algorithms into FPAS's.
In the third part of the thesis we introduce the matching interdiction problem which is basically a natural extension of other interdiction problems to matchings. The task is to choose in a given undirected network a subset of edges with respect to some budget such that the weight of a maximum matching in the resulting network is minimized. Hardness results for different types of graph classes are presented. For graphs with bounded treewidth we introduce a pseudo-polynomial algorithm and an FPAS.
In the fourth part of this thesis we present a proof for a conjecture raised by Goemans and Vondrák about a bound on the number of edges contained in the union of all minimum spanning trees of fixed sized subgraphs. We show that the proven bound can be seen as a generalization of Mader's theorem which bounds the number of edges in any edge-minimal k-connected graph.
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.
In a first part we review the class of generalized Kojima functions and different generalized derivatives. We compute these generalized derivatives for generalized Kojima functions and obtain exact formulas, especially for our main application class resulting from nonlinear programs with data, which are not twice differentiable, but differentiable with locally Lipschitzian derivative.
We consider a local nonsmooth Newton method introduced by Bernd Kummer, which can handle different generalized derivatives and allows inexact solutions of the Newton equation. We work out the abstract convergence conditions from this method for generalized Kojima functions.
In a second part a globalization of this local method by a path search with non-monotone backtracking is described in a rather general framework. We discuss and analyze the causes for a possible premature termination. Under the assumptions of feasibility we give a global convergence theorem. We show that the globalized method inherits the convergence properties from the local Newton method.
We also present a modification of the globalized method, which enables the integration of a suited first order method.
A third part is devoted to the applications and numerical testing of the globalized method. We specify the single steps of our method for finite dimensional optimization problems and complementarity problems. The numerical results on a set of test problems from (generalized) semi-infinite optimization and nonlinear complementarity problems are very satisfying. They confirm the theoretical convergence results derived in the second part.
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.
The thesis is made up of two parts. The first part considers coherent risk-adjusted values, the second part the optimal control of the plant. The first part defines a simple recursive risk-adjusted value, for which in a special case a lower bound can be derived. In the second part, some optimization problems of simple dispatch models are explicitly solved; the problems are structured similarly to those in coherent risk measurement. The short-term trading on the spot market is modeled in defiance of the limited number of numerically tractable time stages. The scenario tree is generated by the occupation times of the spot price. The principal component analysis of the occupation times exhibit their characteristic pattern. Finally, the general dispatch model subject to the multi-period constraint on risk is numerically solved.
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.
In this work we propose an approach, which converts an electricity market into a virtual base market consisting of zero bonds and an additional risky asset. Using this structure, interest rate theory as well as the change-of-numeraire technique are applied to elaborate risk neutral price dynamics in electricity markets. As a result, explicit formulas are obtained for European type derivatives such as spread, cap, floor and collar options. Through the performed historical calibration it can be seen that in the proposed model, contract volatilities close to maturity increase significantly.
For valuing swing type derivatives, which possess no closed-form solutions, an algorithm based on finite element methods is proposed. Thereby the reduction of multiple stopping time problems to a cascade of single stopping time problems is utilized. The obtained numerical results for different swing options all show a smooth and stable behavior. This allows an interpretation of the optimal exercise boundary and an analysis of the dependence of swing option prices on initial spot prices and on the number of exercise rights. A comparison of the finite element algorithm to Monte Carlo methods demonstrates the strengths of the developed numerical procedure.
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.
The market of exclusive synthesis is specialized in customized services related to research, development and the manufacturing of chemicals, intermediates and active pharmaceutical ingredients from preclinical to commercial quantities. The market of exclusive synthesis is characterized by a small number of customers and an according «exclusivity» of contracts (make-to-order). Contracts are negotiated individually (contract engineering) and usually feature a high degree of customer flexibility in terms of demand quantity and delivery date. Undoubtedly this increases customers' loyalty and satisfaction but exposes the manufacturer to uncertainty with respect to production of the different products (capacity management), which may lead to capacity shortages, and require replanning and (expensive) adjustments in production.
In view of the business functions «Sales & Marketing» and «Operations» this work focuses on the investigation of operational and contractual flexibilities, by which LES can react to the uncertainties and risks mentioned above. After a general discussion about the basic workflow at LES, the work will concentrate on different flexibility terms. This will be followed by a concept of how to valuate flexibility. It is shown that for a given contract portfolio and one bottleneck-plant the relevante LES problem can be formulated as a multistage decision problem. Given the multistage framework where for every point in time it has to be decided whether a product is to be produced now (1st stage) or will be produced at a later point in time (2nd stage), it is argued that the basic problem can be addressed in a 2-stage framework. The corresponding 2-stage approach is formulated as a stochastic mixed integer linear program. In particular the formulation includes a profit-maximizing modeling as well as a risk-minimizing formulation based on Conditional Value-at-Risk.
It turns out in the performed case study that the contractual and operational aspects are closely related and that the value of different flexibilities is determined by both the specifications of the different contracts and the operational process. In particular it will be shown that some contractual and operational flexibilities can complement one another. In view of the optimization with respect to expected profit or risk, the investigations illustrate that the valuation of flexibility yields different results for different objectives. More precisely, flexibility is generally valued more highly under a risk perspective than under a risk neutral approach. Finally, it becomes apparent, how strong decisions may vary subject to different objectives.
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.
In this work we will not continue along the line of financial mathematics but exploit the flexibility embedded in a utility's portfolio in order to value those contracts. Thereby a managerial view will be adopted by using flexibility in order to control the firm's profit and loss distribution. In the following flexibility will be interpreted in terms of risk reduction and a coherent principle will be given to price flexibility internally. The link between financial positions and the production portfolio's flexibility will be drawn by deriving a coherent framework that jointly optimizes both aspects. To be able to compare generation assets and contracts on a unified basis we identify power plants as sets of contracts in order to replicate those assets -- flexible power plants are regarded as options and inflexible ones as futures contracts. This joint optimization leads to the well-known problem in finance of portfolio optimization, which however needs to be tailored for the power market. As a result of the portfolio optimization we obtain trading and dispatch policies, i.~e.~dynamic decision rules that are specified today but determine the portfolio's composition at each point in time over the whole time horizon -- similar to a series of American put options with exercise boundary. Those so-called policies not only maximize the expected profit but also dynamically control the risk over time. This will be done with a dynamic risk engineering approach based on Conditional Value-at-Risk. The advantage of our approach is linearization resulting in a linear program that can even be solved for large instances which is truly the case for utilities.
It turns out in the performed case study that the value of flexibility can be substantial. Especially one observes that the power market does not price the embedded flexibility correctly -- it is underestimated. Therefore utilities that highly value flexibility need to buy inflexibility, such as wind farms, up to a certain degree in order to increase their value. This observation only becomes apparent when looking at the portfolio of a utility as a whole and not on an aggregated level -- subsequently flexibility is a portfolio property.
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.
By examining the routing alternatives, which are tremendously high in station regions, the feasibility problem is modeled as an independent set problem. The node set corresponds to all possible routes of the trains and two nodes are connected by an edge, if their corresponding routes are mutually exclusive. The independent set problem is then solved by applying a fixed point heuristic.
The probability that the routes of two different trains are incompatible, can be calculated by assuming certain delay patterns for arriving and departing trains. The previous model is then extended by the introduction of additional edges whose weights are set to the probability that the corresponding routes are incompatible. Stability measures are then expressed as certain properties of the extended graph. Moreover, a stability measure that is independent of any delay distributions is also introduced. In a second step, these stability measure functions are used to state different optimization problems that are then solved by a random restart local search heuristic.
In order to test the methodology, the Bern station region has been used. Depending on the applied optimization problem and the underlying delay patterns, the trains are scheduled to travel on different routes through the network. Results show that the tighter the timetable becomes the more important is the design of the railway system and the coordination of suitable track topologies, meaningful train service intentions, the dense schedules, elaborate routings, and actively managed train delays.
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.
Petri Nets are applied for the modelling of the aggregated level. First, a train service intention is depicted as a general Petri Net in which restrictions resulting from the number of available tracks and desired train connections are included. In the next step, the train sequence is chosen on stretches of parallel tracks, which corresponds to transforming the Petri Net into an event graph---a decision free Petri Net. Finally, the cycle time of the resulting tentative timetable is minimised applying Simulated Annealing.
The question of feasibility of the tentative timetable in the switch regions is modelled as an independent set problem. All possible routes of a train are depicted as nodes in a graph and nodes are connected if they correspond to routes that are mutually exclusive due to insufficient safety distance. A fixed point iteration heuristics is applied to find independent sets. Should a timetable prove to be infeasible, an additional restriction to include in the Petri Net of the aggregated level is calculated in order to remove the conflict in a renewed calculation of the tentative timetable.
The methodology was implemented and tested for the station region of Bern. Results showed that dense timetables could be constructed within an hour. The sections of the region that mainly limit the overall capacity utilisation could be detected by modifying the aggregated topology used in the top level.
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.
In order to effectively support management systems, multi-agent systems must follow the structural guidelines as proposed by cybernetics. Operationalized, the framework supports recursively structured multi-agent systems, in which the behaviors of planning, scheduling and execution can be found in every multi-agent system. Thus, a behavior determines an agent's entire action repertoire, denoted also as capabilities.
The advanced level of adaptive conduct as a source for building eigen-variety is supported in a way that agents feature multiple levels of adaptation. Owing to the multi-level adaptation process, robustness can be gained by attenuating uncertainty. In order to maintain the system's cohesion, the adjustment of agents' variety is brought about by the introduction of constraint blocks to be respected by them. The information base of agents is embodied by their knowledge bases and internal models.
Additionally, a distinction has been made between decision-related agents (management agents) and decision-supporting agents (service agents). Multi-agent systems containing management agents are being developed on the management level and are subject to performance assessments regarding their organizational structure. The primary reason for the introduction of the management level is not the analysis of algorithmic competence, but rather to examine its utilization by decision-making agents.
The conceptual development of agents is technically backed up by an implementation based on an active object approach, which grants agents communication and process autonomy. The conceptual separation of the three modeling levels is technically supported as well. However, agents must interfere on the logical level. Proxies as special types of service agents can encapsulate objects on the logical level. As a result, the proxies are able to redirect the information flow to managerial agents, which was originally connecting the objects on the logical level. Thus, these agents are, among other things, able to allocate resources differently than originally planned.
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.
The electricity market is heavily incomplete, why perfect hedges are not achievable for a number of contracts. Hence we introduce the concept of best hedge. The best hedge is found through an optimization, where risk, measured as CVaR, is minimized subject to a constraint on the expected profit. It turns out that this problem can be solved with linear programming, allowing us to handle problems of substantial size.
When a whole portfolio is considered we try to utilize our risk mandate at the best possible way. This leads us to the well-known problem in finance of portfolio optimization. However, this problem needs to be tailored for the electricity market because of the special characteristics of power portfolios. An optimal portfolio implies also an optimal dispatch of the production assets. We focus on the challenging hydro storage plant, which because of its flexible nature corresponds to a series of options. These options are however interdependent through the stored water in the reservoir. An exercise of an option, i. e. production, decreases the amount of stored water and may prohibit production at a later point in time. We develop a dynamic dispatch strategy, which takes this interdependence into account. The optimization of a portfolio consisting of a hydro storage plant and electricity contracts hence needs to derive the optimal portfolio of contracts and the optimal dispatch strategy, or with financial terms the optimal exercise conditions for the corresponding options. We solve the problem with linear programming by maximizing the expected profit over a specified time horizon under the constraint that CVaR of the portfolio may not exceed some threshold, typically determined by the risk preferences of the firm.
It turns out that a simultaneous optimization of the dispatch and the contracts is needed, since the dispatch depends on the volume risk in the entered contracts. A main result is the high value related to the operational flexibility of the hydro storage plant. By studying the dual of our linear portfolio optimization problem, we can actually quantify this value. In a performed case study it is shown that this value of flexibility can be substantial. Any valuation that does not take this operational flexibility into account may hence underestimate flexible power plants.
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.
The reconstruction problem is the problem of whether an oriented matroid can be reconstructed from some representation of it, which is here the tope graph and the cocircuit graph. It is known that tope graphs determine oriented matroids up to isomorphism. However, there is no simple graph theoretical characterization of tope graphs of oriented matroids. We strengthen the known properties of tope graphs and prove that for every element f the topes that are not bounded by f induce a connected subgraph in the tope graph. This property is later used for the design of generation methods that are based on tope graphs.
On the contrary to the tope graph case, it is known that cocircuit graphs do not determine isomorphism classes of oriented matroids. However, if every vertex is labeled by its supporting hyperplane, oriented matroids can be reconstructed up to reorientation. We present a simple algorithm which gives a constructive proof for this result. Furthermore, we extend the known results and show that the isomorphism class of a uniform oriented matroid is determined by its cocircuit graph. In addition, we present polynomial algorithms which provide a constructive proof to this result, and it is shown that the correctness of the input of the algorithms can be verified in polynomial time.
The generation problem asks for methods for listing all oriented matroids of given cardinality of the ground set and given rank. The known generation methods have been designed primarily for uniform oriented matroids in rank 3 or 4. Our methods are based on tope graph and cocircuit graph representations and generate all isomorphism classes of oriented matroids, including non-uniform ones in arbitrary rank. The generation approach incrementally extends oriented matroids by adding single elements. These single element extensions are studied in terms of localizations of graphs, which are signatures on the vertex sets that characterize single element extensions.
The first two generation methods are based on tope graphs. These methods make use of the properties of tope graphs studied earlier in this thesis, especially of the new connectedness property. The first method is a reverse search method for the generation of generalized localizations in the tope graph. In the second method graph automorphisms are used to reduce the amount of isomorphic single element extensions. Furthermore we discuss techniques which reduce multiple extension of the same oriented matroid from different minors.
Two algorithms based on cocircuit graph representations are designed similarly to those based on tope graphs. However, all these first four generation methods lack efficiency, and a reason for this is that they do not use a good characterization of localizations. Due to a result of Las Vergnas, localizations of cocircuit graphs can be characterized by sign patterns on the coline cycles in the cocircuit graph. This allows us to design a fifth method which is efficient in practice. This method is a backtracking algorithm which enumerates all sign patterns of coline cycles that are feasible in terms of the characterization. It turns out that the method is similar to a method of Bokowski and Guedes de Oliveira for the uniform case. Our method is more general as it is capable to handle all oriented matroids in arbitrary rank, including non-uniform oriented matroids. Furthermore it uses an efficient data structure and a new dynamic ordering in the backtrack procedure.
The generation methods are used for the construction of a catalog of oriented matroids. This catalog is organized using basis orientations of oriented matroids. We discuss some properties of the catalog and a method to generate the catalog. The catalog of oriented matroids can be used to find complete listings of combinatorial types of point configurations and hyperplane arrangements. We study these listing problems and discuss solution methods. Furthermore we show by an example the potential of these complete listings in resolving geometric conjectures. The listings of oriented matroids, point configurations, and hyperplane arrangements can be accessed via the Internet.
he 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.
Essentially FPH is based on a discrete dynamical system which results from iterating an appropriately defined operator. For any fixed starting point a sequence of points is generated in this way. The operator should be chosen such that this sequence converges for a large portion of starting points to a good local maximum of the problem.
By an appropriate choice of the operator in FPH, global information can be included in the solution process. Thus FPH has for certain C-SAP instances a big advantage over local search methods, which would fail in such situations due to their local vision and lack of orientation.
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. The envisioned change concerns the tasks and goals as well as the means and instruments of shop floor logistics. Within the realms of this change, firms want to shift from a product/functional view focusing on certain states of production (e.g. utilization) to a relationship/systemic view focusing on certain skills (e.g. agility). Indeed, while design efforts in the past focussed mainly on the actual performance requirements, the long-term development of the shop floor logistics are finding more and more their way into the design targets.
It should come as no surprise that this change has led to a general challenge of traditional design approaches. In fact, there is a broad acknowledgement that to improve the ability of planning and control through more powerful technical systems, and consequently, trying to convert the shop floor in an operationally closed system, is not the right path towards a sustainable success. Instead, instruments should be created, which allow an integral logistic management of the shop floor.
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.
An equilibrium with non-negative price is found when either supply equals demand or supply exceeds demand and the corresponding price is zero.
The choice to study equilibria on the level of the excess-function was motivated by a number of specific advantages including its broad applicability to different economic equilibrium problems, its simplicity of integrating existing and arbitrarily heterogeneous agents in an overall equilibrium model, and its possibility to treat agents in parallel. For MMmr (Markal-Macro multi-region), the energy-economy model studied in this work, the last two advantages are of decisive value. A serious disadvantage of this excess-based view is the possible lacking of structural properties of the excess-function which are required for proving convergence of related algorithms to equilibria.
The above mentioned advantages, however, necessitated the development of two main heuristics to solve the equilibrium problem based on the excess-function approach. The first, the Cutting Plane Method (CPM), is derived from a formulation of the equilibrium problem as a Variational Inequality Problem (VIP). The second heuristic is a fixed point method.
Contributions to the solution of equilibrium problems include the mathematical analysis of monotonicity of the excess-function, the clarification of the central role of monotonicity when applying CPM, and the treatment of unboundedness of the Lagrangian-function in some cases. This unboundedness appears in the decomposition of the optimization problem which underlies the fixed point problem. Another contribution is the discussion and extension of different strategies to prove the existence of an equilibrium. One of these strategies is finally applied to MMmr.
One of the study's empirical result is the robustness and convergence of the fixed point method when a specific dual relationship to the VIP is utilized.
The economically oriented part of this study starts with a discourse upon energyeconomy models from the perspective of CO2 emission bounds. Specific attention is given to burden sharing and the implementation of CO2 emission-permits.
Based on national energy-economy models (Markal-Macro), different possibilities to model CO2-permits are developed. First, the permits are used to integrate the national models in the international model MMmr. Second, the consequences of the different permit strategies are analyzed.
Using data from Sweden, the Netherlands and Switzerland, the two heuristics are finally successfully tested. Even though the resulting numbers must be interpreted cautiously, some interesting economic trends can be observed. Assuming a CO2 emission scenario which reduces linearly the emission by 40 % from 2000 to 2040, the average permit price is calculated to be 14 US cents per liter of fuel if discounted back to the year 2000. Furthermore, the GNP-losses are around 2 % compared to a reference case without emission bounds. In our model these losses can be reduced by one fifth if tradable permits instead of fixed national emission bounds are introduced. Significant economic di,erences were observed between nations. Because the distribution of gains and losses can be influenced directly by the initial endowment with permits, models like MMmr can be useful as a decision support tool when initial endowments or transfer payments are negotiated.
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). The more elaborated methods determine the worst case scenario by solving constrained minimization problems, where the set of feasible scenarios is generally defined by the stochastic characteristics of the market rates. Compared to other worst case techniques, the Maximum Loss methodology uses a very particular choice of feasible domains: the so-called "trust regions" cover a certain percentage of all future outcomes and their shape reflects the correlation structure of the market rates. Furthermore, ML uses a polynomial time algorithm to identify the global minimum, whereas other techniques employ rudimentary optimization procedures. The fact that the Maximum Loss computation is based on a fast and reliable algorithm allows to solve the optimization problem repeatedly, which leads to new insights into the risks of nonlinear portfolios.