Overview

• Application Fields
  • Clinical Research and Health Care
  • Metropolitan Infrastructure
  • Optical Technologies
  • Sustainable Energies
  • Geometric Design and Visualization
  • Education and Outreach
• Projects
  • Running projects
  • Successfully completed projects
• Publications
• Scientists
• Preprints
• Institutional Cooperation
• Archiv 02-14

Successfully completed projects

• 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: completed
  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: Dr. Anastasia Thöns
  Duration: -
  Status: completed
  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: completed
  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: completed
  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: -
  Duration: - 31.05.2017
  Status: completed
  Located at: Technische Universität Berlin
  

  Description

  Metropolitan infrastructures like public roads, telecommunication networks, the electric grid, and public transport are a key factor for quality of life as well as cultural and economic development. However, their installation and maintenance often requires huge efforts both in terms of financial or personal investments, and in terms of environmental burden. The huge effect of infrastructure design decisions on nature, society, and economy make sound infrastructure planning indispensable.
  
  A main characteristic of infrastructure systems is that they are used by a large number of economically independent entities that strive to optimize their private goals instead of optimizing the overall network usage. This fact is apparent for publicly available services like public roads or transport, but matters also for electricity and gas networks that are operated and used by independent economic actors.
  
  Since the last 50 years, such systems of independent decision makers are analyzed within the theory of noncooperative games. Based on the works of Nash and Wardrop, the central concepts of game theory are Nash equilibria and Wardop equilibria. Roughly speaking, a system is in equilibrium when none of its users can minimize its personal costs of the network usage by altering its usage patters. To optimize the design and maintenance of the infrastructure networks above it is imperative to understand the conditions under which equilibria emerge, to assess their quality, and to design mechanisms that lead to good equilibria, e.g., in terms of a provable performance guarantee. These are the main goals of this project.
  
  https://www.coga.tu-berlin.de/v_menue/projects/network_and_mechanism_design_for_metropolitan_infrastructures/

• MI6

  Geometry of Equilibria for Shortest Path

  Prof. Dr. Michael Joswig

  Project heads: Prof. Dr. Michael Joswig
  Project members: Dr. Benjamin Schröter
  Duration: 01.06.2017 - 31.12.2018
  Status: completed
  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/

• MI9

  Solving multi-objective integer programs

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

  Project heads: Prof. Dr. Ralf Borndörfer / Prof. Dr. Martin Skutella
  Project members: Sebastian Schenker
  Duration: 01.06.2017 - 31.12.2017
  Status: completed
  Located at: Konrad-Zuse-Zentrum für Informationstechnik Berlin
  

  Description

  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

• 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: 01.06.2017 - 31.12.2018
  Status: completed
  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/

• 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: completed
  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-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: completed
  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: completed
  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.12.2017
  Status: completed
  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-AP4

  Models, algorithms and complexity for scheduling under uncertainty

  Project heads: -
  Project members: -
  Duration: 01.04.2012 - 31.03.2016
  Status: completed
  Located at: Technische Universität Berlin
  

  Description

  The vast majority of scheduling research assumes complete information about the problem instance. In most real-world applications, however, uncertain input that is gradually revealed during schedule execution is an omnipresent issue. Unlike its deterministic counterpart, the diverse field of scheduling under uncertainty is not well understood from an algorithmic point of view. Moreover, most current approaches on algorithm’s design assume arbitrary algorithmic flexibility and neglect practice-driven limitations on adaptivity. In this project we design algorithmic and analytic tools for solving important scheduling problems with uncertain input, such as unreliable machines, stochastic job processing times, or unknown job arrival times. Our major goal is to study thoroughly the tradeoff between the performance of an algorithm and the amount of adaptivity it requires. On the one hand, we aim for best possible algorithms which are potentially highly dynamic, i.e., scheduling decisions may adapt arbitrarily to the instantiated problem data. On the other hand, we are interested in good but simple algorithms that respect practice-driven adaptivity restrictions. We analyze what kind and what amount of adaptivity an algorithm needs to achieve a certain performance guarantee. Our main tools come from approximation algorithms, combinatorial optimization, mathematical programming, and probability theory, and our investigations integrate the concepts of universal and robust solu- tions. We study fundamental theoretical questions on practically relevant algorithms for problems from stochastic, online, and real-time scheduling.
  
  https://www.coga.tu-berlin.de/megow-group/junior_research_group_dr_nicole_megow/

