Library

Description: In a number of studies the feeding of pharmacological levels of Zinc to weanling pigs was examined. The publications agree in the fact that the achieved performance increase of the pigs depends on the amount of Zinc as well as on the type of mineral complex used as feed additive. The results are based on measurements of the animals' body weight and the Zinc concentration in the blood within the first two weeks of the experiments. From the measurement values, conclusions are drawn about adequate Zinc doses, but a deeper understanding of the physiological processes that influence the Zinc distribution in the organism is still missing. In this report, we want to close this gap by using a systems biology approach. We present a small mathematical model that describes the organic feedback mechanisms with the help of differential equations. The simulation results not only match with measurement values, but also give insight into non-measurable processes, which will hopefully contribute to animal experiments being organized in a more selective and reduced way.

Description: Fast computation of valid linear programming (LP) bounds serves as an important subroutine for solving mixed-integer programming problems exactly. We introduce a new method for computing valid LP bounds designed for this application. The algorithm corrects approximate LP dual solutions to be exactly feasible, giving a valid bound. Solutions are repaired by performing a projection and a shift to ensure all constraints are satisfied; bound computations are accelerated by reusing structural information through the branch-and-bound tree. We demonstrate this method to be widely applicable and faster than solving a sequence of exact LPs. Several variations of the algorithm are described and computationally evaluated in an exact branch-and-bound algorithm within the mixed-integer programming framework SCIP.

Description: Constraint Integer Programming (CIP) is a generalization of mixed-integer programming (MIP) in the direction of constraint programming (CP) allowing the inference techniques that have traditionally been the core of \P to be integrated with the problem solving techniques that form the core of complete MIP solvers. In this paper, we investigate the application of CIP to scheduling problems that require resource and start-time assignments to satisfy resource capacities. The best current approach to such problems is logic-based Benders decomposition, a manual decomposition method. We present a CIP model and demonstrate that it achieves performance competitive to the decomposition while out-performing the standard MIP and CP formulations.

Description: This study presents a differential equation model for the feedback mechanisms between Gonadotropin-releasing Hormone (GnRH), Follicle-Stimulating Hormone (FSH), Luteinizing Hormone (LH), development of follicles and corpus luteum, and the production of estradiol (E2), progesterone (P4), inhibin A (IhA), and inhibin B (IhB) during the female menstrual cycle. In contrast to other models, this model does not involve delay differential equations and is based on deterministic modelling of the GnRH pulse pattern, which allows for faster simulation times and efficient parameter identification. These steps were essential to tackle the task of developing a mathematical model for the administration of GnRH analogues. The focus of this paper is on model development for GnRH receptor binding and the integration of a pharmacokinetic/pharmacodynamic model for the GnRH agonist Nafarelin and the GnRH antagonist Cetrorelix into the menstrual cycle model. The final mathematical model describes the hormone profiles (LH, FSH, P4, E2) throughout the menstrual cycle in 12 healthy women. Moreover, it correctly predicts the changes in the cycle following single and multiple dose administration of Nafarelin or Cetrorelix at different stages in the cycle.

Description: Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust programs with arbitrary recourse. We apply them to robust network design with polyhedral demand uncertainty, introducing the affine routing principle. We compare the affine routing to the well-studied static and dynamic routing schemes for robust network design. All three schemes are embedded into the general framework of two-stage network design with recourse. It is shown that affine routing can be seen as a generalization of the widely used static routing still being tractable and providing cheaper solutions. We investigate properties on the demand polytope under which affine routings reduce to static routings and also develop conditions on the uncertainty set leading to dynamic routings being affine. We show however that affine routings suffer from the drawback that (even totally) dominated demand vectors are not necessarily supported by affine solutions. Uncertainty sets have to be designed accordingly. Finally, we present computational results on networks from SNDlib. We conclude that for these instances the optimal solutions based on affine routings tend to be as cheap as optimal network designs for dynamic routings. In this respect the affine routing principle can be used to approximate the cost for two-stage solutions with free recourse which are hard to compute.

