Library

Description: In recent years Markov State Models (MSMs) have attracted a consid- erable amount of attention with regard to modelling conformation changes and associated function of biomolecular systems. They have been used successfully, e.g., for peptides including time-resolved spectroscopic experiments, protein function and protein folding , DNA and RNA, and ligand-receptor interaction in drug design and more complicated multivalent scenarios. In this article a novel reweighting scheme is introduced that allows to construct an MSM for certain molecular system out of an MSM for a similar system. This permits studying how molecular properties on long timescales differ between similar molecular systems without performing full molecular dynamics simulations for each system under con- sideration. The performance of the reweighting scheme is illustrated for simple test cases including one where the main wells of the respective energy landscapes are located differently and an alchemical transformation of butane to pentane where the dimension of the state space is changed.

Description: We consider problems concerning the scheduling of a set of trains on a single track. For every pair of trains there is a minimum headway, which every train must wait before it enters the track after another train. The speed of each train is also given. Hence for every schedule - a sequence of trains - we may compute the time that is at least needed for all trains to travel along the track in the given order. We give the solution to three problems: the fastest schedule, the average schedule, and the problem of quantile schedules. The last problem is a question about the smallest upper bound on the time of a given fraction of all possible schedules. We show how these problems are related to the travelling salesman problem. We prove NP-completeness of the fastest schedule problem, NP-hardness of quantile of schedules problem, and polynomiality of the average schedule problem. We also describe some algorithms for all three problems. In the solution of the quantile problem we give an algorithm, based on a reverse search method, generating with polynomial delay all Eulerian multigraphs with the given degree sequence and a bound on the number of such multigraphs. A better bound is left as an open question.

Description: We present a novel heuristic to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network's capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the nonlinearities by linear outer approximation and spatial branching. At certain nodes of the branching tree, we compute a KKT point of a nonlinear relaxation. Based on the information from the KKT point we alter some of the binary variables in a locally promising way exploiting our problem-specific structure. On a test set of real-world instances, we are able to increase the chance of identifying feasible solutions by some order of magnitude compared to standard MINLP heuristics that are already built in the general-purpose MINLP solver SCIP.

Description: Optimal control problems governed by nonlinear, time-dependent PDEs on three-dimensional spatial domains are an important tool in many fields, ranging from engineering applications to medicine. For the solution of such optimization problems, methods working on the reduced objective functional are often employed to avoid a full spatio-temporal discretization of the problem. The evaluation of the reduced gradient requires one solve of the state equation forward in time, and one backward solve of the adjoint equation. The state enters into the adjoint equation, requiring the storage of a full 4D data set. If Newton-CG methods are used, two additional trajectories have to be stored. To get numerical results that are accurate enough, in many cases very fine discretizations in time and space are necessary, leading to a significant amount of data to be stored and transmitted to mass storage. This thesis deals with the development and analysis of methods for lossy compression of such finite element solutions. The algorithms are based on a change of basis to reduce correlations in the data, combined with quantization. This is achieved by transforming the finite element coefficient vector from the nodal to the hierarchical basis, followed by rounding the coefficients to a prescribed precision. Due to the inexact reconstruction, and thus inexact data for the adjoint equation, the error induced in the reduced gradient, and reduced Hessian, has to be controlled, to not impede convergence of the optimization. Accuracy requirements of different optimization methods are analyzed, and computable error estimates for the influence of lossy trajectory storage are derived. These tools are used to adaptively control the accuracy of the compressed data. The efficiency of the algorithms is demonstrated on several numerical examples, ranging from a simple linear, scalar equation to a semi-linear system of reaction-diffusion equations. In all examples considerable reductions in storage space and bandwidth requirements are achieved, without significantly influencing the convergence behavior of the optimization methods. Finally, to go beyond pointwise error control, the hierarchical basis transform can be replaced by more sophisticated wavelet transforms. Numerical experiments indicate that choosing suitable norms for error control allows higher compression factors.

Description: Model-based optimal design of experiments (M-bODE) is a crucial step in model parametrization since it encloses a framework that maximizes the amount of information extracted from a battery of lab experiments. We address the design of M-bODE for dynamic models considering a continuous representation of the design. We use Semidefinite Programming (SDP) to derive robust minmax formulations for nonlinear models, and extend the formulations to other criteria. The approaches are demonstrated for a CSTR where a two-step reaction occurs.

Description: Cardiovascular diseases are one of the major problems in medicine today and the number of patients increases worldwide. To find the most efficient treatment, prior knowledge about function and dysfunction of the cardiovas- cular system is required and methods need to be developed that identify the disease in an early stage. Mathematical modeling is a powerful tool for prediction and investigation of cardiovascular diseases. It has been shown that the Windkessel model, being based on an analogy between electrical circuits and fluid flow, is a simple but effective method to model the human cardiovascular system. In this paper, we have applied parametric local sensitivity analysis (LSA) to a linear elastic model of the arm arteries, to find and rank sensitive param- eters that may be helpful in clinical diagnosis. A computational model for end-to-side anastomosis (superior ulnar collateral anastomosis with posterior ulnar recurrent, SUC-PUR) is carried out to study the effects of some clinically relevant haemodynamic parameters like blood flow resistance and terminal re- sistance on pressure and flow at different locations of the arm artery. In this context, we also discuss the spatio-temporal dependency of local sensitivities. The sensitivities with respect to cardiovascular parameters reveal the flow resistance and diameter of the vessels as most sensitive parameters. These parameters play a key role in diagnosis of severe stenosis and aneurysms. In contrast, wall thickness and elastic modulus are found to be less sensitive.

Description: Amalgamated graph transformation allows to define schemes of rules coinciding in common core activities and differing over additional parallel independent activities. Consequently, a rule scheme is specified by a kernel rule and a set of extending multi-rules forming an interaction scheme. Amalgamated transformations have been increasingly used in various modeling contexts. Critical Pair Analysis (CPA) can be used to show local confluence of graph transformation systems. It is an open challenge to lift the CPA to amalgamated graph transformation systems, especially since infinite many pairs of amalgamated rules occur in general. As a first step towards an efficient local confluence analysis of amalgamated graph transformation systems, we show that the analysis of a finite set of critical pairs suffices to prove local confluence.

Description: Stimulated Brillouin Scattering (SBS) is a third-order nonlinear optical effect which originates from the interplay of acoustics and optics. Recently, SBS has been harnessed in nano-photonic waveguides for applications such as narrow-linewidth lasers and Brillouin dynamic gratings [1]. Since the timescales of both phenomena differ significantly, coupled-mode equations derived from a slowly varying envelope approximation are well suited for numerical investigations of SBS [2]. We use the Relaxation Method (RM) [3] to study the optical power transfer and spatially resolved power distributions in long waveguides in the steady state limit.

