Prof. Dr. Martin Skutella

Projects as a project leader

• 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

• 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

• MI10

  Acyclic network flows

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

  Project heads: Dr. Benjamin Hiller / Prof. Dr. Thorsten Koch / Prof. Dr. Martin Skutella
  Project members: Dr. Kai-Helge Becker
  Duration: 01.06.2017 - 31.12.2019
  Status: running
  Located at: Konrad-Zuse-Zentrum für Informationstechnik Berlin
  

  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.
  
  http://www.zib.de/projects/acyclic-network-flows

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

• MI12

  Dynamic Models and Algorithms for Equilibria in Traffic Networks

  Prof. Dr. Martin Skutella

  Project heads: Prof. Dr. Martin Skutella
  Project members: Leon Sering
  Duration: 01.06.2017 - 31.12.2019
  Status: running
  Located at: Technische Universität 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.
  
  http://www.tu-berlin.de/?id=186306

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

  Efficient network flow methods for non-steady-state gasflows

  Prof. Dr. Martin Skutella

  Project heads: Prof. Dr. Martin Skutella
  Project members: -
  Duration: 01.10.2014 - 30.06.2022
  Status: running
  Located at: Technische Universität Berlin
  

  Description

  The goal of this subproject is to apply network flow theory to simplified models for gas pipelines and related transportation networks. Network flow theory has proven itself to be a powerful and valueable tool for solving complex problems in many areas of application, like traffic networks, telecommunication networks, and logistic networks. All of these networks can be designed and operated using network flow algorithms, which exhibit a very efficient runtime behaviour, making them capable of handling the large instances occuring in practice. In this subproject, we strive to employ network flow algorithms for solving problems in gas and related networks. Conventional network flow theory is insufficient to describe gas networks, since it neither accounts for pressures in nodes, nor for the non-linear dependency of the flow from the pressure in nodes. However, there are several problems in gas networks which occur in a similar form in network flow theory and are known and well understood there, for example generalized or length-bounded flows. Furthermore, non-linear relationships in other aspects like for example the flow velocity in traffic networks, have been studied and solved by network flow theory. As a base for our models we use a model based on the Weymouth equations, which can be solved using convex minimum cost flows. This flow model and its solution techniques can be generalized from the stationary to the transient case, analogous to how classic network flows can be generalized to dynamic network flows. For solving dynamic networks (approximately), there are useful techniques known from network flow theory, e.g. adaptive time-expanded networks, which have a great number of applications. These techniques are to be made useable for transient gas flows in this subproject. Gas networks usually contain a number of active elements - valves, compressors, and so on - which require integral decisions which have a significant impact on the gas flow. Therefore, these elements have to be incorporated in the network flow model. This can be handled by Branch & Bound based methods, or by adaption of techniques from network design. For Branch & Bound based techniques it is crucial to identify infeasible solutions as fast as possible. In gas networks, this means identifying partial configurations of active elements which imply infeasiblity. Therefore, analysis of infeasiblity will be a focus of the research done in this subproject. By developing efficient models and solution techniques for gas networks and characterizing infeasibility in these models, this subproject will contribute for Demonstrator 1, with a special focus on large gas networks.
  
  http://trr154.fau.de/index.php/en/subprojects/a07e