Prof. Dr. Ralf Borndörfer

Scientist in Charge of Innovation Area Metropolitan Infrastructure

Zuse Institute Berlin
Takustr. 7
14195 Berlin
+49 (0) 30 +49-30-84185-243
borndoerfer@zib.de
Website


Research focus

Combinatorial Optimization, Integer Programming

Projects as a project leader

  • 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
  • MI7

    Routing Structures and Periodic Timetabling

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

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

    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.

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