Description: We employ a recently developed coarse-grained model for peptides and proteins where the effect of pH is automatically included. We explore the effect of pH in the aggregation process of the amyloidogenic peptide KTVIIE and two related sequences, using three different pH environments. Simulations using large systems (24 peptides chains per box) allow us to correctly account for the formation of realistic peptide aggregates. We evaluate the thermodynamic and kinetic implications of changes in sequence and pH upon peptide aggregation, and we discuss how a minimalistic coarse- grained model can account for these details.

Description: A chiral structure is not super-imposable with its mirror image. Most commonly found in organic molecules, chirality can also occur in other systems, such as electromagnetic fields, where circularly polarized light is the most widespread example. Chiral electromagnetic fields can be a useful tool for biosensing applications. In particular, it has been shown that chiral plasmonic nanostructures have the ability to produce strongly enhanced chiral near-fields. Recently, our group has developed chiral plasmonic nanopyramids, which have the ability to focus chiral near-fields at their tip. This could enable chiral sensing at the single-molecule level. Chiral near-fields can be characterized in terms of the “optical chirality density”. This time-even and parity-odd pseudoscalar was first derived by Lipkin and was found to follow a conservation law analogous to the energy conservation of electromagnetic fields. More recently, Tang and Cohen identified the physical meaning of the “optical chirality density” as the degree of asymmetry in the excitation rate of a chiral molecule. However, how this near-field interpretation of the optical chirality could translate into the far-field is not well understood. Here, we formulate a far-field interpretation by investigating the conservation law for optical chirality in matter, and performing time-averaging in analogy to Poynting’s Theorem. In parallel to extinction energy, we define the “global chirality” as the sum of chirality dissipation within a material and the chirality flux leaving the system. With finite-element simulations, we place a dipole source at locations of enhanced local chirality and investigate the global chirality and ellipticity of emitted light in the far-field. Interestingly, we find that lossy materials with a complex dielectric function have the ability to generate global chirality when excited by achiral light. In particular, chiral plasmonic nanostructures are found to act as effective global chirality generators. The global interpretation of optical chirality provides a useful tool for biosensing applications with chiral plasmonic nanostructures, where the detection is routinely performed in the far-field.

Description: Railway transportation and in particular train timetabling is one of the basic and source application areas of combinatorial optimization and integer programming. We will discuss two well established modeling techniques for the train timetabling problem. In this paper we focus on one major ingredient - the bounding by dual relaxations. We compare two classical dual relaxations of large scale time expanded train timetabling problems - the Lagrangean Dual and Lagrangean Decomposition. We discuss the convergence behavior and show limitations of the Lagrangean Decomposition approach for a configuration based model. We introduce a third dualization approach to overcome those limitations. Finally, we present promising preliminary computational experiments that show that our new approach indeed has superior convergence properties.

Description: We present two algorithms to solve a 3-objective optimization problem arising in telecommunications access network planning, the k-Architecture Connected Facility Location Problem. The methods can also be used to solve any 3-objective integer linear programming model and can be extended to the multiobjective case. We give some exemplary computations using small and medium-sized instances for our problem.

Description: Integrated treatment of hitherto individual steps in the planning process of public transit companies discloses opportunities to reduce costs and to improve the quality of service. The arising integrated planning problems are complex and their solution requires the development of novel mathematical methods. This article proposes a mathematical optimization approach to integrate duty scheduling and rostering in public transit, which allows to significantly increase driver satisfaction at almost zero cost. This is important in order to to increase the attractiveness of the driver profession. The integration is based on coupling the subproblems by duty templates, which, compared to a coupling by duties, drastically reduces the problem complexity.

Description: We derive a set of design guidelines and a figure of merit to aid the engineering process of on-chip waveguides for strong Stimulated Brillouin Scattering (SBS). To this end, we examine the impact of several types of loss on the total amplification of the Stokes wave that can be achieved via SBS. We account for linear loss and nonlinear loss of third order (two-photon absorption, 2PA) and fifth order, most notably 2PA-induced free carrier absorption (FCA). From this, we derive an upper bound for the output power of continuous-wave Brillouin-lasers and show that the optimal operating conditions and maximal realisable Stokes amplification of any given waveguide structure are determined by a dimensionless parameter ℱ involving the SBS-gain and all loss parameters. We provide simple expressions for optimal pump power, waveguide length and realisable amplification and demonstrate their utility in two example systems. Notably, we find that 2PA-induced FCA is a serious limitation to SBS in silicon and germanium for wavelengths shorter than 2200nm and 3600nm, respectively. In contrast, three-photon absorption is of no practical significance.

Description: In this paper, we present a systematic transition scheme for a large class of ordinary differential equations (ODEs) into Boolean networks. Our transition scheme can be applied to any system of ODEs whose right hand sides can be written as sums and products of monotone functions. It performs an Euler-like step which uses the signs of the right hand sides to obtain the Boolean update functions for every variable of the corresponding discrete model. The discrete model can, on one hand, be considered as another representation of the biological system or, alternatively, it can be used to further the analysis of the original ODE model. Since the generic transformation method does not guarantee any property conservation, a subsequent validation step is required. Depending on the purpose of the model this step can be based on experimental data or ODE simulations and characteristics. Analysis of the resulting Boolean model, both on its own and in comparison with the ODE model, then allows to investigate system properties not accessible in a purely continuous setting. The method is exemplarily applied to a previously published model of the bovine estrous cycle, which leads to new insights regarding the regulation among the components, and also indicates strongly that the system is tailored to generate stable oscillations.

Description: Markov State Modelling as a concept for a coarse grained description of the essential kinetics of a molecular system in equilibrium has gained a lot of atten- tion recently. The last 10 years have seen an ever increasing publication activity on how to construct Markov State Models (MSMs) for very different molecular systems ranging from peptides to proteins, from RNA to DNA, and via molecu- lar sensors to molecular aggregation. Simultaneously the accompanying theory behind MSM building and approximation quality has been developed well be- yond the concepts and ideas used in practical applications. This article reviews the main theoretical results, provides links to crucial new developments, outlines the full power of MSM building today, and discusses the essential limitations still to overcome.

Description: The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal.