Description: In cumulative scheduling, conflict analysis seems to be one of the key ingredients to solve such problems efficiently. Thereby, the computational complexity of explanation algorithms plays an important role. Even more when we are faced with a backtracking system where explanations need to be constructed on the fly. In this paper we present extensive computational results to analyze the impact of explanation algorithms for the cumulative constraint in a backward checking system. The considered explanation algorithms differ in their quality and computational complexity. We present results for the domain propagation algorithms time-tabling, edge-finding, and energetic reasoning.

Description: Our model of the bovine estrous cycle is a set of ordinary differential equations which generates hormone profiles of successive estrous cycles with several follicular waves per cycle. It describes the growth and decay of the follicles and the corpus luteum, as well as the change of the key substances over time. In this work we describe recent improvements of this model, including the introduction of new components, and elimination of time delays. We validate our model by showing that the simulations agree with observations from synchronization studies and with measured progesterone data after a single dose administration of synthetic prostaglandin F2alpha.

Description: As part of the CPAIOR 2011 a call was made for late breaking abstracts for presentation at the conference. These abstracts were meant to represent work in process, recent work, or work appearing in other academic areas but of interest to the CPAIOR community. A total of 19 submissions were received of which 16 were selected by the program chairs for presentation. This document is a compilation of the presented abstracts.

Description: Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation. In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics.

Description: In diesem Report wird ein Überblick über Recommender Systeme (RS) im Bibliotheksbereich gegeben, welche Eigenschaften RS haben und welche Bedeutung sie damit für Bibliotheken besitzen. Es existieren semantische und nicht-semantische Lösungen, die dem Benutzer aus einer Menge von Publikationen die für ihn relevantesten empfehlen. Diese Arbeiten sowie eine Einleitung in das Thema werden präsentiert und mit den gewonnenen Kenntnissen ein Ausblick auf mögliche Entwicklungen gegeben.

Description: Die vorliegende Arbeit befasst sich mit Primalheuristiken für gemischt-ganzzahlige, lineare Optimierungsprobleme (engl.: mixed integer program MIP). Zahlreiche Optimierungsprobleme aus der Praxis lassen sich als MIP modellieren, Beispiele hierfür sind u. a. Optimierungsprobleme im öffentlichen Nah- und Fernverkehr, bei logistischen Fragestellungen oder im Bereich der Chip-Verifikation. Das Lösen von MIP ist NP-schwer und wird heutzutage meistens mit Hilfe von Branch-and-Bound-basierenden Algorithmen versucht. Das Branch-and-Bound-Ver\-fah\-ren profitiert unter Umständen von bereits frühzeitig zur Verfügung stehenden Lösungen, daher sind wir sehr an heuristischen Verfahren interessiert, die in der Praxis schnell eine gute Lösung für eine große Zahl an MIPs liefern und somit die Lösezeit des Branch-and-Bound-Verfahrens erheblich beschleunigen können. Primalheuristiken sind Suchverfahren zum Auffinden zulässiger Lösungen eines MIP. Verschiedene Typen von Primalheuristiken sollen dabei den jeweiligen Bedarf des Anwenders zu unterschiedlichen Zeiten während der Branch-and-Bound-Suche decken. Während Start- und Rundeheuristiken zu Beginn des Löseprozesses eine große Rolle bei der Suche nach der ersten zulässigen Lösung haben, arbeiten Verbesserungs-heuristiken auf schon bekannten Lösungen, um neue, bessere Lösungen zu produzieren. Diese Arbeit beschäftigt sich mit Primalheuristiken, welche Teil des MIP-Lösers SCIP sind. Im ersten Kapitel werden nach der Erarbeitung grundlegender Definitionen viele der durch Tobias Achterberg und Timo Berthold in SCIP integrierten heuristischen Verfahren vorgestellt und kategorisiert. Auf dieser Grundlage bauen dann die Kapitel 2-4 der Arbeit auf. In diesen werden drei zusätzliche Heuristiken vorgestellt, im Einzelnen sind dies ZI Round, eine Rundeheuristik, welche zuerst von Wallace beschrieben wurde, außerdem eine 2-Opt-Heuristik für MIP und eine neue Startheuristik, Shift-And-Propagate. Großer Wert wird in jedem Kapitel auf die algorithmische Beschreibung der Heuristiken gelegt, die stets anhand von motivierenden Beispielen eingeführt und anhand von Pseudocode-Algorithmen begleitet werden. Zusätzlich enthält jedes Kapitel Auswertungen der mit den neuen Heuristiken gemessenen Ergebnisse von SCIP. Eine kurze Zusammenfassung in Kapitel 5 schließt diese Arbeit ab.

