Library

Description: In this paper we present a novel extended formulation for the line planning problem that is based on what we call “configurations” of lines and frequencies. Configurations account for all possible options to provide a required transportation capacity on an infrastructure edge. The proposed configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, MIR, and multicover inequalities. These theoretical findings can be confirmed in computational results. Further, we show how this concept can be generalized to define configurations for subsets of edges; the generalized model implies additional inequalities from the line planning literature.

Description: One of the main goals of mathematical modelling in systems biology related to medical applications is to obtain patient-specific parameterisations and model predictions. In clinical practice, however, the number of available measurements for single patients is usually limited due to time and cost restrictions. This hampers the process of making patient-specific predictions about the outcome of a treatment. On the other hand, data are often available for many patients, in particular if extensive clinical studies have been performed. Using these population data, we propose an iterative algorithm for contructing an informative prior distribution, which then serves as the basis for computing patient-specific posteriors and obtaining individual predictions. We demonsrate the performance of our method by applying it to a low-dimensional parameter estimation problem in a toy model as well as to a high-dimensional ODE model of the human menstrual cycle, which represents a typical example from systems biology modelling.

Description: Dieser Beitrag stellt mögliche Ansätze zur Reduktion der Rechenzeit von linearen Optimierungsproblemen mit energiewirtschaftlichem Anwendungshintergrund vor. Diese Ansätze bilden im Allgemeinen die Grundlage für konzeptionelle Strategien zur Beschleunigung von Energiesystemmodellen. Zu den einfachsten Beschleunigungsstrategien zählt die Verkleinerung der Modelldimensionen, was beispielsweise durch Ändern der zeitlichen, räumlichen oder technologischen Auflösung eines Energiesystemmodells erreicht werden kann. Diese Strategien sind zwar häufig ein Teil der Methodik in der Energiesystemanalyse, systematische Benchmarks zur Bewertung ihrer Effektivität werden jedoch meist nicht durchgeführt. Die vorliegende Arbeit adressiert genau diesen Sachverhalt. Hierzu werden Modellinstanzen des Modells REMix in verschiedenen Größenordnungen mittels einer Performance-Benchmark-Analyse untersucht. Die Ergebnisse legen zum einen den Schluss nahe, dass verkürzte Betrachtungszeiträume das größte Potential unter den hier analysierten Strategien zur Reduktion von Rechenzeit bieten. Zum anderen empfiehlt sich die Verwendung des Barrier-Lösungsverfahrens mit multiplen Threads unter Vernachlässigung des Cross-Over.

Description: We utilize the theory of coherent sets to build Markov state models for non- equilibrium molecular dynamical systems. Unlike for systems in equilibrium, “meta- stable” sets in the non-equilibrium case may move as time evolves. We formalize this concept by relying on the theory of coherent sets, based on this we derive finite-time non-stationary Markov state models, and illustrate the concept and its main differences to equilibrium Markov state modeling on simple, one-dimensional examples.

Description: Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT. Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs. We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17% to 19% on average. Most importantly, more instances can be solved when using OBBT.

Description: We present a numerical method to characterize the symmetry properties of photonic crystal (PhC) modes based on field distributions, which themselves can be obtained numerically. These properties can be used to forecast specific features of the optical response of such systems, e.g. which modes are allowed to couple to external radiation fields. We use 2D PhCs with a hexagonal lattice of holes in dielectric as an example and apply our technique to reproduce results from analytical considerations. Further, the method is extended to fully vectorial problems in view of 3D PhCs and PhC slabs, its functionality is demonstrated using test cases and, finally, we provide an efficient implementation. The technique can thus readily be applied to output data of all band structure computation methods or even be embedded – gaining additional information about the mode symmetry.

Description: We prove characterizations of the existence of perfect f-matchings in uniform mengerian and perfect hypergraphs. Moreover, we investigate the f-factor problem in balanced hypergraphs. For uniform balanced hypergraphs we prove two existence theorems with purely combinatorial arguments, whereas for non-uniform balanced hypergraphs we show that the f-factor problem is NP-hard.

Description: The Rosetta probe around comet 67P/Churyumov–Gerasimenko (67P) reveals an anisotropic dust distribution of the inner coma with jet-like structures. The physical processes leading to jet formation are under debate, with most models for cometary activity focusing on localized emission sources, such as cliffs or terraced regions. Here we suggest, by correlating high-resolution simulations of the dust environment around 67P with observations, that the anisotropy and the background dust density of 67P originate from dust released across the entire sunlit surface of the nucleus rather than from few isolated sources. We trace back trajectories from coma regions with high local dust density in space to the non-spherical nucleus and identify two mechanisms of jet formation: areas with local concavity in either two dimensions or only one. Pits and craters are examples of the first case; the neck region of the bi-lobed nucleus of 67P is an example of the latter case. The conjunction of multiple sources, in addition to dust released from all other sunlit areas, results in a high correlation coefficient (~0.8) of the predictions with observations during a complete diurnal rotation period of 67P.

Description: Viele Kulturinstitutionen nutzen bereits die Möglichkeiten, die ihnen die Digitalisierung und das Internet bieten. Bestände werden digitalisiert und digital aufbereitet, ganze Kunstgattungen gibt es bereits digital. Im heutigen 21. Jahrhundert existieren viele Kultureinrichtungen, wie Museen, Archive und Bibliotheken, bereits seit 100 Jahren oder länger. Doch was ist notwendig, um Institutionen, die vor der Erfindung des Fernsehens etabliert wurden, in der heutigen von Technologien bestimmten Welt bei ihren gesellschaftlichen Aufgaben zu unterstützen? Der vorliegende Text gibt eine Einführung in offene Kulturdaten und zeigt Möglichkeiten auf, wie Kultureinrichtungen von der offenen Bereitstellung ihrer digitalen Bestände profitieren und durch neue Kooperationen kulturinteressierte Menschen stärker an sich binden können. Es wird erklärt, was die Cultural Commons ausmacht und wie Kulturinstitutionen bei der Öffnung ihrer Daten vorgehen können. Um den gesellschaftlichen und institutionellen Wert frei nutzbarer Sammlungsbestände zu verdeutlichen, werden realisierte Projekte basierend auf offenen Kulturdaten im lokalen und internationalen Kontext vorgestellt.