Description: Time series classification tries to mimic the human understanding of similarity. When it comes to long or larger time series datasets, state-of-the-art classifiers reach their limits because of unreasonably high training or testing times. One representative example is the 1-nearest-neighbor dynamic time warping classifier (1-NN DTW) that is commonly used as the benchmark to compare to. It has several shortcomings: it has a quadratic time complexity in the time series length and its accuracy degenerates in the presence of noise. To reduce the computational complexity, early abandoning techniques, cascading lower bounds, or recently, a nearest centroid classifier have been introduced. Still, classification times on datasets of a few thousand time series are in the order of hours. We present our Bag-Of-SFA-Symbols in Vector Space classifier that is accurate, fast and robust to noise. We show that it is significantly more accurate than 1-NN DTW while being multiple orders of magnitude faster. Its low computational complexity combined with its good classification accuracy makes it relevant for use cases like long or large amounts of time series or real-time analytics.

Description: To counteract the antagonistic relationship between milk yield and fertility in dairy cow, a deeper understanding of the underlying biological mechanisms is required. For this purpose, we study physiological networks related to reproduction and metabolism in dairy cows. We interactively develop dynamic, mechanistic models by fitting the models to experimental data and mechanistic knowledge. We have already developed models for potassium balance and hormonal regulation of fertility in the dairy cow, which will briefly be reviewed here. The main focus of this article is a glucose-insulin model currently developed by us. This model links the bovine hormonal cycle and the potassium balance to glucose and thus to energy metabolism. The models can be applied in scientific research, education, experimental planning, drug development and production on farms.

Description: Facial trauma or congenital malformation of bones of the skull may degrade both skeletal integrity as well as the esthetic appearance. For the attending surgeon a prediction of the esthetic outcome of a bone replacement or augmentation implant insertion is challenging. Therefore, it would be advantageous if we were able to compute an implant shape from a given desired outcome. This task presents the main focus of this thesis. Besides the development of a model for the implant shape design problem, this work is concerned with the efficient solution and optimization of realistic models. This includes recent material laws for different soft tissue types as well as complex geometries attained from medical image data. The implant shape design problem can be described as an optimal control problem with constraints given by the necessary optimality conditions in polyconvex hyperelasticity with nonlinear pressure-type boundary conditions. Important theoretical results, such as existence of solutions and higher regularity, are currently not available for such problems. Based on the existence result for polyconvex materials laws, existence of solutions of the nonconvex optimal control problem is proven for the case of a simpler Neumann boundary condition. Due to the “impossible convexity” and the high nonlinearity of hyperelastic material laws the numerical solution of the arising problems is difficult. In this regard, an affine covariant composite step method for nonconvex, equality constrained optimization is presented. The corresponding globalization strategy is based on the affine covariant Newton method for underdetermined systems and cubic regularization methods for unconstrained optimization problems. The linear systems arising from the discretization of constrained optimization problems are described by saddle point matrices. The efficient solution of these equality systems by conjugate gradient methods for convex and nonconvex problems is discussed. Moreover, an error estimator that fits into the affine covariant setting is presented. The presented composite step method was implemented in the C++ finite element library Kaskade 7. The performance of the algorithm is demonstrated on several examples. Next to simple optimization problems, with admissible set given through models of linear and nonlinear heat transfer, we give four examples with nonconvex, hyperelastic constraints.

Description: This paper describes three presolving techniques for solving mixed integer programming problems (MIPs) that were implemented in the academic MIP solver SCIP. The task of presolving is to reduce the problem size and strengthen the formulation, mainly by eliminating redundant information and exploiting problem structures. The first method fixes continuous singleton columns and extends results known from duality fixing. The second analyzes and exploits pairwise dominance relations between variables, whereas the third detects isolated subproblems and solves them independently. The performance of the presented techniques is demonstrated on two MIP test sets. One contains all benchmark instances from the last three MIPLIB versions, while the other consists of real-world supply chain management problems. The computational results show that the combination of all three presolving techniques almost halves the solving time for the considered supply chain management problems. For the MIPLIB instances we obtain a speedup of 20 % on affected instances while not degrading the performance on the remaining problems.

Description: Background. The chemical master equation is the fundamental equation of stochastic chemical kinetics. This differential-difference equation describes temporal evolution of the probability density function for states of a chemical system. A state of the system, usually encoded as a vector, represents the number of entities or copy numbers of interacting species, which are changing according to a list of possible reactions. It is often the case, especially when the state vector is high-dimensional, that the number of possible states the system may occupy is too large to be handled computationally. One way to get around this problem is to consider only those states that are associated with probabilities that are greater than a certain threshold level. Results. We introduce an algorithm that significantly reduces computational resources and is especially powerful when dealing with multi-modal distributions. The algorithm is built according to two key principles. Firstly, when performing time integration, the algorithm keeps track of the subset of states with significant probabilities (essential support). Secondly, the probability distribution that solves the equation is parametrised with a small number of coefficients using collocation on Gaussian radial basis functions. The system of basis functions is chosen in such a way that the solution is approximated only on the essential support instead of the whole state space. Discussion. In order to demonstrate the effectiveness of the method, we consider four application examples: a) the self-regulating gene model, b) the 2-dimensional bistable toggle switch, c) a generalisation of the bistable switch to a 3-dimensional tristable problem, and d) a 3-dimensional cell differentiation model that, depending on parameter values, may operate in bistable or tristable modes. In all multidimensional examples the manifold containing the system states with significant probabilities undergoes drastic transformations over time. This fact makes the examples especially challenging for numerical methods. Conclusions. The proposed method is a new numerical approach permitting to approximately solve a wide range of problems that have been hard to tackle until now. A full representation of multi-dimensional distributions is recovered. The method is especially attractive when dealing with models that yield solutions of a complex structure, for instance, featuring multi-stability. Electronic version: http://www.biomedcentral.com/1752-0509/9/67

Description: In this paper, we describe an OAIS aligned data model and architectural design that enables us to archive digital infor- mation with a single core preservation workflow. The data model allows for normalization of metadata from widely var- ied domains to ingest and manage the submitted information utilizing only one generalized toolchain and be able to create access platforms that are tailored to designated data con- sumer communities. The design of the preservation system is not dependent on its components to continue to exist over its lifetime, as we anticipate changes both of technology and environment. The initial implementation depends mainly on the open-source tools Archivematica, Fedora/Islandora, and iRODS.

Description: Rolling stock, i.e., rail vehicles, are among the most expensive and limited assets of a railway company. They must be used efficiently applying optimization techniques. One important aspect is re-optimization, which is the topic that we consider in this paper. We propose a template concept that allows to compute cost minimal rolling stock rotations under a large variety of re-optimization requirements. Two examples, involving a connection template and a rotation template, are discussed. An implementation within the rolling stock rotation optimizer rotor and computational results for scenarios provided by DB Fernverkehr AG, one of the leading railway operators in Europe, are presented.