Description: Many practically relevant problems can be formulated in terms of a mixed integer programming (MIP) model. MIP denotes the optimization of a linear objective function under a certain number of linear side constraints including the need for some of the involved variables to take integral solution values. Applications of MIP based optimization can be found in the area of public transit, scheduling, automatic vehicle routing, network design, etc. From a complexity point of view, MIP solving is known to be NP-hard and most commonly tried to be solved via Branch-and-Bound based algorithms. Branch-and-Bound algorithms benefit from early and good feasible solutions of a MIP in various ways. Primal heuristics are aimed at finding new solutions during the MIP solving process. There are different types of primal heuristics: while start heuristics are particularly valuable to find an early solution, improvement heuristics hopefully drive a given solution further towards optimality. This thesis focusses on primal heuristics which are part of the MIP-solving framework SCIP. The first chapter comes with basic definitions and a brief description of SCIP and the test set which we used. The remainder of the first chapter is an overview of the existing heuristics in SCIP which have been implemented by Achterberg and Berthold. In the following chapters we introduce three new heuristics which apply rounding or propagation techniques for their specific purpose, namely the new rounding heuristic ZI Round, taken from Wallace, a 2-Opt improvement heuristic for MIP and the propagation heuristic Shift-and-Propagate. It is characteristic of all three heuristics that they mainly apply computationally inexpensive algorithms. Each of them is presented in an own chapter, starting with an algorithmic description, followed by implementational details. All chapters close with a discussion of the computational results obtained with the respective implementations in SCIP.

Description: Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this paper we consider telecommunication network design under traffic uncertainty, adapting the robust optimization approach of Bertsimas and Sim [2004]. We present three different mathematical formulations for this problem, provide valid inequalities, study the computational implications, and evaluate the realized robustness. To enhance the performance of the mixed-integer programming solver we derive robust cutset inequalities generalizing their deterministic counterparts. Instead of a single cutset inequality for every network cut, we derive multiple valid inequalities by exploiting the extra variables available in the robust formulations. We show that these inequalities define facets under certain conditions and that they completely describe a projection of the robust cutset polyhedron if the cutset consists of a single edge. For realistic networks and live traffic measurements we compare the formulations and report on the speed up by the valid inequalities. We study the "price of robustness" and evaluate the approach by analyzing the real network load. The results show that the robust optimization approach has the potential to support network planners better than present methods.

Description: We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on linear outer approximation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.

Description: We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the MIPLIB and Mittelmann collections.

Description: Mobile communication is nowadays taken for granted. Having started primarily as a service for speech communication, data service and mobile Internet access are now driving the evolution of network infrastructure. Operators are facing the challenge to match the demand by continuously expanding and upgrading the network infrastructure. However, the evolution of the customer's demand is uncertain. We introduce a novel (long-term) network planning approach based on multistage stochastic programming, where demand evolution is considered as a stochastic process and the network is extended as to maximize the expected profit. The approach proves capable of designing large-scale realistic UMTS networks with a time-horizon of several years. Our mathematical optimization model, the solution approach, and computational results are presented in this paper.

Description: Energetic reasoning is one of the most powerful propagation algorithms in cumulative scheduling. In practice, however, it is not commonly used because it has a high running time and its success highly depends on the tightness of the variable bounds. In order to speed up energetic reasoning, we provide an easy-to-check necessary condition for energetic reasoning to detect infeasibilities. We present an implementation of energetic reasoning that employs this condition and that can be parametrically adjusted to handle the trade-off between solving time and propagation overhead. Computational results on instances from the PSPLIB are provided. These results show that using this condition decreases the running time by more than a half, although more search nodes need to be explored.

