Laufende Projekte

ECMath finanziert

  • MI6

    Geometry of Equilibria for Shortest Path

    Prof. Dr. Michael Joswig

    Projektleiter: Prof. Dr. Michael Joswig
    Projekt Mitglieder: Benjamin Schröter
    Laufzeit: -
    Status: laufend
    Standort: Technische Universität Berlin

    Beschreibung

    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

    Projektleiter: Prof. Dr. Ralf Borndörfer / Dr. Marika Karbstein
    Projekt Mitglieder: Heide Hoppmann / Dr. Niels Lindner
    Laufzeit: 01.06.2017 - 31.12.2018
    Status: laufend
    Standort: Konrad-Zuse-Zentrum für Informationstechnik Berlin

    Beschreibung

    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.

  • MI8

    Understanding and Improving Traffic with Uncertain Demands

    Prof. Dr. Max Klimm

    Projektleiter: Prof. Dr. Max Klimm
    Projekt Mitglieder: Philipp Warode
    Laufzeit: -
    Status: laufend
    Standort: Humboldt Universität Berlin

    Beschreibung

    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/
  • MI9

    Solving multi-objective integer programs

    Prof. Dr. Ralf Borndörfer / Prof. Dr. Martin Skutella

    Projektleiter: Prof. Dr. Ralf Borndörfer / Prof. Dr. Martin Skutella
    Projekt Mitglieder: Sebastian Schenker
    Laufzeit: 01.06.2017 - 31.12.2017
    Status: laufend
    Standort: Konrad-Zuse-Zentrum für Informationstechnik Berlin

    Beschreibung

    Multi-objective optimization is oncerned with optimizing several conflicting objectives at once.It can be considered as a generalization of single-objective optimization with numerous applications that range from health care, sustainable manufacturing, economics and social sciences to traffic and logistics. Roughly speaking, basically any real-world application that can be modeled as an optimization problem might be considered as a multi-criteria optimization problem if enough data is available. In contrast to the single-objective case, it is generally impossible to compute a single solution that optimizes all objectives simultaneously. Instead, we have to deal with trade-offs and distinguish between non-dominated points that cannot be improved upon (on at least one objective without getting worse at another) and dominated points that can be improved upon. In this project we pursue a new concept to partition the set of non-dominated points. This approach enables us to solve general integer programs by combining the research goals of achieving theoretical efficiency, of implementing practical algorithmic approaches and of being able to approximate the entire set of non-dominated points via a subset of non-dominated points with some kind of approximation guarantee. Furthermore, we aim at making all project results available to the optimization community via implementations to PolySCIP, our solver for multi-objective linear and integer programs.

    https://www.zib.de/projects/solving-multi-objective-integer-programs
  • MI10

    Acyclic network flows

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

    Projektleiter: Dr. Benjamin Hiller / Prof. Dr. Thorsten Koch / Prof. Dr. Martin Skutella
    Projekt Mitglieder: Dr. Kai-Helge Becker
    Laufzeit: -
    Status: laufend
    Standort: Konrad-Zuse-Zentrum für Informationstechnik Berlin

    Beschreibung

    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.

  • MI11

    Data mobility in ad-hoc networks: Vulnerability & security

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

    Projektleiter: Dr. Benedikt Jahnel / Prof. Dr. Wolfgang König
    Projekt Mitglieder: Alexander Wapenhans
    Laufzeit: -
    Status: laufend
    Standort: Weierstraß-Institut

    Beschreibung

    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/people/koenig/?lang=0 / http://www.wias-berlin.de/people/jahnel/?lang=0
  • MI12

    Dynamic Models and Algorithms for Equilibria in Traffic Networks

    Prof. Dr. Martin Skutella

    Projektleiter: Prof. Dr. Martin Skutella
    Projekt Mitglieder: Leon Sering
    Laufzeit: -
    Status: laufend
    Standort: Technische Universität Berlin

    Beschreibung

    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

    Projektleiter: Prof. Dr. Caren Tischendorf
    Projekt Mitglieder: Dr. Jan Philipp Pade / Jonas Pade
    Laufzeit: 01.06.2017 - 31.12.2018
    Status: laufend
    Standort: Humboldt Universität Berlin

    Beschreibung

    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

    Projektleiter: Dr. Guillaume Sagnol
    Projekt Mitglieder: -
    Laufzeit: 01.06.2017 - 31.12.2018
    Status: laufend
    Standort: Technische Universität Berlin

    Beschreibung

    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.





Anders finanziert

  • MI-AP3

    Probabilistic methods for ad-hoc networks with mobile relays

    Prof. Dr. Wolfgang König

    Projektleiter: Prof. Dr. Wolfgang König
    Projekt Mitglieder: -
    Laufzeit: 01.09.2014 - 31.12.2017
    Status: laufend
    Standort: Weierstraß-Institut

    Beschreibung

    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

    Projektleiter: Prof. Dr. Dr. h.c. mult. Martin Grötschel / Dr. Benjamin Hiller / Prof. Dr. Caren Tischendorf
    Projekt Mitglieder: -
    Laufzeit: 01.10.2014 - 30.06.2018
    Status: laufend
    Standort: Humboldt Universität Berlin / Konrad-Zuse-Zentrum für Informationstechnik Berlin

    Beschreibung

    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

    Projektleiter: Prof. Dr. Michael Hintermüller
    Projekt Mitglieder: -
    Laufzeit: 01.10.2014 - 30.06.2018
    Status: laufend
    Standort: Humboldt Universität Berlin

    Beschreibung

    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

    Projektleiter: Prof. Dr. Volker Mehrmann
    Projekt Mitglieder: -
    Laufzeit: 01.10.2014 - 30.06.2018
    Status: laufend
    Standort: Technische Universität Berlin

    Beschreibung

    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

    Projektleiter: PD Dr. René Henrion
    Projekt Mitglieder: -
    Laufzeit: 01.10.2014 - 30.06.2018
    Status: laufend
    Standort: Weierstraß-Institut

    Beschreibung

    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

    Projektleiter: Prof. Dr. Caren Tischendorf
    Projekt Mitglieder: -
    Laufzeit: 01.10.2014 - 30.06.2018
    Status: laufend
    Standort: Humboldt Universität Berlin

    Beschreibung

    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

    Projektleiter: Prof. Dr. Thorsten Koch
    Projekt Mitglieder: -
    Laufzeit: 01.10.2014 - 30.06.2018
    Status: laufend
    Standort: Konrad-Zuse-Zentrum für Informationstechnik Berlin

    Beschreibung

    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

    Projektleiter: Prof. Dr. Martin Skutella
    Projekt Mitglieder: -
    Laufzeit: 01.10.2014 - 30.06.2018
    Status: laufend
    Standort: Technische Universität Berlin

    Beschreibung

    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

    Projektleiter: Prof. Dr. Gitta Kutyniok
    Projekt Mitglieder: -
    Laufzeit: 01.10.2015 - 31.03.2018
    Status: laufend
    Standort: Technische Universität Berlin

    Beschreibung

    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