Description: Multivalent sugar/protein interactions are well-known to proceed through different binding modes 1-5 which in turn can be described by their binding kinetics 3-5. This study provides additional insight into the association and dissociation reaction rates of complex multivalent sugar/protein interactions. Binding kinetics of recently introduced multivalent precision glycomacromolecules 6-8 to Concanavalin A (Con A) were studied by " kinetic Isothermal Titration Calorimetry " (kinITC) 9-11. The effect of multivalency is evaluated by comparing rate constants of glycomacromolecules obtaining the same and different valency of mannose ligands and by variation of the overall backbone properties, such as hydrophilic/ hydrophoboc. In addition, binding kinetics were studied using different conformations of Con A (homodimer vs.-tetramer) and thus a different protein valency. Our results show that precision glycomacromolecule/Con A binding proceeds non-cooperatively. Further, association and dissociation rates are mainly described by intermolecular complex formation. Together with the so-called functional valency, we can discriminate between " bound " and " unbound " states for macroscopic on-and off-rates, even for such complex glycooligomer/protein systems. By comparing e.g. a mono-to a divalent glycomacromolecule for their binding to dimeric Con A, we see a lower dissociation rate for the latter. As both bind monovalently to Con A, this is a strong indication for a statistical rebinding event. Further, there is a strong dependence of multivalent binding kinetics on the ligand density of glycomacromolecules as well as the Con A conformation and thus the overall on-and off-rates.

Description: Spectral deferred correction methods for solving stiff ODEs are known to converge rapidly towards the collocation limit solution on equidistant grids, but show a much less favourable contraction on non-equidistant grids such as Radau-IIa points. We interprete SDC methods as fixed point iterations for the collocation system and propose new DIRK-type sweeps for stiff problems based on purely linear algebraic considerations. Good convergence is recovered also on non-equidistant grids. The properties of different variants are explored on a couple of numerical examples.

Description: This paper considers the optimal control of tuberculosis through education, diagnosis campaign and chemoprophylaxis of latently infected. A mathematical model which includes important components such as undiagnosed infectious, diagnosed infectious, latently infected and lost-sight infectious is formulated. The model combines a frequency dependent and a density dependent force of infection for TB transmission. Through optimal control theory and numerical simulations, a cost-effective balance of two different intervention methods is obtained. Seeking to minimize the amount of money the government spends when tuberculosis remain endemic in the Cameroonian population, Pontryagin's maximum principle is used to characterize the optimal control. The optimality system is derived and solved numerically using the forward-backward sweep method (FBSM). Results provide a framework for designing cost-effective strategies for diseases with multiple intervention methods. It comes out that combining chemoprophylaxis and education, the burden of TB can be reduced by 80 % in 10 years.

Description: Reversible Markov chains are the basis of many applications. However, computing transition probabilities by a finite sampling of a Markov chain can lead to truncation errors. Even if the original Markov chain is reversible, the approximated Markov chain might be non-reversible and will lose important properties, like the real valued spectrum. In this paper, we show how to find the closest reversible Markov chain to a given transition matrix. It turns out that this matrix can be computed by solving a convex minimization problem.

Description: The Graduate-Level Research in Industrial Projects (G-RIPS) Program provides an opportunity for high-achieving graduate-level students to work in teams on a real-world research project proposed by a sponsor from industry or the public sector. Each G-RIPS team consists of four international students (two from the US and two from European universities), an academic mentor, and an industrial sponsor. This is the report of the Rail-Lab project on the definition and integration of robustness aspects into optimizing rolling stock schedules. In general, there is a trade-off for complex systems between robustness and efficiency. The ambitious goal was to explore this trade-off by implementing numerical simulations and developing analytic models. In rolling stock planning a very large set of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacity, and regularity aspects, have to be considered in an integrated model. General hypergraphs provide the modeling power to tackle those requirements. Furthermore, integer programming approaches are able to produce high quality solutions for the deterministic problem. When stochastic time delays are considered, the mathematical programming problem is much more complex and presents additional challenges. Thus, we started with a basic variant of the deterministic case, i.e., we are only considering hypergraphs representing vehicle composition and regularity. We transfered solution approaches for robust optimization from the airline industry to the setting of railways and attained a reasonable measure of robustness. Finally, we present and discuss different methods to optimize this robustness measure.

Description: The different approaches to solve the validation of nomination problem presented in the previous chapters are evaluated computationally in this chapter. Each approach is analyzed individually, as well as the complete solvers for these problems. We demonstrate that the presented approaches can successfully solve large-scale real-world instances.

Description: We consider a stationary discrete-time linear process that can be observed by a finite number of sensors. The experimental design for the observations consists of an allocation of available resources to these sensors. We formalize the problem of selecting a design that maximizes the information matrix of the steady-state of the Kalman filter, with respect to a standard optimality criterion, such as $D-$ or $A-$optimality. This problem generalizes the optimal experimental design problem for a linear regression model with a finite design space and uncorrelated errors. Finally, we show that under natural assumptions, a steady-state optimal design can be computed by semidefinite programming.

Description: One quarter of Europe’s energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi billion Euro business. Therefore, automatic planning tools that support the decision process are desired. We model the topology extension problem in gas networks by a mixed-integer nonlinear program (MINLP). This gives rise to a so-called active transmission problem, a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. In this article we offer novel sufficient conditions for proving the infeasibility of this active transmission problem. These conditions can be expressed in the form of a mixed-integer program (MILP), i.e., the infeasibility of a non-convex NLP can be certified by solving an MILP. These results provide an efficient bounding procedure in a branch-and-bound algorithm. Our computational results demonstrate a substantial speed-up for the necessary computations.

Description: Network virtualization techniques allow for the coexistence of many virtual networks (VNs) jointly sharing the resources of an underlying substrate network. The Virtual Network Embedding problem (VNE) arises when looking for the most profitable set of VNs to embed onto the substrate. In this paper, we address the offline version of the problem. We propose a Mixed-Integer Linear Programming formulation to solve it to optimality which accounts for acceptance and rejection of virtual network requests, allowing for both splittable and unsplittable (single path) routing schemes. Our formulation also considers a Rent-at-Bulk (RaB) model for the rental of substrate capacities where economies of scale apply. To better emphasize the importance of RaB, we also compare our method to a baseline one which only takes RaB into account a posteriori, once a solution to VNE, oblivious to RaB, has been found. Computational experiments show the viability of our approach, stressing the relevance of addressing RaB directly with an exact formulation.