Description: We propose an algorithm to approximate the distribution of the completion time (makespan) and the tardiness costs of a project, when durations are lognormally distributed. This problem arises naturally for the optimization of surgery scheduling, where it is very common to assume lognormal procedure times. We present an analogous of Clark's formulas to compute the moments of the maximum of a set of lognormal variables. Then, we use moment matching formulas to approximate the earliest starting time of each activity of the project by a shifted lognormal variable. This approach can be seen as a lognormal variant of a state-of-the-art method used for the statistical static timing analysis (SSTA) of digital circuits. We carried out numerical experiments with instances based on real data from the application to surgery scheduling. We obtained very promising results, especially for the approximation of the mean overtime in operating rooms, for which our algorithm yields results of a similar quality to Monte-Carlo simulations requiring an amount of computing time several orders of magnitude larger.

Description: This article extends the framework of Bayesian inverse problems in infinite-dimensional parameter spaces, as advocated by Stuart (Acta Numer. 19:451–559, 2010) and others, to the case of a heavy-tailed prior measure in the family of stable distributions, such as an infinite-dimensional Cauchy distribution, for which polynomial moments are infinite or undefined. It is shown that analogues of the Karhunen–Loève expansion for square-integrable random variables can be used to sample such measures. Furthermore, under weaker regularity assumptions than those used to date, the Bayesian posterior measure is shown to depend Lipschitz continuously in the Hellinger metric upon perturbations of the misfit function and observed data.

Description: Given a sequence of Cauchy-distributed random variables defined by a sequence of location parameters and a sequence of scale parameters, we consider another sequence of random variables that is obtained by perturbing the location or scale parameter sequences. Using a result of Kakutani on equivalence of infinite product measures, we provide sufficient conditions for the equivalence of laws of the two sequences.

Description: Strong and directionally specific forward scattering from optical nanoantennas is of utmost importance for various applications in the broader context of photovoltaics and integrated light sources. Here, we outline a simple yet powerful design principle to perceive a nanoantenna that provides directional scattering into a higher index substrate based on the interference of multiple electric dipoles. A structural implementation of the electric dipole distribution is possible using plasmonic nanoparticles with a fairly simple geometry, i.e. two coupled rectangular nanoparticles, forming a dimer, on top of a substrate. The key to achieve directionality is to choose a sufficiently large size for the nanoparticles. This promotes the excitation of vertical electric dipole moments due to the bi-anisotropy of the nanoantenna. In turn, asymmetric scattering is obtained by ensuring the appropriate phase relation between the vertical electric dipole moments. The scattering strength and angular spread for an optimized nanoantenna can be shown to be broadband and robust against changes in the incidence angle. The scattering directionality is maintained even for an array configuration of the dimer. It only requires the preferred scattering direction of the isolated nanoantenna not to be prohibited by interference.

Description: In many applications one is interested to compute transition probabilities of a Markov chain. This can be achieved by using Monte Carlo methods with local or global sampling points. In this article, we analyze the error by the difference in the $L^2$ norm between the true transition probabilities and the approximation achieved through a Monte Carlo method. We give a formula for the error for Markov chains with locally computed sampling points. Further, in the case of reversible Markov chains, we will deduce a formula for the error when sampling points are computed globally. We will see that in both cases the error itself can be approximated with Monte Carlo methods. As a consequence of the result, we will derive surprising properties of reversible Markov chains.

Description: In many applications one is interested to compute transition probabilities of a Markov chain. This can be achieved by using Monte Carlo methods with local or global sampling points. In this article, we analyze the error by the difference in the $L^2$ norm between the true transition probabilities and the approximation achieved through a Monte Carlo method. We give a formula for the error for Markov chains with locally computed sampling points. Further, in the case of reversible Markov chains, we will deduce a formula for the error when sampling points are computed globally. We will see that in both cases the error itself can be approximated with Monte Carlo methods. As a consequence of the result, we will derive surprising properties of reversible Markov chains.

Description: Given a sequence of Cauchy-distributed random variables defined by a sequence of location parameters and a sequence of scale parameters, we consider another sequence of random variables that is obtained by perturbing the location or scale parameter sequences. Using a result of Kakutani on equivalence of infinite product measures, we provide sufficient conditions for the equivalence of laws of the two sequences.

Description: In this paper we present a novel extended formulation for the line planning problem that is based on what we call “configurations” of lines and frequencies. Configurations account for all possible options to provide a required transportation capacity on an infrastructure edge. The proposed configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, MIR, and multicover inequalities. These theoretical findings can be confirmed in computational results. Further, we show how this concept can be generalized to define configurations for subsets of edges; the generalized model implies additional inequalities from the line planning literature.

Description: Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration.

Description: In this paper, we address the Energetic Reasoning propagation rule for the Cumulative Scheduling Problem (CuSP). An energetic reasoning propagation algorithm is called exact, if it computes the maximum possible energetic reasoning propagation for all the jobs. The currently best known exact energetic reasoning algorithm has complexity O(n^3). In this paper, we present a new exact energetic reasoning propagation algorithm with improved complexity of O(n^2 \log^2 n).

