Library

Description: Cows typically have different numbers of follicular waves during their hormonal cycle. Understanding the underlying regulations leads to insights into the reasons for declined fertility, a phenomenon that has been observed during the last decades. We present a systematic approach based on Fourier analysis to examine how parameter changes in a model of the bovine estrous cycle lead to different wave patterns. Even without any biological considerations, this allows to detect the responsible model parameters that control the type of periodicity of the solution, thus supporting experimental planning of animal scientists.

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: 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: 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 integrated line planning and passenger routing problem is an important planning problem in service design of public transport. A major challenge is the treatment of transfers. A main property of a line system is its connectivity. In this paper we show that analysing the connecvitiy aspect of a line plan gives a new idea to handle the transfer aspect of the line planning problem.

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 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: 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: 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: 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: 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: The optimal design of wireless networks has been widely studied in the literature and many optimization models have been proposed over the years. However, most models directly include the signal-to-interference ratios representing service coverage conditions. This leads to mixed-integer linear programs with constraint matrices containing tiny coefficients that vary widely in their order of magnitude. These formulations are known to be challenging even for state-of-the-art solvers: the standard numerical precision supported by these solvers is usually not sufficient to reliably guarantee feasible solutions. Service coverage errors are thus commonly present. Though these numerical issues are known and become evident even for small-sized instances, just a very limited number of papers has tried to tackle them, by mainly investigating alternative non-compact formulations in which the sources of numerical instabilities are eliminated. In this work, we explore a new approach by investigating how recent advances in exact solution algorithms for linear and mixed-integer programs over the rational numbers can be applied to analyze and tackle the numerical difficulties arising in wireless network design models.

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: 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: While the majority of the photochemical states and pathways related to the biological capture of solar energy are now well understood and provide paradigms for artificial device design, additional low-energy states have been discovered in many systems with obscure origins and significance. However, as low-energy states are naively expected to be critical to function, these observations pose important challenges. A review of known properties of low energy states covering eight photochemical systems, and options for their interpretation, are presented. A concerted experimental and theoretical research strategy is suggested and outlined, this being aimed at providing a fully comprehensive understanding.