Description: Energy storages can be of great value when added to power grids. They introduce the possibility to store and release energy whenever this is favorable. This is particularly relevant, for example, if power supply is volatile (as is the case with renewable energy) and the network is small (so that there are few other nodes that might balance fluctuations in consumption or production). We present models and methods from mathematical optimization for computing an optimized storage schedule for this purpose. We look at alternative optimization objectives, such as smallest possible peak load, low energy costs, or the close approximation of a prescribed load curve. The optimization needs to respect general operational and economic constraints as well as limitations in the use of storage, which are imposed by the chosen storage technology. We therefore introduce alternative approaches for modeling the non-linear properties of energy storages and study their impact on the efficiency of the optimization process. Finally, we present a computational study with batteries as storage devices. We use this to highlight the trade-off between solution quality and computational tractability. A version of the model for the purpose of leveling peaks and instabilities has been implemented into a control system for an office-building smart grid scenario.

Description: In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.

Description: We propose a composite step method, designed for equality constrained optimization with partial differential equations. Focus is laid on the construction of a globalization scheme, which is based on cubic regularization of the objective and an affine covariant damped Newton method for feasibility. We show finite termination of the inner loop and fast local convergence of the algorithm. We discuss preconditioning strategies for the iterative solution of the arising linear systems with projected conjugate gradient. Numerical results are shown for optimal control problems subject to a nonlinear heat equation and subject to nonlinear elastic equations arising from an implant design problem in craniofacial surgery.

Description: We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex.

Description: Wir illustrieren anhand des Liniennetzes der Stadt Potsdam das Potenzial mathematischer Methoden der Angebotsplanung. Wir zeigen, dass das "bestmögliche" Verkehrsangebot stark von planerischen Vorgaben beeinflusst wird, mit denen man die Erreichung unterschiedlicher und teilweise gegenläufiger Ziele steuern kann. Die Komplexität des Systems führt zum Auftreten von Rückkoppelungseffekten, die man nicht mit Hilfe von Daumenregeln beherrschen kann. Vielmehr ist der Einsatz moderner Planungsverfahren in einer interdisziplinären Zusammenarbeit von politischen Entscheidungsträgern, Verkehrsingenieuren und Mathematikern notwendig, um die aktuellen Herausforderungen in der Verkehrsplanung zu meistern. Der Artikel dokumentiert einen Beitrag zum 7. ÖPNV Innovationskongress des Ministeriums für Verkehr und Infrastruktur des Landes Baden-Württemberg, der vom 9.-11. März 2015 in Freiburg stattfand.

Description: Wireless body area networks are wireless sensor networks whose adoption has recently emerged and spread in important healthcare applications, such as the remote monitoring of health conditions of patients. A major issue associated with the deployment of such networks is represented by energy consumption: in general, the batteries of the sensors cannot be easily replaced and recharged, so containing the usage of energy by a rational design of the network and of the routing is crucial. Another issue is represented by traffic uncertainty: body sensors may produce data at a variable rate that is not exactly known in advance, for example because the generation of data is event-driven. Neglecting traffic uncertainty may lead to wrong design and routing decisions, which may compromise the functionality of the network and have very bad effects on the health of the patients. In order to address these issues, in this work we propose the first robust optimization model for jointly optimizing the topology and the routing in body area networks under traffic uncertainty. Since the problem may result challenging even for a state-of-the-art optimization solver, we propose an original optimization algorithm that exploits suitable linear relaxations to guide a randomized fixing of the variables, supported by an exact large variable neighborhood search. Experiments on realistic instances indicate that our algorithm performs better than a state-of-the-art solver, fast producing solutions associated with improved optimality gaps.

Description: Amalgamated graph transformation allows to define schemes of rules coinciding in common core activities and differing over additional parallel independent activities. Consequently, a rule scheme is specified by a kernel rule and a set of extending multi-rules forming an interaction scheme. Amalgamated transformations have been increasingly used in various modeling contexts. Critical Pair Analysis (CPA) can be used to show local confluence of graph transformation systems. It is an open challenge to lift the CPA to amalgamated graph transformation systems, especially since infinite many pairs of amalgamated rules occur in general. As a first step towards an efficient local confluence analysis of amalgamated graph transformation systems, we show that the analysis of a finite set of critical pairs suffices to prove local confluence.

Description: Wir illustrieren anhand des Liniennetzes der Stadt Potsdam das Potenzial mathematischer Methoden der Angebotsplanung. Wir zeigen, dass das "bestmögliche" Verkehrsangebot stark von planerischen Vorgaben beeinflusst wird, mit denen man die Erreichung unterschiedlicher und teilweise gegenläufiger Ziele steuern kann. Die Komplexität des Systems führt zum Auftreten von Rückkoppelungseffekten, die man nicht mit Hilfe von Daumenregeln beherrschen kann. Vielmehr ist der Einsatz moderner Planungsverfahren in einer interdisziplinären Zusammenarbeit von politischen Entscheidungsträgern, Verkehrsingenieuren und Mathematikern notwendig, um die aktuellen Herausforderungen in der Verkehrsplanung zu meistern. Der Artikel dokumentiert einen Beitrag zum 7. ÖPNV Innovationskongress des Ministeriums für Verkehr und Infrastruktur des Landes Baden-Württemberg, der vom 9.-11. März 2015 in Freiburg stattfand.

Description: Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively.

Description: This book is a comprehensive explanation of graph and model transformation. It contains a detailed introduction, including basic results and applications of the algebraic theory of graph transformations, and references to the historical context. Then in the main part the book contains detailed chapters on M-adhesive categories, M-adhesive transformation systems, and multi-amalgamated transformations, and model transformation based on triple graph grammars. In the final part of the book the authors examine application of the techniques in various domains, including chapters on case studies and tool support. The book will be of interest to researchers and practitioners in the areas of theoretical computer science, software engineering, concurrent and distributed systems, and visual modelling.

Description: Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP, we demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice.