• 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: completed
  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-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: completed
  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-AP11

  TEAM - Tomorrow's elastic, adaptive mobility

  Prof. Dr. Rolf Möhring

  Project heads: Prof. Dr. Rolf Möhring
  Project members: -
  Duration: 01.11.2012 - 31.03.2016
  Status: completed
  Located at: Technische Universität Berlin
  

  Description

  TEAM stands for Tomorrow’s Elastic Adaptive Mobility. It turns static into elastic mobility by joining drivers, travellers and infrastructure operators together into one collaborative network. Thereby TEAM explicitly takes into account the needs and constraints of all participants and the network itself.
  
  The vision is to use mobile devices such as smartphones to significantly improve transportation safety and efficiency, implementing environmental aspects. This includes contribution towards the objective of reducing fatalities in the EU, not only addressing drivers but all road users – including passengers and pedestrians. In this way, drivers, travellers and infrastructure are meant to act as a team, adapting to each other and to the situation, creating optimised mobility conditions.
  
  The success of the project will be demonstrated and validated via innovative applications for end-users and a Europe-wide mobility experiment to illustrate the systems’ benefits in a pan-European setting.
  
  The project duration is four years. It has started in November 2013 as a joint initiative of 27 partners (now: 28), ranging from car manufacturers to telecommunication providers, research institutes, road infrastructure operators, traffic managers and more.
  
  http://www.collaborative-team.eu/

• MI-AP12

  RobuNet - Robust Network Design for Large Scale Logistics

  Prof. Dr. Rolf Möhring / Prof. Dr. Martin Skutella

  Project heads: Prof. Dr. Rolf Möhring / Prof. Dr. Martin Skutella
  Project members: -
  Duration: 01.10.2012 - 30.09.2015
  Status: completed
  Located at: Technische Universität Berlin
  

  Description

  Facility location decisions belong to the most important cost drivers in the design of modern logistics networks. Moreover these longterm investments determine the framework for finding cost efficient solutions in tactical and operational planning. This close interrelation between operational cost and longterm investments makes an integrated planning of both aspects desirable.
  
  This integrated approach is even more complex due to the disparate time horizons of both planning aspects. From mathematical point of view, this belongs to the realm of optimizing over scenarios, since the scenario of demands is unknown at the time of investments and the investments have to be convenient for many scenarios. E.g., fluctuations of fuel prices or differing developments of labor costs in different regions constitute relevant uncertainties in designing logistic networks.
  
  In practice it is common to firstly ignore uncertainties in input data and to react a-postiori to changes. It has been shown that with this practice already small fluctuations can lead to much worse results as opposed to a robust optimization, a modelling technique that considers the possible range of fluctuations in input data a priori. A large gap between the actual state of research and the logistic practice has to be closed here. On the other hand, it is essential to the research of robust optimization to understand which kinds of uncertainties appear in practice.
  
  The goal of RobuNet is to develop solutions techniques that are tailored for the use in large scale logistics networks, which requires to link actual mathematical research with practical expertise.
  
  http://www.coga.tu-berlin.de/v-menue/projekte/robunet/

