DE | EN
Home
About Us
Overview
Facts and Figures
Organization
Scientists
Contact
Approach
Situations offered
Research
Overview
Application Fields
Projects
Publications
Scientists
Preprints
Institutional Cooperation
Archiv 02-14
Transfer
Overview
Industry
References
MODAL-AG
Spin Offs
Software
Patents
Schools
Overview
MathInside
MATHEATHLON
Matheon-Kalender
What'sMath
Training for Teachers
Summer Schools
Events
Press
Overview
Releases
News
Overview
Matheon Head
Number of the week
News 2002 - 2014
Activities
Overview
Workshops
15 Years Matheon
Media
Overview
Photos
Videos
Audios
Booklets
Books
News from around the world

Running projects

Financed by ECMath

  • MI6

    Geometry of Equilibria for Shortest Path

    Prof. Dr. Michael Joswig

    Project heads: Prof. Dr. Michael Joswig
    Project members: Dr. Benjamin Schröter
    Duration: -
    Status: running
    Located at: Technische Universität Berlin

    Description

    The most basic techniques in network optimization are methods to find shortest paths between pairs of nodes in a directed graph. Classical examples include the algorithms of Dijkstra and Floyd–Warshall. These are among the core tools used, e.g., in devices which help a car driver to navigate a road network. Since efficient algorithms are available the corresponding shortest–path problems can be solved almost instantly, even on cheap hardware, and even for fairly large networks. Yet the situation for the network provider is quite different from the perspective of the network user. One reason is that the provider’s objective does not necessarily agree with the one of the user: While the individual driver might be interested in short travel times, the traffic authorities of a metropolitan city might want to, e.g., minimize the total amount of pollution. More importantly, the traffic authorities seek to achieve a system optimum, whereas the driver cares for an individual objective. Typically, in relevant cases it is next to impossible to even describe a system optimum. To help circumventing this problem, this project will focus on developing mathematical tools to assess the impact of local changes to a network a priori. Our prime application will be toward the computation of shortest paths. However, it is expected that some results can also be transferred to other network optimization problems. The optimization of networks is a central theme in combinatorial optimization. Hence the literature is abundant, and the 600 pages of the first volume of Schrijver’s monograph only form the tip of the iceberg. Modern concepts in this area include online techniques as well as robustness and randomization and dynamic algorithms. There are methods which can deal with partial or even incorrect information, and these can also be useful for analyzing modifications to a network to some extent. Further, in practice simulation plays an important role, possibly even on a microscopic level with agents modeling individual drivers. Here we propose to take a somewhat different view on this subject. We will make use of methods from polyhedral geometry to allow for addressing the relevant combinatorial optimization problems in a parameterized fashion.

    http://www3.math.tu-berlin.de/combi/dmg/2017-ECMath-MI06/
  • MI7

    Routing Structures and Periodic Timetabling

    Prof. Dr. Ralf Borndörfer / Dr. Marika Karbstein

    Project heads: Prof. Dr. Ralf Borndörfer / Dr. Marika Karbstein
    Project members: Dr. Niels Lindner
    Duration: 01.06.2017 - 31.12.2018
    Status: running
    Located at: Konrad-Zuse-Zentrum für Informationstechnik Berlin

    Description

    The integration of passenger route choices in traffic planning problems taps essential optimization potentials that cannot be neglected. In this project, we approach this topic by mainly focusing on the timetabling problem: The aim is to efficiently find optimal solutions for the integrated timetabling and passenger routing problem. The research focuses on three work packages: the timetabling problem itself, efficient routing algorithms, and the identification and exploitation of routing structures.

    http://www.zib.de/projects/routing-structures-and-periodic-timetabling
  • MI8

    Understanding and Improving Traffic with Uncertain Demands

    Prof. Dr. Max Klimm

    Project heads: Prof. Dr. Max Klimm
    Project members: Philipp Warode
    Duration: -
    Status: running
    Located at: Humboldt Universität Berlin

    Description

    Traffic and logistic networks are among the most vital infrastructures of modern civilization providing access to economic activities, work, health care, and social and cultural life. However, the huge benefits of private and commercial traffic are accompanied by severe burdens in terms of congestion, exhaust gas pollution and land consumption. In the past years, we witnessed the emergence of several new car-related technologies that have the potential to fundamentally change the way traffic networks are managed and used: navigation devices with real-time information allow each traffic participant to make an informed decision concerning the route choice; electrical and hybrid vehicles allow mobility with reduced carbon-dioxide footprint; car-to-car and car-to-infrastructure communications pave the way to a more coordinated traffic, ultimately culminating in the use of autonomous vehicles. The ubiquity of navigation devices and car communication today produces a wealth of data concerning the traffic demand, its elasticity, and the travel times, making these pieces of information available to the system designer. However, the mathematical theory of traffic equilibria typically assumes a fixed travel demand that is then distributed in the network according to the equilibrium concept in question. The restriction to a single demand matrix may be useful when modeling a particular traffic scenario (e.g. a rush hour situation). However, when designing the overall network or when installing road-pricing schemes that are active for a long time period it is much more sensible to analyze the overall performance of the system, i.e., to study the average travel with respect to the empirical distribution of travel demands over a given time span. This is the main question addressed in this project.

    https://www.wiwi.hu-berlin.de/de/professuren/quantitativ/or/projects/unknown-demands/
  • MI10

    Acyclic network flows

    Dr. Benjamin Hiller / Prof. Dr. Thorsten Koch / Prof. Dr. Martin Skutella

    Project heads: Dr. Benjamin Hiller / Prof. Dr. Thorsten Koch / Prof. Dr. Martin Skutella
    Project members: Dr. Kai-Helge Becker
    Duration: -
    Status: running
    Located at: Konrad-Zuse-Zentrum für Informationstechnik Berlin

    Description

    Utility and infrastructure networks are at the heart of our daily life and we are taking their proper working for granted. To provide this service, network operators face difficult planning and operational problems. The complexity of the considered optimization problems increases for several reasons, for instance because geographically bigger networks are considered or the detail level is increased. For large networks, providing globally optimal solutions or at least good bounds for assessing solution quality is still a big challenge. This project addresses this challenge for so-called potential-driven nonlinear network flow problems that are a key model for infrastructure networks for fluids, e.g. water and gas. These problems feature a so-called potential for each node, and the flow on an arc is related to the difference of the potential of its end nodes. In particular, flow is always directed from higher to lower potential, i.e. the potentials induce an acylic orientation of the arcs. This observation is the motivation for this project: We study network flow problems with the additional requirement of acyclic flows: If each network arc is oriented in the direction of flow over this arc, then there is no directed cycle in the resulting network. This is an interesting combinatorial structure that arises from nonconvex nonlinear constraints and thus links combinatorial and continuous optimization. The aim of this project is to develop algorithmic techniques to exploit this structure to improve global optimization methods for large-scale nonlinear flow problems.

    http://www.zib.de/projects/acyclic-network-flows
  • MI11

    Data mobility in ad-hoc networks: Vulnerability & security

    Dr. Benedikt Jahnel / Prof. Dr. Wolfgang König

    Project heads: Dr. Benedikt Jahnel / Prof. Dr. Wolfgang König
    Project members: Alexander Wapenhans
    Duration: 2018-10-24 - 2018-10-24
    Status: running
    Located at: Weierstraß-Institut

    Description

    Present day telecommunication networks are ill equipped for the rapidly growing demand for mobile data transfers. With the fifth generation of mobile networks, paradigmatic shifts in the design of the network are on the agenda. A critical aspect here is the role of infrastructure. Multilayered cellular networks with possible incorporation of relaying mechanisms are under investigation not only in the scientific community, but also in industry. All these new designs have in common a rapid increase of degrees of freedom in the system. The central role of (expensive) base stations is reduced in favour of an increasingly important role of (cheap) relays. In particular, also the users of the system will be attached a relay functionality in the system. As a result, the network becomes more and more decentralised. First implementations of peer-to-peer (P2P) communications for public use are already available. Exploring the possible benefits of such new architectures is in full swing in the academic and the industrial research. For a survey on device-to-device (D2D) communication in cellular networks see for example. One promising way to cope with the new and more complex structures that arise is to exploit probabilistic methods. Indeed, fundamental ansatzes from stochastic geometry (e.g., spatial Poisson processes, continuum percolation theory, ...) are widely used for modelling the spatial locations of the users, the relays and the base stations and their basic connectivity properties. For the description of temporal developments, standard methods from stochastic processes (stochastic interacting particle processes like bootstrap percolation or the contact process) are commonly used to model the spread of information through a network. Of crucial importance in all these future scenarios with less centralised architectures is a good understanding of vulnerability and security, in particular of the way in which malware (e.g., proximity-based propagation sabotage software or computer killing viruses like Cabir or CommWarrior) spreads in such networks. For usual networks, a number of strategies have been exploited by operators in order to restrict the spread of the malware and to keep the functionality of the network available. For security in D2D communication networks see the review. However, the new challenges accompanying the system decentralisation also include the question how successful these defense strategies can be in such systems, in particular since the spread of malware (more generally, of any information) in such a system follows a different set of rules than in centralised networks. The project aims at a probabilistic analysis of (1) the velocity of the propagation of infected or otherwise flawed relays in a realistic mobile ad-hoc network if a malware has attacked some node(s), and (2) of the performance and the success of some of the most widely used security strategies against this. We strive to understand how quickly a region of damaged nodes in a realistic mobile ad-hoc network spreads out, in particular whether, under the defense strategies that we consider, the infected region will be kept bounded or not.

    http://www.wias-berlin.de/projects/ECMath-MI11/
  • MI12

    Dynamic Models and Algorithms for Equilibria in Traffic Networks

    Prof. Dr. Martin Skutella

    Project heads: Prof. Dr. Martin Skutella
    Project members: Leon Sering
    Duration: -
    Status: running
    Located at: Technische Universität Berlin

    Description

    The efficiency of private transport is of particular importance for densely populated metropolitan areas. In light of ever growing traffic volumes, road infrastructure constitutes a scarce resource that must be used as effectively as possible. In this context, the availability of data and, associated therewith, the development of future technologies such as autonomously guided vehicles dramatically change the way users act and interact. This project wants to address some of the challenges occurring in these next generation traffic networks.

    http://www.tu-berlin.de/?id=186306
  • MI13

    Modelling, Stability and Synchronization of Traffic Flow Networks

    Prof. Dr. Caren Tischendorf

    Project heads: Prof. Dr. Caren Tischendorf
    Project members: Dr. Jan Philipp Pade / Jonas Pade
    Duration: 01.06.2017 - 31.12.2018
    Status: running
    Located at: Humboldt Universität Berlin

    Description

    The project aims to develop and test a mesoscopic traffic model that allows an efficient simulation of the traffic flow under consideration of traffic lights controlled by the traffic density. We want to study the impact of installing, removing and controlling traffic lights to obtain congestions.

    www.math.hu-berlin.de/~numteam1/trafficnetwork.html
  • MI-CH1

    Robust Optimization of Load Balancing in the Operating Theatre

    Dr. Guillaume Sagnol

    Project heads: Dr. Guillaume Sagnol
    Project members: Daniel Schmidt genannt Waldschmidt
    Duration: 01.06.2017 - 31.12.2018
    Status: running
    Located at: Technische Universität Berlin

    Description

    The operating theater (OT) is one of the most expensive hospital resources, and its management is a very complex task, which involves combinatorial aspects in an uncertain environment (surgical durations, emergency cases, availability of recovery beds). This project is concerned with the tactical (middle-term) planning of the OT, which aims at maximizing the utilization of resources in the OT, balancing the workload over the different operating sessions, and ensuring an equitable access and treatment duration to all patients.

    http://www.coga.tu-berlin.de/v_menue/projects/mi_ch1