Description: A commercial aircraft cannot freely use the available airspace but instead has to stick to a three-dimensional network of segments similar to a car in a road network. In this network it faces several variable and interdependent costs in the form of travel time, fuel consumption and overflight charges. These are also highly dependent on other factors such as weather conditions, aircraft performance, take-off time and weight as well as the changing availability of elements in the graph. This is further complicated by the distinction of separate flight phases that challenge the standard notion of a graph with predetermined nodes and arcs. Therefore when trying to find either a distance, fuel, time or cost minimal trajectory for a specific aircraft between an origin and a destination airport, one faces a very complex shortest path problem in the airway network graph that even for strong implifications is often NP-hard. This thesis will focus on exploring the costs that occur in this graph and that are associated with the aircraft performance. Here we will rely on actual performance and weather data supplied by Lufthansa Systems AG in Frankfurt and analyze whether they meet the requirements necessary for common algorithms such as the First-in, First-out property. Since it is vital for any shortest path algorithm to have a fast and accurate way of determining the costs in the graph, we will face two problems regarding the calculation of aircraft performance during cruise as well as the calculation of the so-called air distance. So far these problems have been approached by the industry with rudimentary approximative methods. We will reformulate them as initial value problems and try to find good approximations using both general Runge-Kutta methods as well as a novel approach which relies on finding piecewise linear approximations of some primitive integrals in pre-processing. Computations will show that these approaches deliver fast and accurate results.

Description: Given a directed, acyclic graph, a source and a sink node, and a set of forbidden pairs of arcs, the path avoiding forbidden pairs (PAFP) problem is to find a path that connects the source and sink nodes and contains at most one arc from each forbidden pair. The general version of the problem is NP-hard, but it becomes polynomially solvable for certain topological configurations of the pairs. We present the first polyhedral study of the PAFP problem. We introduce a new family of valid inequalities for the PAFP polytope and show that they are sufficient to provide a complete linear description in the special case where the forbidden pairs satisfy a disjointness property. Furthermore, we show that the number of facets of the PAFP polytope is exponential in the size of the graph, even for the case of a single forbidden pair.

Description: In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.

Description: A conventional by hand construction and parameterization of a polymer model for the purpose of molecular simulations can quickly become very workintensive and time-consuming. Using the example of polyglycerol, I present a polymer decompostion strategy yielding a set of five monomeric residues that are convenient for an instantaneous assembly and subsequent force field simulation of a polyglycerol polymer model. Force field parameters have been developed in accordance with the classical Amber force field. Partial charges of each unit were fitted to the electrostatic potential using quantumchemical methods and slightly modified in order to guarantee a neutral total polymer charge. In contrast to similarly constructed models of amino acid and nucleotide sequences, the glycerol building blocks may yield an arbitrary degree of bifurcations depending on the underlying probabilistic model. The iterative development of the overall structure as well as the relation of linear to branching units is controlled by a simple Markov model which is presented with few algorithmic details. The resulting polymer is highly suitable for classical explicit water molecular dynamics simulations on the atomistic level after a structural relaxation step. Moreover, the decomposition strategy presented here can easily be adopted to many other (co)polymers.

Description: With the advent of high-performance computing, Bayesian methods are becoming increasingly popular tools for the quantification of uncertainty throughout science and industry. Since these methods can impact the making of sometimes critical decisions in increasingly complicated contexts, the sensitivity of their posterior conclusions with respect to the underlying models and prior beliefs is a pressing question to which there currently exist positive and negative answers. We report new results suggesting that, although Bayesian methods are robust when the number of possible outcomes is finite or when only a finite number of marginals of the data-generating distribution are unknown, they could be generically brittle when applied to continuous systems (and their discretizations) with finite information on the data-generating distribution. If closeness is defined in terms of the total variation (TV) metric or the matching of a finite system of generalized moments, then (1) two practitioners who use arbitrarily close models and observe the same (possibly arbitrarily large amount of) data may reach opposite conclusions; and (2) any given prior and model can be slightly perturbed to achieve any desired posterior conclusion. The mechanism causing brittleness/robustness suggests that learning and robustness are antagonistic requirements, which raises the possibility of a missing stability condition when using Bayesian inference in a continuous world under finite information.

Description: The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances that can be used by researchers in the field of gas transport. The advantages are that researchers save time by using these instances and that different models and algorithms can be compared on the same specified test sets. The library instances are encoded in an XML format. In this paper, we explain this format and present the instances that are available in the library.

Description: Spawned by practical applications, numerous variations of the classical Steiner tree problem in graphs have been studied during the last decades. Despite the strong relationship between the different variants, solution approaches employed so far have been prevalently problem-specific. In contrast, we pursue a general-purpose strategy resulting in a solver able to solve both the classical Steiner tree problem and ten of its variants without modification. These variants include well-known problems such as the prize-collecting Steiner tree problem, the maximum-weight connected subgraph problem or the rectilinear minimum Steiner tree problem. Bolstered by a variety of new methods, most notably reduction techniques, our solver is not only of unprecedented versatility, but furthermore competitive or even superior to specialized state-of-the-art programs for several Steiner problem variants.

Description: In the Resource-Constrained Project Scheduling Problem (RCPSP) a set of jobs is planned subject to resource- and precedence constraints. The objective is to minimize the makespan, that is the time when all jobs have been completed. There exist several Mixed-Integer-Programming (MIP) models in order to solve the problem. Most common models are based on time-discretization. In this case, the scheduling horizon is split into unit size intervals and each job gets assigned a unique starting interval. The drawback of time-discrete models is the computational intractability for large scheduling horizons or fine discretizations. In this connection, this thesis deals with compact MIP models where the model size is independent of the scheduling horizon. In addition to two compact models from the literature, we present two new compact models. We investigate their induced polyhedra and deduce an inclusion hierarchy via linear transformations. Moreover, we give a combinatorial interpretation of these transformations. Furthermore, we study a class of valid cutting planes for the compact models, which are known as cover inequalities. In order to strengthen these cutting planes we introduce a lifting algorithm that is independent of the model size. Subsequently, we examine lower bounds for the RCPSP from linear programming. Based on a linear transformation, we reveal a connection between two approaches from the literature. For one model we generate strong cutting planes that are obtained from a primal-dual relation between the models. Two cutting plane algorithms are derived. Likewise, we show that similar cutting planes can be transferred to the compact MIP models. Our models have been implemented, tested and evaluated on the instances of the PSPLIB problem library.

Description: For the solution of optimal control problems governed by nonlinear parabolic PDEs, methods working on the reduced objective functional are often employed to avoid a full spatio-temporal discretization of the problem. The evaluation of the reduced gradient requires one solve of the state equation forward in time, and one backward solve of the ad-joint equation. The state enters into the adjoint equation, requiring the storage of a full 4D data set. If Newton-CG methods are used, two additional trajectories have to be stored. To get numerical results which are accurate enough, in many case very fine discretizations in time and space are necessary, which leads to a significant amount of data to be stored and transmitted to mass storage. Lossy compression methods were developed to overcome the storage problem by reducing the accuracy of the stored trajectories. The inexact data induces errors in the reduced gradient and reduced Hessian. In this paper, we analyze the influence of such a lossy trajectory compression method on Newton-CG methods for optimal control of parabolic PDEs and design an adaptive strategy for choosing appropriate quantization tolerances.