• MI-AP13

  Algorithms for Complex Scheduling Problems

  Prof. Dr. Rolf Möhring

  Project heads: Prof. Dr. Rolf Möhring
  Project members: -
  Duration: 01.10.2009 - 31.03.2015
  Status: completed
  Located at: Technische Universität Berlin
  

  Description

  Real-world scheduling problems are usually much more complex than most of the models that were considered in algorithm theory so far. Typically, optimal solutions cannot be found in reasonable computing time. However in practice, good solutions have to be computed fast. To meet the runtime requirements, mostly (simple) heuristics are established in industry, not taking into account results and techniques that are know for related theoretical problems. We aim to start filling this gap between theory and practice for the following fields of scheduling:
  

  • Integrated Sequencing and Scheduling, a class of problems typically arising in production planning: For a given set of goods, a minimum cost processing sequence has to determined. The cost of a sequence highly depends on the corresponding (non-trivial) scheduling decisions taken, e.g. the scheduling of setup work.
  • Basis Sequencing aims for a minimum cost sequence of a set of given items. In contrast to the previous problem class, the cost incurred by an item solely depends on the neighboring items or on the item's completion time. Basic sequencing problems often occur as a subproblem in integrated sequencing and scheduling, and hence, insights on these problems are of great value.
  • Turnaround Scheduling, a field of scheduling problems which result from shutting down industrial plants for maintenance. These problems are characterized by time-cost tradeoff, precedence constraints, hiring external resources, resource leveling, different working shifts, and risk analysis.

  
  We seek for insights into the structure and complexity of these problems, which then need to be transferred into efficient algorithms, aiming to produce provably good solutions also for large real-world problems within an appropriate computing time. Realistic data is available from cooperations with T.A. Cook Consultants, PSI Metals and Salzgitter Flachstahl, and Sachsenmilch, respectively (10.000 - 100.000 activities for turnaround scheduling, and two examples from sequencing and scheduling, one from coil coating with 20-40 coils, and another one from dairy industry with 30-40 jobs).
  
  http://www.coga.tu-berlin.de/v-menue/projekte/complex_scheduling/

• MI-AP14

  Algorithm engineering for real-time Scheduling and Routing

  Prof. Dr. Martin Skutella

  Project heads: Prof. Dr. Martin Skutella
  Project members: -
  Duration: 01.12.2011 - 31.10.2014
  Status: completed
  Located at: Technische Universität Berlin
  

  Description

  While 20 years ago microprocessors have mostly been used in desktop computer workstations and large-scale computers, they have meanwhile become ubiquitous. They are used in nearly all areas of technology and specifically in safety and mission critical applications. The future vision of the automotive and avionics industry is complete, safe and reliable drive-by-wire and fly-by-wire respectively. Such industrial applications gave rise to the field of computer science which is called real-time scheduling and routing. Whereas classical scheduling deals with the distribution of a finite set of tasks to a set of machines, real-time scheduling deals with recurring tasks which are often periodic and thus appear infinitely often. Since the processors in a real-time system communicate by passing messages, the messages have to be routed through the architecture (modelled as a directed graph) additionally.
  
  The goal of the project is to develop, implement, analyse and test algorithms for real-time scheduling and routing problems using methods of linear and integer programming as well as various scheduling and routing techniques from discrete optimization.
  
  http://www.coga.tu-berlin.de/v_menue/projects/algorithm_engineering_for_real_time_scheduling_and_routing/

• MI-AP15

  Multicriteria Optimisation

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

  Project heads: Prof. Dr. Ralf Borndörfer / Prof. Dr. Martin Skutella
  Project members: -
  Duration: 01.01.2012 - 31.12.2016
  Status: completed
  Located at: Technische Universität Berlin / Konrad-Zuse-Zentrum für Informationstechnik Berlin
  

  Description

  The project "Multicriteria Optimisation" considers mathematical questions and discrete problems within the CRC 1026 "Sustainable Manufacturing". The three sustainability dimensions "economic", "environmental" and "social", respectively, are considered as different objective functions by the project A5. Hence, discrete problems and mathematical questions are modelled by a feasible space of solutions and several objectives which have to be optimised simultaneously. In contrast to the single-criteria case, it is generally not possible to find a solution which optimises all considered objectives simultaneously. Instead one has to deal with trade-offs. For example, the cheapest way to manufacture a certain amount of bicycle frames might not be the environmentally friendliest. A solution that can be improved in at least one objective without getting worse off in the other is called inefficient and will generally be neglected by a decision maker. Hence, only the efficient solutions are interesting from a decision maker's point of view. Besides the mathematical questions about the existence and number of efficient solutions and the algorithmic approaches of how to compute them, the project A5 is also concerned with the modelling of quantitative problems within the CRC 1026. With respect to models the focus and expertise is on mixed integer programming.
  
  We have developed PolySCIP, an open-source and freely available solver which aims at solving multicriteria mixed integer programs with an arbitrary number of objectives. With respect to scenario analysis two tools, tech-con and field-con, were implemented. Exemplary applications like the optimization of process chains for bicycle frame manufacturing, the selection of sustainable welding processes and design decision support are documented.
  
  http://www.sustainable-manufacturing.net/en_GB/subproject-a5

