Mathematics for Metropolitan Infrastructure

Duration: - Status: completed Located at: Technische Universität Berlin (TU 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

Website

X Close project

Duration: - Status: completed Located at: Technische Universität Berlin (TU 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.

Website

X Close project

Duration: - Status: completed Located at: Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)

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

Website

X Close project

Duration: - Status: completed Located at: Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)

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.

Website

X Close project

Duration: - 31.05.2017 Status: completed Located at: Technische Universität Berlin (TU 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.

Website

X Close project

Duration: 01.06.2017 - 31.12.2018 Status: completed Located at: Technische Universität Berlin (TU 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.

Website

X Close project

Duration: 01.06.2017 - 31.12.2019 Status: running Located at: Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)

Description

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

Website

X Close project

Duration: 01.06.2017 - 31.12.2019 Status: running Located at: Humboldt Universität Berlin (HU Berlin)

Description

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

Website

X Close project

Duration: 01.06.2017 - 31.12.2017 Status: completed Located at: Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)

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.

Website

X Close project

Duration: 01.06.2017 - 31.12.2019 Status: running Located at: Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)

Description

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

Website

X Close project

Duration: 01.06.2017 - 31.12.2018 Status: completed Located at: Weierstraß-Institut (WIAS Berlin)

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.

Website

X Close project

Duration: 01.06.2017 - 31.12.2019 Status: running Located at: Technische Universität Berlin (TU Berlin)

Description

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

Website

X Close project

Duration: 01.06.2017 - 31.12.2018 Status: completed Located at: Humboldt Universität Berlin (HU 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.

Website

X Close project

Duration: 01.06.2017 - 31.12.2019 Status: running Located at: Technische Universität Berlin (TU Berlin)

Description

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

Website

X Close project