Running projects

Financed by ECMath

  • MI1

    Design and operation of infrastructure networks under uncertainty

    Prof. Dr. Martin Skutella

    Project heads: Prof. Dr. Martin Skutella
    Project members: Julie Meißner
    Duration: -
    Status: running
    Located at: Technische Universität Berlin

    Description

    Uncertainty in the input data is an omnipresent issue in most real world planning processes. Metropolitan infrastructure -its design, operation and maintenance- induces complex planning processes where data uncertainty lies, e. g. in processing durations, transit times, cost, market prices, customer demands, capacity, bandwidth, energy consumption, et cetera. Since decisions on the infrastructure are typically very cost-intensive and of long-term impact, there is an urgent need of best possible mathematical support in this decision making process.

    The quality of solutions for optimization problems (e. g. in infrastructure networks) with uncertain input data crucially depends on the amount of uncertainty. More information, or even knowing the exact data, allows for significantly improved solutions. It is impossible to fully abolish/avoid uncertainty. Nevertheless, it is sometimes possible to obtain exact data, but it may involve certain exploration cost in time, money, energy, bandwidth, etc.

    In telecommunication networks planning, for example, information on the existing infrastructure (copper lines, optical fiber etc.) or the transmission range might not be easily available. The challenging major task of this project is to develop a structural understanding and algorithmic methods on how to balance the cost for data exploration with the actual benefit for the quality of solution to the optimization problem under consideration.

    Project Webpage

    http://www.coga.tu-berlin.de/index.php?id=159901
  • MI2

    Optimized noise reduction in transportation and interior spaces

    Dr. Kersten Schmidt

    Project heads: Dr. Kersten Schmidt
    Project members: Robert Gruhlke / Dr. Anastasia Thöns
    Duration: -
    Status: running
    Located at: Technische Universität Berlin

    Description

    The reduction of the excited noise of transportation, especially in gas turbines of airplanes and ships or mufflers of cars, is currently of major public and industrial interest. We aim to describe the effective absorption properties of sound absorbing resonator structures and perforated walls. As the governing equations and structures possess several scales, we study the problems asymptotically. In this project we derive and study approximative boundary and transmission conditions, that take into account the physical phenomena on the small scales inside the holes of the perforated absorber and the boundary layers in their neighbourhood.

    https://www.math.tu-berlin.de/fachgebiete_ag_modnumdiff/nachwuchsgruppe_dr_kersten_schmidt/nachwuchsgruppe_dr_kersten_schmidt/forschung/matheon_b_mi2/
  • MI3

    Infrastructure design and passenger behavior in public transport

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

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

    Description

    The strategic planning process in public transport is usually divided into consecutive planning steps - network design, line planning, and timetabling. In line planning, one has to find a set of lines defined by their paths and frequencies in a public transportation network such that a given travel demand can be routed. The task of timetabling is to schedule the trips of each line, i.e., by determining periodic arrival and departure times at their stations. The goal of each planning step is to provide a transportation system that is both attractive for passengers and can be operated economically. Integrating passenger behaviour is a major challenge in infrastructure design optimization.

    The aim of this project is the adequate treatment of passenger routing in optimization models for public transport. We want to extend our existing theoretic and algorithmic base in line planning and timetabling by (advanced) passenger routing methods in order to construct efficiently solvable integrated models.

    Project Webpage

    http://www.zib.de/projects/infrastructure-design-and-passenger-behaviour-public-transport
  • MI4

    Robust optimization of urban access networks

    Prof. Dr. Ralf Borndörfer

    Project heads: Prof. Dr. Ralf Borndörfer
    Project members: Jonad Pulaj
    Duration: -
    Status: running
    Located at: Konrad-Zuse-Zentrum für Informationstechnik Berlin

    Description

    Over the last years, telecommunications have assumed a central role in our everyday life and the volume of exchanged traffic has astonishingly increased, causing a growth of networks in size and complexity. Major telecommunications companies forecast that such traffic increase will continue, reaching the volume of more than 1000 exabyte/ year by the end of 2015 (T. Theimer, ECOC 2009, Vienna). In order to tackle such growth, an important recent trend is the integration of fixed and wireless access networks, leading to so-called fiber-wireless (Fi-Wi) networks. In a Fi-Wi network, optical fibers support long-distance access with high capacity, whereas wireless links are adopted to cover the last connection segment to bring the service directly to the final users. The essential aim of this integration is to get the best of both worlds: the high capacity offered by optical fiber networks and the mobility and ubiquity offered by wireless networks. Such integration also grants a critical cost advantage, since deploying wireless transceivers is in general simpler and less expensive than deploying optical fibers. Last but not least, the integration offers a convenient way of providing a backup in case of failing connections. In Project ROUAN, we aim at developing mathematical programming models for the integrated and robust design of fixed and wireless components of a Fi-Wi network. As a general theoretical objective, we aim at enlarging the knowledge about Robust Optimization by investigating the topic of how to construct uncertainty sets using available historical data.

    http://www.zib.de/dandreagiovanni/ROUAN.html
  • MI5

    Network and mechanism design for metropolitan infrastructures

    Prof. Dr. Max Klimm

    Project heads: Prof. Dr. Max Klimm
    Project members: Antje Bjelde / Jan Hackfeld
    Duration: -
    Status: running
    Located at: Technische Universität Berlin

    Description



    https://www.coga.tu-berlin.de/v_menue/projects/network_and_mechanism_design_for_metropolitan_infrastructures/