Description: The primary goal of this paper is to study the coupling of monodomain and eikonal models for the numerical simulation of cardiac electrophysiology. Eikonal models are nonlinear elliptic equations describing the excitation time of the cardiac tissue. They are often used as very fast approximations for monodomain or bidomain models - parabolic reaction-diffusion systems describing the excitation wavefront in terms of ionic currents. The excitation front is a thin region with high gradients, whereas excitation times vary over larger domains. Hence, eikonal equations can be solved on much coarser grids than monodomain equations. Moreover, as eikonal models are not time-dependent, no time integration is needed. Eikonal models are derived from monodomain models making additional assumptions and using certain approximations. While generally the approximation is rather good, several specific situations are not well captured by eikonal models. We consider coupling the two models, i.e. using the monodomain model in regions where more accurate results or the shape of the wavefront are needed, and the eikonal model in the remaining parts of the domain, where the excitation time is sufficient. Restricting the monodomain simulation to a small subdomain reduces the computational effort considerably. Numerical methods for the simulation of the individual models are presented, with the finite element method as the main ingredient. Coupling conditions as well as algorithms for implementing the coupling are explained. The approximation quality and efficiency of the coupled model is illustrated on simple geometries using an Aliev-Panfilov membrane model.

Description: This paper investigates the criterion of long-term average costs for a Markov decision process (MDP) which is not permanently observable. Each observation of the process produces a fixed amount of \textit{information costs} which enter the considered performance criterion and preclude from arbitrarily frequent state testing. Choosing the \textit{rare} observation times is part of the control procedure. In contrast to the theory of partially observable Markov decision processes, we consider an arbitrary continuous-time Markov process on a finite state space without further restrictions on the dynamics or the type of interaction. Based on the original Markov control theory, we redefine the control model and the average cost criterion for the setting of information costs. We analyze the constant of average costs for the case of ergodic dynamics and present an optimality equation which characterizes the optimal choice of control actions and observation times. For this purpose, we construct an equivalent freely observable MDP and translate the well-known results from the original theory to the new setting.

Description: Accurate modeling and numerical simulation of reaction kinetics is a topic of steady interest. We consider the spatiotemporal chemical master equation (ST-CME) as a model for stochastic reaction-diffusion systems that exhibit properties of metastability. The space of motion is decomposed into metastable compartments and diffusive motion is approximated by jumps between these compartments. Treating these jumps as first-order reactions, simulation of the resulting stochastic system is possible by the Gillespie method. We present the theory of Markov state models (MSM) as a theoretical foundation of this intuitive approach. By means of Markov state modeling, both the number and shape of compartments and the transition rates between them can be determined. We consider the ST-CME for two reaction-diffusion systems and compare it to more detailed models. Moreover, a rigorous formal justification of the ST-CME by Galerkin projection methods is presented.

Description: We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.

Description: The primary goal of this paper is to study the coupling of monodomain and eikonal models for the numerical simulation of cardiac electrophysiology. Eikonal models are nonlinear elliptic equations describing the excitation time of the cardiac tissue. They are often used as very fast approximations for monodomain or bidomain models - parabolic reaction-diffusion systems describing the excitation wavefront in terms of ionic currents. The excitation front is a thin region with high gradients, whereas excitation times vary over larger domains. Hence, eikonal equations can be solved on much coarser grids than monodomain equations. Moreover, as eikonal models are not time-dependent, no time integration is needed. Eikonal models are derived from monodomain models making additional assumptions and using certain approximations. While generally the approximation is rather good, several specific situations are not well captured by eikonal models. We consider coupling the two models, i.e. using the monodomain model in regions where more accurate results or the shape of the wavefront are needed, and the eikonal model in the remaining parts of the domain, where the excitation time is sufficient. Restricting the monodomain simulation to a small subdomain reduces the computational effort considerably. Numerical methods for the simulation of the individual models are presented, with the finite element method as the main ingredient. Coupling conditions as well as algorithms for implementing the coupling are explained. The approximation quality and efficiency of the coupled model is illustrated on simple geometries using an Aliev-Panfilov membrane model.

Description: We consider the problem of enforcing a toll on a transportation network with limited inspection resources. We formulate a game theoretic model to optimize the allocation of the inspectors, taking the reaction of the network users into account. The model includes several important aspects for practical operation of the control strategy, such as duty types for the inspectors. In contrast to an existing formulation using flows to describe the users' strategies we choose a path formulation and identify dominated user strategies to significantly reduce the problem size. Computational results suggest that our approach is better suited for practical instances.

Description: Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MILP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format, illustrating its capabilities and structure through examples. The certificate format is designed with simplicity in mind and is composed of a list of statements that can be sequentially verified using a limited number of simple yet powerful inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of mixed-integer linear programming instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.

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 customers 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 developing 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 (e.g. Cacchiani et al., 2014; Borndörfer et al., 2010), with a few notable exceptions. In this paper we address three individual 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 discuss 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 mathematical optimization can support the planning of railway resources. Thus, mathematical models and optimization can lead to a greater efficiency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry.

Description: The operation of railways gives rise to many fundamental optimization problems. One of these problems is to cover a given set of timetabled trips by a set of rolling stock rotations. This is well known as the Rolling Stock Rotation Problem (RSRP). Most approaches in the literature focus primarily on modeling and minimizing the operational costs. However, an essential aspect for the industrial application is mostly neglected. As the RSRP follows timetabling and line planning, where periodicity is a highly desired property, it is also desired to carry over periodic structures to rolling stock rotations and following operations. We call this complex requirement regularity. Regularity turns out to be of essential interest, especially in the industrial scenarios that we tackle in cooperation with DB Fernverkehr AG. Moreover, regularity in the context of the RSRP has not been investigated thoroughly in the literature so far. We introduce three regularity patterns to tackle this requirement, namely regular trips, regular turns, and regular handouts. We present a two-stage approach in order to optimize all three regularity patterns. At first, we integrate regularity patterns into an integer programming approach for the minimization of the operational cost of rolling stock rotations. Afterwards regular handouts are computed. These handouts present the rotations of the first stage in the most regular way. Our computational results (i.e., rolling stock rotations evaluated by planners of DB Fernverkehr AG) show that the three regularity patterns and our concept are a valuable and, moreover, an essential contribution to rolling stock rotation optimization.