Description: We present and prove a theorem which gives the optimal dual vector for which a Lagrangian dual problem in the Single Period Design Problem (SPDP) is maximized. Furthermore we give a straightforward generalization to the Multi-Period Design Problem (MPDP). Based on the optimal dual values derived we compute the solution of the Lagrangian relaxation and compare it with the linear relaxation and optimal IP values.

Description: Politiker müssten doch in der Lage sein, faire Wahlverfahren, rationale gesellschaftliche Entscheidungsprozesse und schlupflochfreie Marktregulierungen zu finden. Und wenn sie sich nicht einigen können, so denkt fast jeder, dann sollen das eben unsere Gerichte regeln. Dies ist im Allgemeinen unerfüllbares Wunschdenken. Die Gründe dafür sind oft mathematischer Natur. Man kann z. B. mathematisch beweisen, dass es (in einem präzisierbaren Sinn) gar keine „fairen“ Wahlverfahren und nur in seltenen Fällen „rationale“ Entscheidungsprozesse gibt. Ein anderer Sachverhalt liegt z. B. bei Regulierungs- oder Deregulierungsmaßnahmen vor. Die dabei zu berücksichtigenden technischen Restriktionen sind häufig so kompliziert (man denke u. a. an die technischen Vorschriften im Schienen- oder Luftverkehr oder zum Betrieb von Pipelines), dass sie einfach nicht in juristischer Sprache formuliert werden können. Gut gemeinte Verordnungen sind nicht selten mathematisch widersprüchlich, führen auf praktisch unlösbare Probleme oder überfordern das Verständnis aller Beteiligten. Diese Beispiele legen nahe, dass bei einigen Gesetzgebungsprozessen und Verordnungen mathematischer Sachverstand erforderlich ist. Dieser wird derzeit aber nur sehr selten genutzt.

Description: We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the ``regularity'' of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.

Description: Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway company. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market in Europe. This leads to more potential conflicts between trains caused by an increasing demand of train paths. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. In order to make best use of the infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithms can help to automatize and tackle these challenges. Our contribution in this paper is to present a renewed planning process due to the liberalization in Europe and an associated concept for track allocation, that consists of three important parts, simulation, aggregation, and optimization. Furthermore, we present results of our general framework for real world data.

Description: We derive a-priori estimates on the length of the primal-dual path that results from a Moreau-Yosida approximation of the feasible set for state constrained optimal control problems. These bounds depend on the regularity of the state and the dimension of the problem. Comparison with numerical results indicates that these bounds are sharp and are attained for the case of a single active point.

Description: The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints, originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer program for this problem has been given by Forrest et al. The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values of 76 instances compared to previous results. Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality.

Description: This paper surveys the required mathematics for a typical challenging problem from computational medicine, the cancer therapy planning in deep regional hyperthermia. In the course of many years of close cooperation with clinics, the medical problem gave rise to quite a number of subtle mathematical problems, part of which had been unsolved when the common project started. Efficiency of numerical algorithms, i.e. computational speed and monitored reliability, play a decisive role for the medical treatment. Off-the-shelf software had turned out to be not sufficient to meet the requirements of medicine. Rather, new mathematical theory as well as new numerical algorithms had to be developed. In order to make our algorithms useful in the clinical environment, new visualization software, a virtual lab, including 3D geometry processing of individual virtual patients had to be designed and implemented. Moreover, before the problems could be attacked by numerical algorithms, careful mathematical modelling had to be done. Finally, parameter identification and constrained optimization for the PDEs had to be newly analyzed and realized over the individual patient's geometry. Our new techniques had an impact on the specificity of the individual patients' treatment and on the construction of an improved hyperthermia applicator.