• MI-AP16

  Stability in Networks

  Prof. Dr. Martin Skutella

  Project heads: Prof. Dr. Martin Skutella
  Project members: -
  Duration: 01.01.2013 - 31.12.2015
  Status: completed
  Located at: Technische Universität Berlin
  

• MI-AP18

  Discrete-Valued Sparse Signals - Theory, Algorithms and Applications

  Prof. Dr. Gitta Kutyniok

  Project heads: Prof. Dr. Gitta Kutyniok
  Project members: -
  Duration: 01.10.2014 - 30.09.2016
  Status: completed
  Located at: Technische Universität Berlin
  

  Description

  Over the last decade, compressed sensing (CS) has gained enormous attention, both from a theoretical point of view and from its various applications. The key point in compressed sensing is to solve underdetermined systems of linear equations under the assumption that the unknown vector is sparse, i.e., a signal where only a few non-zero components are present.It is very attractive to use ideas and tools developed in compressed sensing in digital communications. Exemplary scenarios are transmitter-side signal optimization (e.g., peak-to-average power ratio reduction), multiple-access schemes with small duty cycles, source coding schemes, and radar applications. However, in these scenarios the vector/the signal to be recovered (from noisy measurements) may not only be sparse, but it is beneficial that its elements are taken from a discrete set. Hence, discrete sparse signals are extremely relevant in digital communication systems and signal processing. Unfortunately, such signals and the respective recovery algorithms are not yet studied adequately---if at all---in the literature.Consequently, this proposal addresses the application of compressed sensing methodology to the analysis of discrete-valued sparse signals. Effort has to be spent to fundamentally understand the problem from the mathematical side. To this end, we aim to develop a comprehensive theory for the recovery of discrete sparse signals, both from a geometric viewpoint and by adopting analytical results and tools. Moreover, we devise tailored recovery algorithms, thereby interpreting discrete compressed sensing as a link between classical compressed sensing and a multiple-input/multiple-output decoding task. Finally, the application of discrete sparse signals in communications, sensor networks, and for the identification of channel operators will be addressed.
  
  http://gepris.dfg.de/gepris/projekt/257184199?language=en

• 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 - 30.09.2018
  Status: completed
  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

• MI-AP20

  Eigenvalue Analysis and Model Reduction in the Treatment of Disc Brake Squeal

  Prof. Dr. Volker Mehrmann

  Project heads: Prof. Dr. Volker Mehrmann
  Project members: -
  Duration: 01.09.2012 - 31.03.2015
  Status: completed
  Located at: Technische Universität Berlin
  

  Description

  Disc brake squeal is a frequent and annoying phenomenon. It arises from self-excited vibrations caused by friction forces at the pad-rotor interface for an industrial brake model [1] (see Figure 1a and 1b). In order to satisfy customers, the automotive industry has been trying for decades to reduce squeal by changing the design of the brake and the disc. So far, it has found no satisfactory solutions that can be implemented in a systematic way. To improve the situation, several car manufacturers, suppliers, and software companies initiated a joint project, supported by the German Federal Ministry of Economics and Technology, which included two mechanical engineering groups at Technical University (TU) Berlin and TU Hamburg-Harburg, and the numerical analysis group at TU Berlin [1]. The goal of the project was to develop a mathematical model of a brake system with all effects that may cause squeal, to simulate the brake behavior for many different parameters, and to generate a small-scale reduced-order model that can be used for optimization.
  
  https://sinews.siam.org/DetailsPage/TabId/900/ArtMID/2243/ArticleID/443/Eigenvalue-Analysis-and-Model-Reduction-in-the-Treatment-of-Disc-Brake-Squeal.aspx