Description: We consider a novel partitioning of the set of non-dominated points for general multi-objective integer programs with $k$ objectives. The set of non-dominated points is partitioned into a set of non-dominated points whose efficient solutions are also efficient for some restricted subproblem with one less objective; the second partition comprises the non-dominated points whose efficient solutions are inefficient for any of the restricted subproblems. We show that the first partition has the nice property that it yields finite rectangular boxes in which the points of the second partition are located.

Description: When estimating a probability density within the empirical Bayes framework, the non-parametric maximum likelihood estimate (NPMLE) usually tends to overfit the data. This issue is usually taken care of by regularization - a penalization term is subtracted from the marginal log-likelihood before the maximization step, so that the estimate favors smooth solutions, resulting in the so-called maximum penalized likelihood estimation (MPLE). The majority of penalizations currently in use are rather arbitrary brute-force solutions, which lack invariance under transformation of the parameters(reparametrization) and measurements. This contradicts the principle that, if the underlying model has several equivalent formulations, the methods of inductive inference should lead to consistent results. Motivated by this principle and using an information-theoretic point of view, we suggest an entropy-based penalization term that guarantees this kind of invariance. The resulting density estimate can be seen as a generalization of reference priors. Using the reference prior as a hyperprior, on the other hand, is argued to be a poor choice for regularization. We also present an insightful connection between the NPMLE, the cross entropy and the principle of minimum discrimination information suggesting another method of inference that contains the doubly-smoothed maximum likelihood estimation as a special case.

Description: We introduce the shortest path problem with crossing costs (SPPCC), a shortest path problem in a directed graph, in which the objective function is the sum of arc weights and crossing costs. The former are independently paid for each arc used by the path, the latter need to be paid every time the path intersects certain sets of arcs, which we call regions. The SPPCC generalizes not only the classical shortest path problem but also variants such as the resource constrained shortest path problem and the minimum label path problem. We use the SPPCC to model the flight trajectory optimization problem with overflight costs. In this paper, we provide a comprehensive analysis of the problem. In particular, we identify efficient exact and approximation algorithms for the cases that are most relevant in practice.

Description: A railway operator creates (rolling stock) rotations in order to have a precise master plan for the operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply traverses a set of operational days while covering trips of the timetable. As it is well known, the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging and still a topical research subject. Nevertheless, we study a completely different but strongly related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In our industrial application at DB Fernverkehr AG, the handout is exactly as important as the rotation itself. Moreover, it turns out that also other European railway operators use exactly the same methodology (but not terminology). Since a rotation can have many handouts of different quality, we show how to compute optimal ones through an integer program (IP) by standard software. In addition, a construction as well as an improvement heuristic are presented. Our computational results show that the heuristics are a very reliable standalone approach to quickly find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a computational comparison to the IP approach.

Description: One of the main goals of mathematical modelling in systems medicine related to medical applications is to obtain patient-specific parameterizations and model predictions. In clinical practice, however, the number of available measurements for single patients is usually limited due to time and cost restrictions. This hampers the process of making patient-specific predictions about the outcome of a treatment. On the other hand, data are often available for many patients, in particular if extensive clinical studies have been performed. Therefore, before applying Bayes’ rule separately to the data of each patient (which is typically performed using a non-informative prior), it is meaningful to use empirical Bayes methods in order to construct an informative prior from all available data. We compare the performance of four priors - a non-informative prior and priors chosen by nonparametric maximum likelihood estimation (NPMLE), by maximum penalized lilelihood estimation (MPLE) and by doubly-smoothed maximum likelihood estimation (DS-MLE) - by applying them to a low-dimensional parameter estimation problem in a toy model as well as to a high-dimensional ODE model of the human menstrual cycle, which represents a typical example from systems biology modelling.

Description: We present a coarse-to-fine column generation approach for the workforce scheduling of teams. In addition we present a price-and-branch approach and a new hypergraph formulation for a specific workforce team problem, called the Toll Enforcement Problem.

Description: In the context of gas transmission in decoupled entry-exit systems, many approaches to determine the network capacity are based on the evaluation of realistic and severe transport situations. In this paper, we review the Reference Point Method, which is an algorithm used in practice to generate a set of scenarios using the so-called transport moment as a measure for severity. We introduce a new algorithm for finding severe transport situations that considers an actual routing of the flow through the network and is designed to handle issues arising from cyclic structures in a more dynamical manner. Further, in order to better approximate the physics of gas, an alternative, potential based flow formulation is proposed. The report concludes with a case study based on data from the benchmark library GasLib.

Description: In this paper, we compare several approaches for the problem of gas network expansions using loops, that is, to build new pipelines in parallel to existing ones. We present different model formulations for the problem of continuous loop expansions as well as discrete loop expansions. We then analyze problem properties, such as the structure and convexity of the underlying feasible regions. The paper concludes with a computational study comparing the continuous and the discrete formulations.