Description: Supercomputers can simulate complex molecular systems. However, there is a very large gap between the fastest oscillations of covalent bonds of a molecule and the time-scale of the dominant processes. In order to extract the dominant time-scales and to identify the dominant processes, a clustering of information is needed. This thesis shows that only the subspace-based Robust Perron Cluster Analysis (PCCA+) can solve this problem correctly by the construction of a Markov State Model. PCCA+ allows for time-extrapolation in molecular kinetics. This thesis shows the difference between molecular dynamics and molecular kinetics. Only in the molecular kinetics framework a definition of transition rates is possible. In this context, the existence of an infinitesimal generator of the dynamical processes is discussed. If the existence is assumed, the Theorem of Gauß can be applied in order to compute transition rates efficiently. Molecular dynamics, however, is not able to provide a suitable statistical basis for the determination of the transition pattern.

Description: This paper proposes the first model for toll enforcement optimization on German motorways. The enforcement is done by mobile control teams and our goal is to produce a schedule achieving network-wide control, proportional to spatial and time-dependent traffic distributions. Our model consists of two parts. The first plans control tours using a vehicle routing approach with profits and some side constraints. The second plans feasible rosters for the control teams. Both problems can be modeled as Multi-Commodity Flow Problems. Adding additional coupling constraints produces a large-scale integrated integer programming formulation. We show that this model can be solved to optimality for real world instances associated with a control area in East Germany.

Description: The paper deals with the workload and busy period for the M/GI/1 system under FCFS discipline, where the customers may become impatient during their waiting for service with generally distributed maximal waiting times and also during their service with generally distributed maximal service times depending on the time waited for service. This general impatience mechanism, originally introduced by Kovalenko (1961) and considered by Daley (1965), too, covers the special cases of impatience on waiting times as well as impatience on sojourn times, for which Boxma et al. (2010), (2011) gave new results and outlined special cases recently. Our unified approach bases on the vector process of workload and busy time. Explicit representations for the LSTs of workload and busy period are given in case of phase-type distributed impatience.

Description: Given the steady increase in cores per CPU, it is only a matter of time until supercomputers will have a million or more cores. In this article, we investigate the opportunities and challenges that will arise when trying to utilize this vast computing power to solve a single integer linear optimization problem. We also raise the question of whether best practices in sequential solution of ILPs will be effective in massively parallel environments.

Description: We consider systems of ODEs with the right hand side being Laurent polynomials in several non-commutative unknowns. In particular, these unknowns could be matrices of arbitrary size. An important example of such a system was proposed by M. Kontsevich. We prove the integrability of the Kontsevich system by finding a Lax pair, corresponding first integrals and commuting flows. We also provide a pre-Hamiltonian operator which maps gradients of integrals for the Kontsevich system to symmetries.

Description: Base station cooperation in the downlink of cellular systems has been recently suggested as a promising concept towards a better exploitation of the communication system physical resources. It may offer a high gain in capacity through interference mitigation. This however, comes at a cost of high information exchange between cooperating entities and a high computational burden. Clustering of base stations into subgroups is an alternative to guarantee such cooperation benefits in a lower scale. The optimal definition of clusters, however, and a systematic way to find a solution to such problem is not yet available. In this work, we highlight the combinatorial nature of the problem, exploit this to describe the system of users and base stations as a graph and formulate a pure 0-1 program. Its solution suggests a cost optimal way to form clusters and assign user subsets to them.

Description: Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway infrastructure provider. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market. This leads to an increase of slot requests and then it is natural that conflicts occur among them. Furthermore, railway infrastructure networks consist of very expensive assets, even more they are rigid due to the long-term upgrade process. In order to make best use of these valuable infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithmic methodology can help to automatize and tackle these challenges. Our contribution in this paper is to present a renewed planning process due to the liberalization in Europe and a general framework to support the integration of simulation and optimization for railway capacity allocation.

Description: A novel symmetry method for finding exact solutions to nonlinear PDEs is illustrated by applying it to a semilinear reaction-diffusion equation in multi-dimensions. The method uses a separation ansatz to solve an equivalent first-order group foliation system whose independent and dependent variables respectively consist of the invariants and differential invariants of a given one-dimensional group of point symmetries for the reaction-diffusion equation. With this group-foliation reduction method, solutions of the reaction-diffusion equation are obtained in an explicit form, including group-invariant similarity solutions and travelling-wave solutions, as well as dynamically interesting solutions that are not invariant under any of the point symmetries admitted by this equation.

