Successfully completed 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: 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: Robert Gruhlke / 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: Antje Bjelde
    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/




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: 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-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-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-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