Description: Die Grundsätze für den Erwerb überregionaler Lizenzen, die von der Deutschen Forschungsgemeinschaft(DFG) gefördert werden (sog. Allianz-Lizenzen), beinhalten spezifische Regelungen zum Open Access. Damit wird DFG-seitig sichergestellt, dass bei Abschluss von Allianz-Verträgen die inkludierten Inhalte sowohl von Autoren als auch von den lizenznehmenden Einrichtungen unter vorteilhafteren Konditionen gegenüber den üblichen Self Archiving Policies (z.B. Verlagsversion, verkürzte Embargofrist) in Repositorien archiviert und veröffentlicht werden dürfen. Die Erfahrung der seit 2011 getätigten Allianz-Abschlüsse zeigt allerdings, dass der Kreis berechtigter Autorinnen und Autoren und Institutionen eigenständig kaum Gebrauch von ihren hierdurch erhaltenen Open-Access-Rechten macht. Entsprechend liegt ein großer Schatz wissenschaftlicher Literatur bei den Verlagen, der noch zu heben ist. Das bewilligte DFG-Projekt DeepGreen (Ausschreibung „Open-Access-Transformation“ von 2014) zielt darauf ab, die vereinbarten Open-Access-Konditionen der Allianz-Lizenzen auf technischer Ebene komfortabel auszugestalten und, wenn möglich, zu automatisieren, so dass nicht mehr Autorinnen und Autoren oder die hierzu berechtigten Bibliotheken die Publikationen manuell in Open-Access-Repositorien einpflegen müssen, sondern die Verlage selbst zyklisch über definierte Schnittstellen abliefern. Dazu bauen die Projektpartner (Universitätsbibliothek Erlangen-Nürnberg, Universitätsbibliothek TU Berlin, Helmholtz Open Science Koordinationsbüro am Deutschen GeoForschungsZentrum, Bayerische Staatsbibliothek München sowie die Verbünde Bibliotheksverbund Bayern und KooperativerBibliotheksverbund Berlin-Brandenburg) ein Dark Archive namens DeepGreen auf, in das teilnehmende Allianz-Lizenz-Verlage Publikationen und Metadaten einspeisen. DeepGreen soll im Anschluss als Datendrehscheibe für berechtigte Open-Access-Repositorien dienen. Als Pilotpartner konnten die Verlage Karger und SAGE gewonnen werden. Der vorliegende Aufsatz stellt das Projekt und den aktuellen Stand der Arbeiten vor.

Description: Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points.

Description: SAP's decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this paper we describe our coordinated efforts to ensure that the performance of the underlying solution algorithms matches the complexity of the large supply chain problems and tight time limits encountered in practice.

Description: In constraint programming, energetic reasoning constitutes a powerful start time propagation rule for cumulative scheduling problems (CuSP). In this paper, we first present an improved time interval checking algorithm that is derived from a polyhedral model. In a second step, we extend this algorithm to an energetic reasoning propagation algorithm with complexity O(n^2 log n) where n denotes the number of jobs. The key idea is based on a new sweep line subroutine that efficiently evaluates the relevant time intervals for all jobs. In particular, our algorithm yields at least one possible energetic reasoning propagation for each job. Finally, we show that on the vast number of relevant time intervals our approach yields the maximum possible propagation according to the energetic reasoning rule.

Description: This paper proposes a highly integrated solution approach for rolling stock planning problems in the context of long distance passenger traffic between cities. The main contributions are a generic hypergraph-based mixed-integer programming model for the considered rolling stock rotation problem and an integrated algorithm for its solution. The newly developed algorithm is able to handle a large spectrum of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacities, and regularity aspects. We show that our approach has the power to produce rolling stock rotations that can be implemented in practice. In this way, the rolling stock rotations at the largest German long distance operator Deutsche Bahn Fernverkehr AG could be optimized by an automated system utilizing advanced mathematical programming techniques.

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: Real World networks often exhibit a significant number of vertices which are sparsely and irregularly connected to other vertices in the network. For clustering theses networks with a model based algorithm, we propose the Stochastic Block Model with Irrelevant Vertices (SBMIV) for weighted net- works. We propose an original Variational Bayesian Expectation Maximiza- tion inference algorithm for the SBMIV which is an advanced version of our Blockloading algorithm for the Stochastic Block Model. We introduce a model selection criterion for the number of clusters of the SBMIV which is based on the lower variational bound of the model likelihood. We propose a fully Bayesian inference process, based on plausible informative priors, which is independent of other algorithms for preprocessing start values for the cluster assignment of vertices. Our inference methods allow for a multi level identification of irrelevant vertices which are hard to cluster reliably ac- cording to the SBM. We demonstrate that our methods improve on the normal Stochastic Block model by applying it to to Earthquake Networks which are an example of networks with a large number of sparsely and irregularly con- nected vertices.

Description: Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.

Description: The antiepileptic drug carbamazepine (CBZ) and its main metabolites carbamazepine-10,11-epoxide (EP-CBZ) and 10,11-dihydro-10,11-dihydroxy-carbamazepine (DiOH-CBZ) were chosen as test substances to assess chronic toxicity on the non-biting midge Chironomus riparius. All three substances were tested in a 40-day sediment full life cycle test (according to OECD 233) in which mortality, emergence, fertility, and clutch size were evaluated. In addition, these parameters were integrated into the population growth rate to reveal population relevant effects. With an LC50 of 0.203 mg/kg (time-weighted mean), the metabolite EP-CBZ was significantly more toxic than the parent substance CBZ (LC50: 1.11 mg/kg). Especially mortality, emergence, and fertility showed to be sensitive parameters under the exposure to CBZ and EP-CBZ. By using classical molecular dynamics (MD) simulations, the binding of CBZ to the ecdysone receptor was investigated as one possible mode of action but showed to be unlikely. The second metabolite DiOH-CBZ did not show any effects within the tested concentration rage (0.171 – 1.22 mg/kg). Even though CBZ was less toxic compared to EP-CBZ, CBZ is found in the environment at much higher concentrations and causes therefore a higher potential risk for sediment dwelling organisms compared to its metabolites. Nevertheless, the current study illustrates the importance of including commonly found metabolites into the risk assessment of parent substances.