Description: Primal heuristics are an important component of state-of-the-art codes for mixed integer programming. In this paper, we focus on primal heuristics that only employ computationally inexpensive procedures such as rounding and logical deductions (propagation). We give an overview of eight different approaches. To assess the impact of these primal heuristics on the ability to find feasible solutions, in particular early during search, we introduce a new performance measure, the primal integral. Computational experiments evaluate this and other measures on MIPLIB~2010 benchmark instances.

Description: Wir stellen in dieser Arbeit ein mathematisches Optimierungsmodell zur Bestimmung eines optimalen Linienplans vor, das sowohl die Fahrzeiten und die Anzahl der Umstiege berücksichtigt als auch die Kosten des Liniennetzes. Dieses Modell deckt wichtige praktische Anforderungen ab, die in einem gemeinsamen Projekt mit den Verkehrsbetrieben in Potsdam (ViP) formuliert wurden. In diesem Projekt wurde der Linienplan 2010 für Potsdam entwickelt. Unsere Berechnungen zeigen, dass die mathematische Optimierung in nichts einer "Handplanung" des Liniennetzes nachsteht. Im Gegenteil, mit Hilfe des Optimierungsprogramms ist es möglich, durch Veränderung der Parameter mehrere verschiedene Szenarien zu berechnen, miteinander zu vergleichen und Aussagen über minimale Kosten und Fahrzeiten zu machen.

Description: In this paper a bottom-up approach of automatic simplification of a railway network is presented. Starting from a very detailed, microscopic level, as it is used in railway simulation, the network is transformed by an algorithm to a less detailed level (macroscopic network), that is sufficient for long-term planning and optimization. In addition running and headway times are rounded to a pre-chosen time discretization by a special cumulative method, which we will present and analyse in this paper. After the transformation we fill the network with given train requests to compute an optimal slot allocation. Then the optimized schedule is re-transformed into the microscopic level and can be simulated without any conflicts occuring between the slots. The algorithm is used to transform the network of the very dense Simplon corridor between Swiss and Italy. With our aggregation it is possible for the first time to generate a profit maximal and conflict free timetable for the corridor across a day by a simultaneously optimization run.

Description: Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway infrastructure provider. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market. This leads to an increase of slot requests and then it is natural that conflicts occur among them. Furthermore, railway infrastructure networks consist of very expensive assets, even more they are rigid due to the long-term upgrade process. In order to make best use of these valuable infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithmic methodology can help to automatize and tackle these challenges. Our contribution in this paper is to present a renewed planning process due to the liberalization in Europe and a general framework to support the integration of simulation and optimization for railway capacity allocation.

Description: Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation. In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics.

Description: We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the ``regularity'' of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.

Description: Gas distribution networks are complex structures that consist of passive pipes, and active, controllable elements such as valves and compressors. Controlling such network means to find a suitable setting for all active components such that a nominated amount of gas can be transmitted from entries to exits through the network, without violating physical or operational constraints. The control of a large-scale gas network is a challenging task from a practical point of view. In most companies the actual controlling process is supported by means of computer software that is able to simulate the flow of the gas. However, the active settings have to be set manually within such simulation software. The solution quality thus depends on the experience of a human planner. When the gas network is insufficient for the transport then topology extensions come into play. Here a set of new pipes or active elements is determined such that the extended network admits a feasible control again. The question again is how to select these extensions and where to place them such that the total extension costs are minimal. Industrial practice is again to use the same simulation software, determine extensions by experience, add them to the virtual network, and then try to find a feasible control of the active elements. The validity of this approach now depends even more on the human planner. Another weakness of this manual simulation-based approach is that it cannot establish infeasibility of a certain gas nomination, unless all settings of the active elements are tried. Moreover, it is impossible to find a cost-optimal network extension in this way. In order to overcome these shortcomings of the manual planning approach we present a new approach, rigorously based on mathematical optimization. Hereto we describe a model for finding feasible controls and then extend this model such that topology extensions can additionally and simultaneously be covered. Numerical results for real-world instances are presented and discussed.