Description: After we discussed approaches to validate nominations and to verify bookings, we consider possible future research paths. This includes determining technical capacities and planning of network extensions.

Description: In this article we present a new idea for approximating exit rates for diffusion processes living in a craggy landscape. We are especially interested in the exit rates of a process living in a metastable regions. Due to the fact that Monte Carlo simulations perform quite poor and are very computational expensive in this setting we create several similar situations with a smoothed potential. For this we introduce a new parameter $\lambda \in [0,1]$ ($\lambda = 1$ very smoothed potential, $\lambda=0$ original potential) into the potential which controls the influence the smoothing. We then sample the exit rate for different parameters $\lambda$ the exit rate from a given region. Due to the fact that $\lambda$ is connected to the exit rate we can use this dependency to approximate the real exit rate. The method can be seen as something between hyperdynamics and temperature accelerated MC.

Description: The task of periodic timetabling is to schedule the trips in a public transport system by determining arrival and departure times at every station such that travel and transfer times are minimized. To date, the optimization literature generally assumes that passengers do not respond to changes in the timetable, i.e., the passenger routes are fixed. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We show that different routing models have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. to different routing models can be arbitrarily large. Computations on a real-world instance for the city of Wuppertal substantiate the theoretical findings. These results indicate the existence of untapped optimization potentials that can be used to improve the efficiency of public transport systems.

Description: Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively.

Description: We investigate the 3-architecture Connected Facility Location Problem arising in the design of urban telecommunication access networks integrating wired and wireless technologies. We propose an original optimization model for the problem that includes additional variables and constraints to take into account wireless signal coverage represented through signal-to-interference ratios. Since the problem can prove very challenging even for modern state-of-the art optimization solvers, we propose to solve it by an original primal heuristic that combines a probabilistic fixing procedure, guided by peculiar Linear Programming relaxations, with an exact MIP heuristic, based on a very large neighborhood search. Computational experiments on a set of realistic instances show that our heuristic can find solutions associated with much lower optimality gaps than a state-of-the-art solver.

Description: This thesis investigates the shortest path problem with pair constraints or the pair constraint problem (PCP) for short. We consider two types of pair constraints, namely forbidden pairs and binding pairs consisting of two distinct vertices each. A path respects a forbidden pair if it uses at most one of the two vertices and it respects a binding pair (x,y) if it uses also y, if x is used. Within this thesis, we bring together and compare several formulations and variants of the pair constraint problem and their complexities. We also collect existing recursive algorithms and present their running times. Most of the presented contributions only consider forbidden pairs. We introduce a new recursive algorithm also handling binding pairs and prove its theoretical complexity of O(n^4). We implemented the algorithm and tested it on real-world instances provided by Lufthansa Systems AG. Therefore we needed to develop a heuristic translating the real-world data into an instance of the shortest path problem with pair constraints. This heuristic is presented as well as all computational results. In Chapter 4, we start investigating the associated polytope of an integer program formulation of the shortest path problem with pair constraints. For the case of one forbidden or binding pair, we find a complete linear description of the associated polytope. We prove that the number of facets grows exponentially in |V| even in these simple cases. However, separation is still possible in polynomial time. The complete linear description can be extended to the case of contiguously disjoint pairs.

Description: This paper describes how we solved 12 previously unsolved mixed-integer program- ming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances.

Description: Planning and operating railway transportation systems is an extremely hard task due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. Because of that, however, mathematical models and optimization techniques can result in large gains for both railway cus- tomers and operators, e.g., in terms of cost reductions or service quality improvements. In the last years a large and growing group of researchers in the OR community have devoted their attention to this domain devel- oping mathematical models and optimization approaches to tackle many of the relevant problems in the railway planning process. However, there is still a gap to bridge between theory and practice, with a few notable exceptions. In this paper we address three success stories, namely, long-term freight train routing (part I), mid-term rolling stock rotation planning (part II), and real-time train dispatching (part III). In each case, we describe real-life, successful implementations. We will dis- cuss the individual problem setting, survey the optimization literature, and focus on particular aspects addressed by the mathematical models. We demonstrate on concrete applications how mathematical optimization can support railway planning and operations. This gives proof that math- ematical optimization can support the planning of rolling stock resources. Thus, mathematical models and optimization can lead to a greater effi- ciency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry.

Description: Railway transportation and in particular train timetabling is one of the basic and source application areas of combinatorial optimization and integer programming. We will discuss two well established modeling techniques for the train timetabling problem. In this paper we focus on one major ingredient - the bounding by dual relaxations. We compare two classical dual relaxations of large scale time expanded train timetabling problems - the Lagrangean Dual and Lagrangean Decomposition. We discuss the convergence behavior and show limitations of the Lagrangean Decomposition approach for a configuration based model. We introduce a third dualization approach to overcome those limitations. Finally, we present promising preliminary computational experiments that show that our new approach indeed has superior convergence properties.

Description: Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.

Description: We consider problems concerning the scheduling of a set of trains on a single track. For every pair of trains there is a minimum headway, which every train must wait before it enters the track after another train. The speed of each train is also given. Hence for every schedule - a sequence of trains - we may compute the time that is at least needed for all trains to travel along the track in the given order. We give the solution to three problems: the fastest schedule, the average schedule, and the problem of quantile schedules. The last problem is a question about the smallest upper bound on the time of a given fraction of all possible schedules. We show how these problems are related to the travelling salesman problem. We prove NP-completeness of the fastest schedule problem, NP-hardness of quantile of schedules problem, and polynomiality of the average schedule problem. We also describe some algorithms for all three problems. In the solution of the quantile problem we give an algorithm, based on a reverse search method, generating with polynomial delay all Eulerian multigraphs with the given degree sequence and a bound on the number of such multigraphs. A better bound is left as an open question.