Description: We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that the sum of all expected delays and all running times is minimal. Previous research concentrated on microscopic train routings for junctions or inside major stations. Only recently approaches were developed to tackle larger corridors or even networks. We investigate the routing problem from a strategic perspective, calculating the routes in a macroscopic transportation network of Deutsche Bahn AG. In this context, macroscopic refers to an aggregation of complex and large real-world structures into fewer network elements. Moreover, the departure and arrival times of freight trains are approximated. The problem has a strategic character since it asks only for a coarse routing through the network without the precise timings. We provide a mixed-integer nonlinear programming (MINLP) formulation for the FTRP, which is a multicommodity flow model on a time-expanded graph with additional routing constraints. The model’s nonlinearities originate from an algebraic approximation of the delays of the trains on the arcs of the network by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model (MILP) by piecewise linear approximation. The latter is solved by a state-of-the art MILP solver for various real-world test instances.

Description: The application of advanced imaging techniques for the ultrasonic inspection of inhomogeneous anisotropic materials like austenitic and dissimilar welds requires information about acoustic wave propagation through the material, in particular travel times between two points in the material. Forward ray tracing is a popular approach to determine traveling paths and arrival times but is ill suited for inverse problems since a large number of rays have to be computed in order to arrive at prescribed end points. In this contribution we discuss boundary value problems for acoustic rays, where the ray path between two given points is determined by solving the eikonal equation. The implementation of such a two point boundary value ray tracer for sound field simulations through an austenitic weld is described and its efficiency as well as the obtained results are compared to those of a forward ray tracer. The results are validated by comparison with experimental results and commercially available UT simulation tools. As an application, we discuss an implementation of the method for SAFT (Synthetic Aperture Focusing Technique) reconstruction. The ray tracer calculates the required travel time through the anisotropic columnar grain structure of the austenitic weld. There, the formulation of ray tracing as a boundary value problem allows a straightforward derivation of the ray path from a given transducer position to any pixel in the reconstruction area and reduces the computational cost considerably.

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: We consider the problem of a price-taker generating company that wants to select energy offering strategies for its generation units, to maximize the profit while considering the uncertainty of market price. First, we review central references available in literature about the use of Robust Optimization (RO) for price-uncertain energy offering, pointing out how they can expose to the risk of suboptimal and even infeasible offering. We then propose a new RO method for energy offering that overcomes all the limits of other RO methods. We show the effectiveness of the new method on realistic instances provided by our industrial partners, getting very high increases in profit. Our method is based on Multiband Robustness (MR - Büsing, D'Andreagiovanni, 2012), an RO model that refines the classical RO model by Bertsimas and Sim, while maintaining its computational tractability and accessibility. MR is essentially based on the use of histogram-like uncertainty sets, which result particularly suitable to represent empirical distributions commonly available in uncertain real-world optimization problems.

Description: PolySCIP is a new solver for multi-criteria integer and multi-criteria linear programs handling an arbitrary number of objectives. It is available as an official part of the non-commercial constraint integer programming framework SCIP. It utilizes a lifted weight space approach to compute the set of supported extreme non-dominated points and unbounded non-dominated rays, respectively. The algorithmic approach can be summarized as follows: At the beginning an arbitrary non-dominated point is computed (or it is determined that there is none) and a weight space polyhedron created. In every next iteration a vertex of the weight space polyhedron is selected whose entries give rise to a single-objective optimization problem via a combination of the original objectives. If the ptimization of this single-objective problem yields a new non-dominated point, the weight space polyhedron is updated. Otherwise another vertex of the weight space polyhedron is investigated. The algorithm finishes when all vertices of the weight space polyhedron have been investigated. The file format of PolySCIP is based on the widely used MPS format and allows a simple generation of multi-criteria models via an algebraic modelling language.

Description: Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.

Description: Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this paper transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds.

Description: The Train Dispatching Problem (TDP) is to schedule trains through a network in a cost optimal way. Due to disturbances during operation existing track allocations often have to be re-scheduled and integrated into the timetable. This has to be done in seconds and with minimal timetable changes to guarantee smooth and conflict free operation. We present an integrated modeling approach for the re-optimization task using Mixed Integer Programming. Finally, we provide computational results for scenarios provided by the INFORMS RAS Problem Soling Competition 2012.

Description: In this article, we introduce parallel mixed integer linear programming (MILP) solvers. MILP solving algorithms have been improved tremendously in the last two decades. Currently, commercial MILP solvers are known as a strong optimization tool. Parallel MILP solver development has started in 1990s. However, since the improvements of solving algorithms have much impact to solve MILP problems than application of parallel computing, there were not many visible successes. With the spread of multi-core CPUs, current state-of-the-art MILP solvers have parallel implementations and researches to apply parallelism in the solving algorithm also getting popular. We summarize current existing parallel MILP solver architectures.

Description: Accurate quantifications of protein–ligand binding affinities by means of in silico methods increasingly gain importance in various scientific branches including toxicology and pharmacology. In silico techniques not only are generally less demanding than laboratory experiments regarding time as well as cost, in particular, if binding assays or synthesis protocols need to be developed in advance. At times, they also provide the only access to risk assessments on novel chemical compounds arising from biotic or abiotic degradation of anthropogenic substances. However, despite the continuous technological and algorithmic progress over the past decades, binding free energy estimations through molecular dynamics simulations still pose an enormous computational challenge owed to the mathematical complexity of solvated macromolecular systems often consisting of hundreds of thousands of atoms. The goals of this thesis can roughly be divided into two categories dealing with different aspects of host–guest binding quantification. On the one side algorithmic strategies for a comprehensive exploration and decomposition of conformational space in conjunction with an automated selection of representative molecular geometries and binding poses have been elaborated providing initial structures for free energy calculations. In light of the dreaded trapping problem typically associated with molecular dynamics simulations, the focus was laid on a particularly systematic generation of representatives covering a broad range of physically accessible molecular conformations and interaction modes. On the other side and ensuing from these input geometries, binding affinity models based on the linear interaction energy (LIE) method have been developed for a couple of (bio)molecular systems. The applications included a successful prediction of the liquid-chromatographic elution order as well as retention times of highly similar hexabromocyclododecane (HBCD) stereoisomers, a novel empirical LIE–QSAR hybrid binding affinity model related to the human estrogen receptor α (ERα), and, finally, the (eco)toxicological prioritization of transformation products originating from the antibiotic sulfamethoxazole with respect to their binding affinities to the bacterial enzyme dihydropteroate synthase. Altogether, a fully automated approach to binding mode and affinity estimation has been presented that is content with an arbitrary geometry of a small molecule under observation and a spatial vector specifying the binding site of a potential target molecule. According to our studies, it is superior to conventional docking and thermodynamic average methods and primarily suggesting binding free energy calculation on the basis of several heavily distinct complex geometries. Both chromatographic retention times of HBCD and binding affinities to ERα yielded squared coefficients of correlation with experimental results significantly higher than 0.8. Approximately 85 % (100 %) of predicted receptor–ligand binding modes deviated less than 1.53 Å (2.05 Å) from available crystallographic structures.

Description: In several inital value problems with particularly expensive right hand side computation, there is a trade-off between accuracy and computational effort in evaluating the right hand sides. We consider inexact spectral deferred correction (SDC) methods for solving such non-stiff initial value problems. SDC methods are interpreted as fixed point iterations and, due to their corrective iterative nature, allow to exploit the accuracy-work-tradeoff for a reduction of the total computational effort. On one hand we derive an error model bounding the total error in terms of the right hand side evaluation errors. On the other hand, we define work models describing the computational effort in terms of the evaluation accuracy. Combining both, a theoretically optimal tolerance selection is worked out by minimizing the total work subject to achieving the requested tolerance.

Description: We investigate the matching and perfect matching polytopes of hypergraphs having a special structure, which we call partitioned hypergraphs. We show that the integrality gap of the standard LP-relaxation is at most $2\sqrt{d}$ for partitioned hypergraphs with parts of size $\leq d$. Furthermore, we show that this bound cannot be improved to $\mathcal{O}(d^{0.5-\epsilon})$.

Description: We revisit the mathematical models for wireless network jamming introduced by Commander et al. (2007,2008): we first point out the strong connections with classical wireless network design and then we propose a new model based on the explicit use of signal-to-interference quantities. Moreover, to ad- dress the uncertain nature of the jamming problem and tackle the peculiar right-hand-side (RHS) uncertainty of the corresponding model, we propose an original robust cutting-plane algorithm drawing inspiration from Multiband Robust Optimization. Finally, we assess the performance of the proposed cutting plane algorithm by experiments on realistic network instances.

Description: We present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, we developed a personalized crew rostering model, to schedule the crews of the tours. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The main focus of this paper extends our previous publications on how different requirements for the rostering can be modeled in detail. The second focus is on a bi-criteria analysis of the planning problem to find the balance between the control quality and the roster acceptance. Finally, computational results on real-world instances show the practicability of our method and how different input parameters influence the problem complexity.

Description: Verteilte Dateisysteme, wie sie unter anderem in Cloud-Umgebungen eingesetzt werden, werden häufig von verschiedenen Anwendern und Anwendungen zeitgleich verwendet. Da diese Ressourcen in Cloud-Umgebungen gemietet sind, muss sichergestellt werden, dass ein Kunde nur die Ressourcen verwenden kann, für die er bezahlt hat. Andernfalls könnten andere Kunden beeinträchtigt werden. Solch eine Obergrenze wird auch als Quota bezeichnet. Speziell für objektbasierte Dateisysteme, bei denen die Metadaten einer Datei von den Dateiinhalten getrennt gespeichert und verwaltet werden, erfordert die Forcierung einer Quota ein verteiltes Protokoll. Im Rahmen der vorliegenden Arbeit wurde ein Quota-Protokoll für objektbasierte Dateisysteme entwickelt und implementiert. Bei einer aktiven Quota wird zunächst ein Teil des Speicherplatzes für eine bestimmte Datei blockiert, der als Voucher bezeichnet wird. Anschließend wird dem Client die maximale Dateigröße in signierter Form zugewiesen. Sie ergibt sich aus der Summe der bisherigen Dateigröße und allen erstellten Vouchers. Durch diesen Ansatz können die Speicherserver bei jedem Zugriff lokal prüfen, ob der Schreibzugriff die maximale Dateigröße überschreiten würde. Reicht diese nicht aus, muss ein zusätzlicher Voucher erstellt werden, sofern noch Speicherplatz verfügbar ist. Nicht verbrauchter Speicherplatz wird am Ende wieder freigegeben. Zusätzlich unterstützt das Protokoll die Verteilung der Inhalte einer Datei auf mehrere Server (Striping) sowie Sparse-Dateien, bei denen beliebige Bereiche der Datei leer bleiben. Die Implementierung erfolgte im objektbasierten Dateisystem XtreemFS. Dabei wurden spezielle Funktionen von XtreemFS, wie die Dateireplikation, mit einbezogen. In einer abschließenden Evaluation wurde der Einfluss des implementierten Quota- Protokolls bezüglich der Performanz von XtreemFS untersucht. Dabei zeigte sich zunächst, dass bei einer aktiven Quota die Performanz beim Schreiben großer Daten- mengen abhängig von der eingestellten Voucher-Größe ist. Ist diese zu niedrig gewählt, so muss der Client seine maximale Dateigröße durch zusätzliche Anfragen beim Metada- tenserver erhöhen, was die Performanz negativ beeinträchtigt. Bei einer Voucher-Größe von 100 MiB wurde beim Schreiben einer 10 GiB-Datei ein Performanzverlust von unter 2% gemessen, verglichen mit dem Entwicklungsstand ohne implementiertes Quota- Protokoll. Bei der Erstellung mehrerer 64 KiB-Dateien wurde aufgrund zusätzlicher Nachrichten ein Verlust von rund 8% gemessen.

Description: The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects and uncertainty handling. In this article, we formulate this problem as a job shop scheduling problem, in which the job durations follow a lognormal distribution. We propose to use a cutting-plane approach to solve a robust version of this optimization problem. To this end, we develop an algorithm based on fixed-point iterations to solve the subproblems that identify worst-case scenarios and generate cut inequalities. The procedure is illustrated with numerical experiments based on real data from a major hospital in Berlin.

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: Digitale Langzeitarchivierung erfolgt auf Grundlage verbindlicher Regelungen zwischen Langzeitarchiv und Datengeber. Detaillierte organisatorische und technische Bedingungen für Datenübernahmen werden dabei in Absprache zwischen den Kooperationspartnern in einer Übernahmevereinbarung festgehalten. Im Rahmen der Entwicklung des Langzeitarchivs EWIG am Zuse Institute Berlin ist die hier dokumentierte Mustervorlage für Übernahmevereinbarungen entstanden.

Description: In constraint programming, energetic reasoning constitutes a powerful start time propagation rule for cumulative scheduling problems (CuSP). In this paper, we first present an improved time interval checking algorithm that is derived from a polyhedral model. In a second step, we extend this algorithm to an energetic reasoning propagation algorithm with complexity O(n^2 log n) where n denotes the number of jobs. The key idea is based on a new sweep line subroutine that efficiently evaluates the relevant time intervals for all jobs. In particular, our algorithm yields at least one possible energetic reasoning propagation for each job. Finally, we show that on the vast number of relevant time intervals our approach yields the maximum possible propagation according to the energetic reasoning rule.

Description: We study an extension of the shortest path network interdiction problem and present a novel real-world application in this area. We consider the problem of determining optimal locations for toll control stations on the arcs of a transportation network. We handle the fact that drivers can avoid control stations on parallel secondary roads. The problem is formulated as a mixed integer program and solved using Benders decomposition. We present experimental results for the application of our models to German motorways.

Description: We study in experiment and theory thermal energy and charge transfer close to the quantum limit in a ballistic nanodevice, consisting of multiply connected one-dimensional electron waveguides. The fabricated device is based on an AlGaAs/GaAs heterostructure and is covered by a global top-gate to steer the thermal energy and charge transfer in the presence of a temperature gradient, which is established by a heating current. The estimate of the heat transfer by means of thermal noise measurements shows the device acting as a switch for charge and thermal energy transfer. The wave-packet simulations are based on the multi-terminal Landauer-Büttiker approach and confirm the experimental finding of a mode-dependent redistribution of the thermal energy current, if a scatterer breaks the device symmetry.

Description: This paper develops a class of meshless methods that are well-suited to statistical inverse problems involving partial differential equations (PDEs). The methods discussed in this paper view the forcing term in the PDE as a random field that induces a probability distribution over the residual error of a symmetric collocation method. This construction enables the solution of challenging inverse problems while accounting, in a rigorous way, for the impact of the discretisation of the forward problem. In particular, this confers robustness to failure of meshless methods, with statistical inferences driven to be more conservative in the presence of significant solver error. In addition, (i) a principled learning-theoretic approach to minimise the impact of solver error is developed, and (ii) the challenging setting of inverse problems with a non-linear forward model is considered. The method is applied to parameter inference problems in which non-negligible solver error must be accounted for in order to draw valid statistical conclusions.

Description: The task of periodic timetabling is to determine trip arrival and departure times in a public transport system such that travel and transfer times are minimized. This paper investigates periodic timetabling models with integrated passenger routing. We show that different routing models can have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. 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 by integrating passenger routing.

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 optimization 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. 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 continuous nonlinear program (NLP) can be certified by solving an MILP. This result provides an efficient pruning procedure in a branch-and-bound algorithm. Our computational results demonstrate a substantial speedup for the necessary computations.

Description: We study the Flight Planning Problem for a single aircraft, which deals with finding a path of minimal travel time in an airway network. Flight time along arcs is affected by wind speed and direction, which are functions of time. We consider three variants of the problem, which can be modeled as, respectively, a classical shortest path problem in a metric space, a time-dependent shortest path problem with piecewise linear travel time functions, and a time-dependent shortest path problem with piecewise differentiable travel time functions. The shortest path problem and its time-dependent variant have been extensively studied, in particular, for road networks. Airway networks, however, have different characteristics: the average node degree is higher and shortest paths usually have only few arcs. We propose A* algorithms for each of the problem variants. In particular, for the third problem, we introduce an application-specific "super-optimal wind" potential function that overestimates optimal wind conditions on each arc, and establish a linear error bound. We compare the performance of our methods with the standard Dijkstra algorithm and the Contraction Hierarchies (CHs) algorithm. Our computational results on real world instances show that CHs do not perform as well as on road networks. On the other hand, A* guided by our potentials yields very good results. In particular, for the case of piecewise linear travel time functions, we achieve query times about 15 times shorter than CHs.