Description: This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set.

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 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: All relevant implementation aspects of finite element methods are discussed in this book. The focus is on algorithms and data structures as well as on their concrete implementation. Theory is covered as far as it gives insight into the construction of algorithms.Throughout the exercises a complete FE-solver for scalar 2D problems will be implemented in Matlab/Octave.

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 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: Carbon-fiber reinforced composites are becoming more and more important in the production of light-weight structures, e.g., in the automotive and aerospace industry. Thermography is often used for non-destructive testing of these products, especially to detect delaminations between different layers of the composite. In this presentation, we aim at methods for defect reconstruction from thermographic measurements of such carbon-fiber reinforced composites. The reconstruction results shall not only allow to locate defects, but also give a quantitative characterization of the defect properties. We discuss the simulation of the measurement process using finite element methods, as well as the experimental validation on flat bottom holes. Especially in pulse thermography, thin boundary layers with steep temperature gradients occurring at the heated surface need to be resolved. Here we use the combination of a 1D analytical solution combined with numerical solution of the remaining defect equation. We use the simulations to identify material parameters from the measurements. Finally, fast heuristics for reconstructing defect geometries are applied to the acquired data, and compared for their accuracy and utility in detecting different defects like back surface defects or delaminations.

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: 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: 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: 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 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: 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: The airplane has changed the world in a tremendous way. Efficient scheduling of airmen and aircrafts is of considerable importance for cost-effectiveness of compa- nies. Attentiveness of flight crew members is vital as fatigue can lead to severe accidents. Therefore, duty times of flight crews are strictly limited. Long distance flights may be difficult to schedule with only one set of crew members. Furthermore, pertu- bations of the schedules may entail exchanging the entire crew, which confounds multiday schedules. A new EU regulation introduced in-flight rest: a schedule may extend pilots’ duty times if they rest for a certain time in designated crew compart- ments provided aboard airplanes. Of course they have to be replaced in that period of time. This thesis examines the in-flight rest assignment problem, which is the decision problem whether a given schedule allows for all crew members to take their compul- sory rest. The problem can be seen as multimachine scheduling problem. Efficient algorithms for special cases were developed and an alternative approach for entire hard cases is discussed.

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: 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: Simulations of optical processes and complex nanostructured devices have become omnipresent in recent years in several fields of current research and industrial applications, not limited to the field of photovoltaics. Devices or processes are optimized with respect to a certain objective where the underlying physical processes are described by partial differential equations. In photovoltaics and photonics electromagnetic fields are investigated which are governed by Maxwell’s equations. In this thesis a reduced basis method for the solution of the parameter dependent electromagnetic scattering problem with arbitrary parameters is developed. The method is developed with the specific challenges arising in optical simulations of thin-film silicon solar cells in mind. These are large in domain size and have a complex three-dimensional structure, making optimization tasks infeasible if high-accuracy of the electromagnetic field solution is required. The application of the empirical interpolation methods allows to expand an arbitrary parameter dependence affinely. Thus not only geometries, but also material tensors and source fields can be parameterized. Additionally, the required non-linear post-processing steps of the electromagnetic field to derive energy fluxes or volume absorption are addressed. The reduced basis method allows to reduce the computational costs by orders of magnitude compared to efficient finite element solvers. In addition, an efficient tailored domain decomposition algorithm is presented to model incoherent layers or illuminations in optical systems efficiently. This is of particular interest for solar cells in superstrate configuration where the absorber is illuminated through a glass substrate. The developed methods are employed in application examples taken from collaborations with experimentalists active in the joint lab “BerOSE” (Berlin Joint Lab for Optical Simulations for Energy Research). The optical model of a thin-film silicon multi-junction with incoherent light-trapping is characterized in great detail. The computational gains through hybrid, hp adaptive finite elements are studied and the incoherent domain decomposition algorithm is applied to model a more realistic light-trapping by the glass substrate. The numerical examples of a hexagonal nano-hole array and multi-junction silicon solar cell with a tunable intermediate reflector layer show that the reduced basis method is well suited as a forward solver for modeling and optimization tasks arising in photovoltaics and photonics. Reduced models for illumination and geometric parameters are built providing up to five orders of magnitude savings in computational costs. Resonance phenomena present in the nano-hole array example are detected and the model adapts itself automatically.

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 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: 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: 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 designing energy supply systems, designers are requested to rationally determine equipment types, capacities, and numbers in consideration of equipment operational strategies corresponding to seasonal and hourly variations in energy demands. However, energy demands have some uncertainty at the design stage, and the energy demands which become certain at the operation stage may differ from those estimated at the design stage. Therefore, designers should consider that energy demands have some uncertainty, evaluate the performance robustness against the uncertainty, and design the systems to heighten the robustness. Especially, this issue is important for cogeneration plants, because their performances depend significantly on both heat and power demands. Although robust optimal design methods of energy supply systems under uncertain energy demands were developed, all of them are based on linear models for energy supply systems. However, it is still a hard challenge to develop a robust optimal design method even based on a mixed-integer linear model. At the first step for this challenge, in this paper, a method of evaluating the performance robustness of energy supply systems under uncertain energy demands is proposed based on a mixed-integer linear model. This problem is formulated as a bilevel mixed-integer linear programming one, and a sequential solution method is applied to solve it approximately by discretizing uncertain energy demands within their intervals. In addition, a hierarchical optimization method in consideration of the hierarchical relationship between design and operation variables is applied to solve large scale problems efficiently. Through a case study on a gas turbine cogeneration plant for district energy supply, the validity and effectiveness of the proposed method and features of the performance robustness of the plant are clarified.

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: 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: 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: 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: 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 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: 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: 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: Mixed integer programming has become a very powerful tool for modeling and solving real-world planning and scheduling problems, with the breadth of applications appearing to be almost unlimited. A critical component in the solution of these mixed-integer programs is a set of routines commonly referred to as presolve. Presolve can be viewed as a collection of preprocessing techniques that reduce the size of and, more importantly, improve the ``strength'' of the given model formulation, that is, the degree to which the constraints of the formulation accurately describe the underlying polyhedron of integer-feasible solutions. As our computational results will show, presolve is a key factor in the speed with which we can solve mixed-integer programs, and is often the difference between a model being intractable and solvable, in some cases easily solvable. In this paper we describe the presolve functionality in the Gurobi commercial mixed-integer programming code. This includes an overview, or taxonomy of the different methods that are employed, as well as more-detailed descriptions of several of the techniques, with some of them appearing, to our knowledge, for the first time in the 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: 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.

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: We find previously unknown families which imply Frankl’s conjecture using an algorithmic framework. The conjecture states that for any non-empty union-closed (or Frankl) family there exists an element in at least half of the sets. Poonen’s Theorem characterizes the existence of weights which determine whether a given Frankl family implies the conjecture for all Frankl families which contain it. A Frankl family is Non–Frankl-Complete (Non–FC), if it does not imply the conjecture in its elements for some Frankl family that contains it. We design a cutting-plane method that computes the explicit weights which imply the existence conditions of Poonen’s Theorem. This method allows us to find a counterexample to a ten-year-old conjecture by R. Morris about the structure of generators for Non–FC-families.

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 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: 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: 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: 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: 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: We consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, we propose a refined model that allows to precompute tighter relaxations for each operation mode. These relaxations may be used to strengthen the compressor station submodels in gas network optimization problems. We provide a procedure to obtain the refined model from the input data for the original model.

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.