Description: The resource constrained assignment problem (RCAP) is to find a minimal cost partition of the nodes of a directed graph into cycles such that a resource constraint is fulfilled. The RCAP has its roots in rolling stock rotation optimization where a railway timetable has to be covered by rotations, i.e., cycles. In that context, the resource constraint corresponds to maintenance constraints for rail vehicles. Moreover, the RCAP generalizes variants of the vehicle routing problem (VRP). The paper contributes an exact branch and bound algorithm for the RCAP and, primarily, a straightforward algorithmic concept that we call regional search (RS). As a symbiosis of a local and a global search algorithm, the result of an RS is a local optimum for a combinatorial optimization problem. In addition, the local optimum must be globally optimal as well if an instance of a problem relaxation is computed. In order to present the idea for a standardized setup we introduce an RS for binary programs. But the proper contribution of the paper is an RS that turns the Hungarian method into a powerful heuristic for the resource constrained assignment problem by utilizing the exact branch and bound. We present computational results for RCAP instances from an industrial cooperation with Deutsche Bahn Fernverkehr AG as well as for VRP instances from the literature. The results show that our RS provides a solution quality of 1.4 % average gap w.r.t. the best known solutions of a large test set. In addition, our branch and bound algorithm can solve many RCAP instances to proven optimality, e.g., almost all asymmetric traveling salesman and capacitated vehicle routing problems that we consider.

Description: Energy field is one of the practical areas to which optimization can contribute significantly. In this chapter, the application of mixed-integer linear programming (MILP) approaches to optimal design and operation of distributed energy systems is described. First, the optimal design and operation problems are defined, and relevant previous work is reviewed. Then, an MILP method utilizing the hierarchical relationship between design and operation variables is presented. In the optimal design problem, integer variables are used to express the types, capacities, numbers, operation modes, and on/off states of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. The presented method can change the enumeration tree for the branching and bounding procedures, and can search the optimal solution very efficiently. Finally, future work in relation to this method is described.

Description: Kulturerbe- und Gedächtnisinstitutionen sammeln, bewahren, dokumentieren und vermitteln Zeugnisse und Objekte des kulturellen Erbes. Die Digitalisierung eröffnet für alle diese Handlungsfelder neue Möglichkeiten, aber gleichzeitig auch neue Herausforderungen. Diese berühren sowohl organisatorische und technische als auch rechtliche Aspekte. Gerade letztere sind oft mit schwer kalkulierbaren Risiken für die Kultureinrichtungen behaftet. Die vorliegende Handreichung, die von iRights im Auftrag von digiS erstellt wurde, soll eine Einführung für die Mitarbeiter der Kulturinstitutionen in die Themen Urheber- und Leistungsschutzrechte sein. Sie soll für rechtliche Risiken sensibilisieren und Handlungsspielräume aufzeigen. Die bisherige Version 1.1 aus dem letzten Jahr wurde nun überarbeitet.

Description: Mixed-integer nonlinear programming (MINLP) comprises the broad class of finite-dimensional mathematical optimization problems from mixed-integer linear programming and global optimization. The combination of the two disciplines allows us to construct more accurate models of real-world systems, while at the same time it increases the algorithmic challenges that come with solving them. This thesis presents new methods that improve the numerical reliability and the computational performance of global MINLP solvers. Since state-of-the-art algorithms for nonconvex MINLP fundamentally rely on solving linear programming (LP) relaxations, we address numerical accuracy directly for LP by means of LP iterative refinement: a new algorithm to solve linear programs to arbitrarily high levels of precision. The thesis is supplemented by an exact extension of the LP solver SoPlex, which proves on average 1.85 to 3 times faster than current state-of-the-art software for solving general linear programs exactly over the rational numbers. These methods can be generalized to quadratic programming. We study their application to numerically difficult multiscale LP models for metabolic networks in systems biology. To improve the computational performance of LP-based MINLP solvers, we show how the expensive, but effective, bound-tightening technique called optimization-based bound tightening can be approximated more efficiently via feasibility-based bound tightening. The resulting implementation increases the number of instances that can be solved and reduces the average running time of the MINLP solver SCIP by 17-19% on hard mixed-integer nonlinear programs. Last, we present branching rules that exploit the presence of nonlinear integer variables, i.e., variables both contained in nonlinear terms and required to be integral. The new branching rules prefer integer variables when performing spatial branching, and favor variables in nonlinear terms when resolving integer infeasibility. They reduce the average running time of SCIP by 17% on affected instances. Most importantly, all of the new methods enable us to solve problems which could not be solved before, either due to their numerical complexity or because of limited computing resources.

Description: Let the design of an experiment be represented by an $s-$dimensional vector $w$ of weights with nonnegative components. Let the quality of $w$ for the estimation of the parameters of the statistical model be measured by the criterion of $D-$optimality, defined as the $m$th root of the determinant of the information matrix $M(w)=\sum_{i=1}^s w_i A_i A_i^T$, where $A_i$,$i=1,\ldots,s$ are known matrices with $m$ rows. In this paper, we show that the criterion of $D-$optimality is second-order cone representable. As a result, the method of second-order cone programming can be used to compute an approximate $D-$optimal design with any system of linear constraints on the vector of weights. More importantly, the proposed characterization allows us to compute an exact $D-$optimal design, which is possible thanks to high-quality branch-and-cut solvers specialized to solve mixed integer second-order cone programming problems. Our results extend to the case of the criterion of $D_K-$optimality, which measures the quality of $w$ for the estimation of a linear parameter subsystem defined by a full-rank coefficient matrix $K$. We prove that some other widely used criteria are also second-order cone representable, for instance, the criteria of $A-$, $A_K$-, $G-$ and $I-$optimality. We present several numerical examples demonstrating the efficiency and general applicability of the proposed method. We show that in many cases the mixed integer second-order cone programming approach allows us to find a provably optimal exact design, while the standard heuristics systematically miss the optimum.

Description: System Dynamic models describe physical, technical, economical, or social systems using differential and algebraic equations. In their purest form, these models are intended to describe the evolution of a system from a given initial state. In many applications, it is possible to intervene with the system in order to obtain a desired dynamic or a certain outcome in the end. On the mathematical side, this leads to control problems, where aside from the simulation one has to find optimal intervention functions over time that maximize a specific objective function. Using a dynamical model for the utilization of a natural nonrenewable resource of Behrens as a demonstrator example, we present two main mathematical solution strategies. They are distinguished by the quality certificate on their respective solution: one leads to proven local optimal solution, and the other technique yields proven global optimal solutions. We present implementational and numerical issues, and a comparison of both methods.

Description: We propose an approach to solve the validation of nominations problem using mixed-integer nonlinear programming (MINLP) methods. Our approach handles both the discrete settings and the nonlinear aspects of gas physics. Our main contribution is an innovative coupling of mixed-integer (linear) programming (MILP) methods with nonlinear programming (NLP) that exploits the special structure of a suitable approximation of gas physics, resulting in a global optimization method for this type of problem.