Financed by others

  • MI-AP1

    Competitive Exploration of Large Networks

    Dr. Yann Disser / Prof. Dr. Max Klimm

    Project heads: Dr. Yann Disser / Prof. Dr. Max Klimm
    Project members: -
    Duration: 01.06.2014 - 31.05.2017
    Status: running
    Located at: Technische Universität Berlin

    Description

    The goal of this project is to deepen the understanding of algorithms that operate on very large networks and the dynamics that arise from the competition or cooperation between such algorithms. To achieve this goal, we want to combine models and techniques from the areas of graph exploration and algorithmic game theory. To date, the literature in these areas is mostly disjoint. By closing this gap, we hope to develop new insights into the important algorithmic and economic challenges faced in large networks, most prominently in those that are part of the Internet.

    https://www.coga.tu-berlin.de/v-menue/projects/competitive_exploration_of_large_networks/?no_cache=1&tx_sibibtex_pi1[sort]=year%3A0
  • MI-AP2

    Algorithms for Solving Time-Dependent Routing Problems with Exponential Output Size

    Prof. Dr. Martin Skutella

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

    Description

    Within the past decade, routing problems in various transportation networks have experienced a dramatic explosion of the size of data involved. This phenomenon has various causes, one of them being the demand for models and solutions that also take the dynamic (i. e., time-dependent) development of flow in transportation networks into account. Prominent examples are route guidance systems for traffic networks, evacuation planning for major districts or entire cities, and planning problems in huge logistics networks.

    In the efficient algorithms and mathematical programming communities, fast methods for the solution of static (i.e., not time-dependent) routing problems have been developed over the past 50-60 years. In contrast, much less attention has been paid to the study of dynamic routing problems. This project addresses fundamental questions in the area of dynamic network flows and time-expanded networks which constitute an appropriate tool for modeling and solving time-dependent routing problems. Special emphasis is put on earliest arrival flows which capture the essence of evacuation planning.

    An interesting artifact of dynamic flow problems is that static (i.e., small) input data leads to dynamic (i.e., big) output data. For such problems, whose solution size might be exponential in the input size, traditional complexity theory hardly explains their true difficulty. Other prominent examples can be found in parametric optimization, multi-criteria optimization, and enumeration problems. Beyond the main focus of this project, time-dependent routing, and on a more fundamental level, we aim at a better understanding of the curse of exponential output size, that is, the complexity of such problems and algorithms for their solution.

    https://www.coga.tu-berlin.de/v_menue/projects/algorithms_for_solving_time_dependent_routing_problems_with_exponential_output_size/
  • MI-AP3

    Probabilistic methods for ad-hoc networks with mobile relays

    Prof. Dr. Wolfgang König

    Project heads: Prof. Dr. Wolfgang König
    Project members: -
    Duration: 01.09.2014 - 31.08.2017
    Status: running
    Located at: Weierstraß-Institut

    Description

    The latest LTE-Advanced standard introduces fixed relays to reduce the number of base stations (substantially reducing costs) and improve service quality. The relay concept is extended to include users' devices as mobile relays, to further strengthen these benefits. The impact of mobile relays strongly depends on the environment (number of users, their locations and mobility). We investigate a a novel combination of rigorous probability theory and simulation-based systems engineering to study the benefits of this new concept for network operators.

    http://www.wias-berlin.de/research/lgs/lg4/index.jsp?lang=1
  • MI-AP5

    Combinatorial switching for routing gas flows

    Prof. Dr. Dr. h.c. mult. Martin Grötschel / Dr. Benjamin Hiller / Prof. Dr. Caren Tischendorf

    Project heads: Prof. Dr. Dr. h.c. mult. Martin Grötschel / Dr. Benjamin Hiller / Prof. Dr. Caren Tischendorf
    Project members: -
    Duration: 01.10.2014 - 30.06.2018
    Status: running
    Located at: Humboldt Universität Berlin / Konrad-Zuse-Zentrum für Informationstechnik Berlin

    Description

    The goal of this subproject is to develop algorithmic fundamentals for the efficient treatment of switching decisions in gas networks. In particular, this involves the modelling and algorithmics of the switching operations in compressor stations, since these pose a significant source of modelling and runtime complexity. The set of feasible operating points of a compressor station is, in general, non-convex, in some circumstances even non-connected. However, it can be well approximated by the union of convex polyhedra. Hence, the treatment of such structures in MIPs and MINLPs will be the main focus of research in this subproject. While being motivated by the optimization of gas networks, the methods to be developed will be relevant for many applications of MIPs and MINLPs.
    Known techniques for modelling unions of polyhedra as the feasible set of a MIP rely on the inequality description of the underlying polyhedra. In contrast to this, another approach adapted to the geometric properties of the overall set can be considered. More precisely, the goal is to find and analyze a hierarchical description of a non-convex set that provides an as good as possible polyhedral relaxation on each level. This hierarchy can then be used by suitable branching strategies in the branch-and-bound procedure for solving MINLPs.
    In the long term, this subproject of SFB/TRR 154 is aiming at the development of real-time methods for obtaining combinatorial decisions. Furthermore, since the transient control of gas networks requires the successive solving of many similar MIPs/MINLPs, reoptimization techniques come into view that use known information from previous optimization problems in order to reduce running time. For these, a detailed analysis of the problem structure and a deeper understanding of the complex MIP/MINLP solving process will be an essential topic of research.

    http://trr154.fau.de/index.php/en/subprojects/a04e
  • 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.2018
    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.2018
    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.2018
    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.2018
    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-AP10

    Centralized Respository for Test Data

    Prof. Dr. Thorsten Koch

    Project heads: Prof. Dr. Thorsten Koch
    Project members: -
    Duration: 01.10.2014 - 30.06.2018
    Status: running
    Located at: Konrad-Zuse-Zentrum für Informationstechnik Berlin

    Description

    The subproject Z02 aims for a central database of realistic gas network data in standardized formats, and providing interfaces to allow an easy access to the data. This common data standard and common pool of test data drive the workflow and cooperation of all subprojects. A gas network is described by many parameters. Experiences show that it is a very hard task to generate realistic data for gas networks with no access to real data of existing networks.This subproject cooperates with the biggest German network operator, Open Grid Europe GmbH, to compile test data from real gas network data. The generated test data will extend the existing GasLib library for stationary networks. This database relieves other subprojects from generating their own test data, and provides common test cases for them. So, different subprojects can compare their results more easily, since they use the same underlying data. One focus of the subproject Z02 is to standardize the data formats used, and to provide interfaces to them.This interfaces ease the data access for others. The usage of the same data structure throughout the different subprojects leads to more compatible programs and an easier cooperation. The overall goal of the subproject Z02 is to compile a selection of data sets, which can be used to run different demonstration scenarios. The data sets and their descriptions will be published, such that transparency and reproducibility of the results are assured.

    http://trr154.fau.de/index.php/en/subprojects/z02e
  • 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.2018
    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
  • MI-AP19

    Compressive Sensing Algorithms for Structured Massive MIMO

    Prof. Dr. Gitta Kutyniok

    Project heads: Prof. Dr. Gitta Kutyniok
    Project members: -
    Duration: 01.10.2015 - 31.03.2018
    Status: running
    Located at: Technische Universität Berlin

    Description

    Massive MIMO, i.e., very large scale multiuser multi-antenna technology, is widely expected to play a fundamental role in meeting the target performance oft he future generation of wireless/cellular networks, commonly indicated as 5G. The key idea is that by scaling up the number of jointly processed antennas at the infrastructure side (i.e., in the base stations), the wireless channel, notoriously affected by random propagation effects, converges to a deterministic limit in which the network behaves in a predictable and very desirable manner, where intra-cell multiuser interference can be nulled by precoding, and intra-cell interference can be easily controlled. Massive MIMO has been widely analyzed under simple independent and identically distributed channel statistics, and under the naive assumption that the precoding/beamforming operations can be implemented by standard baseband signal processing (fully digital domain). However, a major obstacle in the implementation of Massive MIMO is represented by the very high complexity of the signal acquisition, requiring to demodulate and sample the output of hundreds of antennas. In this project, we propose to exploit the fine structure oft he wireless scattering channel in the asymptotic regime of a large number of antennas, in order to develop a low-complexity structured approach to Massive MIMO. The key observation is that the channel (random) vectors are spatially correlated, and therefore they are sparse in the domain of their Karhunen-Loeve basis. Hence, ideas and techniques from sparse signal processing (sensing and reconstruction) become instrumental to devise new tranceivers architectures, which eventually make Massive MIMO implementable in practice. The central questions that we propose to investigate include: finding universal sparsifying bases or frames to represent general channel spatial correlations; consider wideband channels with sparsity in both the angular and delay domain; understand the tradeoffs and the methods of treating sparsity in the continuous rather than in the discretized domain; understanding the tradeoff, in terms of stable reconstruction of sampling rate versus quantization resolution; consider sparse signal separation in multiuser environments with multiple sparse interferers in the angle-delay and time domain; developing dimensionality reduction techniques that make Massive MIMO affordable also for Frequency-Division Duplexing systems. The proposed research spans across Communications, Information Theory, Signal Processing and Mathematics. The PI team is highly qualified, involving two PIs in the EECS Department and one PI in the Mathematics Department of TU-Berlin. Two PhD students (full time) and two MS/BS students (part-time) will be jointly supervised and collaborate in the research project.

    https://www.ti.rwth-aachen.de/SPP1798/CSMIMO.html