Financed by others

  • MI-AP6

    Parameter identification, sensor localization and quantification of uncertainties

    Prof. Dr. Michael Hintermüller

    Project heads: Prof. Dr. Michael Hintermüller
    Project members: -
    Duration: 01.10.2014 - 30.06.2022
    Status: running
    Located at: Humboldt Universität Berlin

    Description

    The project work concentrates on modeling aspects as well as the conception and analysis of robust numerical methods for solving inverse problems for switching (or hybrid) systems of partial differential equations on graphs. In this context, the graph typically represents a transportation network for a specific substance or commodity. In accordance with the focus application of this collaborative research center (CRC), the main emphasis lies on networks transporting for (natural) gas. The project pursues several research goals:

    The identification of unknown parameters (e.g. the Darcy friction factor) and the detection of anomalies (leakage). the optimal arrangement of sensors in the network for a robustifying the identification tasks the quantification of uncertainties in the identified parameters or in other statistically relevant quantities.

    Within the CRC, this project will collaborate with other subprojects on (constrained) optimal control problems for hyperbolic or hybrid systems and their numerical realization, and on numerical methods for the identification of the friction coefficient. It will equip the hierarchy of models considered with the CRC with relevant physical parameters or statistical information resulting from solving various identification problems. The project participates in demonstrator D2.

    http://trr154.fau.de/index.php/en/subprojects/b02e
  • MI-AP7

    Controlled coupling of mixed integer-continuous models with modeled uncertainties

    Prof. Dr. Volker Mehrmann

    Project heads: Prof. Dr. Volker Mehrmann
    Project members: -
    Duration: 01.10.2014 - 30.06.2022
    Status: running
    Located at: Technische Universität Berlin

    Description

    The aim of project B03 is the development of a new methodology for the coupling of widely different mathematical models in a network. Moreover, error controllers are developed on the basis of modeled errors and uncertainties using the example of gas networks. These errors and uncertainties in submodels of the complex network are balanced in the overall simulation. Therefore, measures for the errors and uncertainties should be modeled for every submodel and made comparable. This can only succeed on the basis of a detailed model hierarchy, see Figure 1. All the errors and uncertainties in the simulation and optimisation are considered as an error in the finest modeling level using a backward error analysis in the model hierarchy. The estimated error in the finest level forms the mathematical basis for the development of a robust coupling controller. The controller should allow us to control the overall error in such a way that a prescribed simulation or optimisation goal is achieved within a desired tolerance.

    http://trr154.fau.de/index.php/en/subprojects/b03e
  • MI-AP8

    Nonlinear chance constraints in gas transportation problems

    PD Dr. René Henrion

    Project heads: PD Dr. René Henrion
    Project members: -
    Duration: 01.10.2014 - 30.06.2022
    Status: running
    Located at: Weierstraß-Institut

    Description

    The aim of this project consists in applying nonlinear probabilistic constraints to optimization problems in gas transportation assuming that the underlying random parameter obeys a multivariate and continuous distribution. Doing so, a robust in the sense of probability design of gas transport shall be facilitated. Stochastic optimization is the appropriate mathematical discipline to cope with uncertainty when looking for optimal decisions under random perturbations of some nominal parameters. Among different modeling options, probabilistic constraints hold a key position first of all in engineering applications. The solution of optimization problems with nonlinear probabilistic constraints with continuous multivariate distributions can be considered as new ground both from the theoretical and – at least for interesting dimension - from the numerical perspectives. Moreover, in the present project, we deal with implicit probabilistic constraints where the relation between decision and random parameter is established only by additional variables via some equation system. Although gas network problems with uncertain injection and consumption provide a very natural motivation for the research in this project, the mathematical insight to be expected has an impact on quite different applications as well, for instance, on optimization problems of power management, particularly those related with renewable energies. Beyond this, optimal control problems governed by PDEs and subjected to random state constraints promise being a potential application of implicit probabilistic constraints. In its first phase the project will investigate optimization problems arising from a simple stationary gas network model (RNET-ISO4) subject to random loads. Here the probabilistic constraint ensures the technical feasibility of loads with a specified probability. In the longer perspective, the consideration of dynamic probabilistic constraints for time-dependent decisions and of binary variables shall be pursued.

    http://trr154.fau.de/index.php/en/subprojects/b04e
  • MI-AP9

    Hierarchical PDAE-surrogate-modeling and stabil PDAE-network-discretization for simulating large non-stationary gas networks

    Prof. Dr. Caren Tischendorf

    Project heads: Prof. Dr. Caren Tischendorf
    Project members: -
    Duration: 01.10.2014 - 30.06.2022
    Status: running
    Located at: Humboldt Universität Berlin

    Description

    This subproject focuses on the development and analysis of models and methods for a stable and fast simulation of huge transient gasnetworks, which will also be used for an efficient parameter optimization and control of the network. The main aspects are the development of a numerical discretization in space and time that is adjusted to the topology of the network as well as a hierarchical modelling of several elements (pipes, compressors ect.) and subnet-structures.
    For the complete network as a coupled system of nonlinear partial differential equations and algebraic equations (PDAE) we consider approximations by a spatial semi-discretization. We strive for a determination and classification of topology depending critera for the index of the time dependend differential algebraic system. Topology- and controldepending spatial discretizations will be determinded, that lead to DAEs of index 1, in order to diminish the influence of perturbations for the DAE system best possible. Moreover we want to establish a perturbationanalysis as well as existence and uniquness results for die PDAE-model. Here, the time and pressure/flow-depending control-states that can change the variable structure (dynamic as well as static) for certain points in time and for certain states of the network will be a major challange.
    As a method, we focus on a Galerkin-Approach in space followed by a discretization in time of the resulting DAE with implicit or semi-implicit methods respectively, such that the algebraic constraints hold for the current point in time. Continuationmethods and space-mapping techniques are used for the initialisation to guarantee good convergence behaviour. Furthermore, to satisfy the control requirements of the systems and to enable the handling of huge networks, this subproject aims at the enhancement of the simulation speed. It is planed to detect characteristic subnetstructures and derive parameter dependen transient surrogate models with suitable error estimators by applying model order reduction methods. These input-ouput models as dynamic systems of ODEs will be coupled with die complete PDAE model in one model hierarchy.

    http://trr154.fau.de/index.php/en/subprojects/c02e
  • MI-AP17

    Efficient network flow methods for non-steady-state gasflows

    Prof. Dr. Martin Skutella

    Project heads: Prof. Dr. Martin Skutella
    Project members: -
    Duration: 01.10.2014 - 30.06.2022
    Status: running
    Located at: Technische Universität Berlin

    Description

    The goal of this subproject is to apply network flow theory to simplified models for gas pipelines and related transportation networks. Network flow theory has proven itself to be a powerful and valueable tool for solving complex problems in many areas of application, like traffic networks, telecommunication networks, and logistic networks. All of these networks can be designed and operated using network flow algorithms, which exhibit a very efficient runtime behaviour, making them capable of handling the large instances occuring in practice. In this subproject, we strive to employ network flow algorithms for solving problems in gas and related networks. Conventional network flow theory is insufficient to describe gas networks, since it neither accounts for pressures in nodes, nor for the non-linear dependency of the flow from the pressure in nodes. However, there are several problems in gas networks which occur in a similar form in network flow theory and are known and well understood there, for example generalized or length-bounded flows. Furthermore, non-linear relationships in other aspects like for example the flow velocity in traffic networks, have been studied and solved by network flow theory. As a base for our models we use a model based on the Weymouth equations, which can be solved using convex minimum cost flows. This flow model and its solution techniques can be generalized from the stationary to the transient case, analogous to how classic network flows can be generalized to dynamic network flows. For solving dynamic networks (approximately), there are useful techniques known from network flow theory, e.g. adaptive time-expanded networks, which have a great number of applications. These techniques are to be made useable for transient gas flows in this subproject. Gas networks usually contain a number of active elements - valves, compressors, and so on - which require integral decisions which have a significant impact on the gas flow. Therefore, these elements have to be incorporated in the network flow model. This can be handled by Branch & Bound based methods, or by adaption of techniques from network design. For Branch & Bound based techniques it is crucial to identify infeasible solutions as fast as possible. In gas networks, this means identifying partial configurations of active elements which imply infeasiblity. Therefore, analysis of infeasiblity will be a focus of the research done in this subproject. By developing efficient models and solution techniques for gas networks and characterizing infeasibility in these models, this subproject will contribute for Demonstrator 1, with a special focus on large gas networks.

    http://trr154.fau.de/index.php/en/subprojects/a07e