Selection of Current Research Topics

Auction Mechanisms for Network Procurement

The allocation of scarce resources can be handled via auction mechanisms. We consider a network procurement context where an auctioneer wants to buy connections from suppliers, a variant of the Steiner tree problem. In this project, we assess which approximation algorithms can be implemented as strategy-proof mechanisms and conduct an extensive computational study.

Participating Researchers

Martin Bichler, Richard Littmann, Stefan Waldherr

Fleet Rebalancing in Carsharing

Free-floating and one-way carsharing operators such as Car2Go, DriveNow or SixtShare face the challenge that demand is not necessarily balanced. Therefore, operators rebalance their fleets by moving vehicles from low demand areas to higher demand areas. We answer the following research questions using advanced optimization methods and machine learning techniques: (i) What are the best models and organizational concepts for rebalancing based on features of the fleet or environment? (ii) How do the presence of competition and different business models change optimal rebalancing?

Participating Researchers

Layla Martin, Stefan Minner, Andreas S. Schulz, D. Pocas, M.G. Speranza

From Unsupervised to Supervised Learning

One powerful and widely used tool, in machine learning — especially in the context of classification — are data transformations. Recently, a “Transformation by Conditional Probabilities” combined with clustering techniques was proposed and studied in applications. For this project, we build on this idea: We generalize it, strengthening and utilizing the connection to tomography. Further, we apply it to convex bodies, creating a link to convex geometry.

Participating Researchers

Peter Gritzmann, Anja Kirschbaum

Geometric Clustering in Shared Mobility

Over the last years, vehicel sharing services (e.g. bikes or cars) have established themselves as prominent factors in the future of urban mobility. One aspect influencing the success of a shared mobility system in terms of profitability as well as customer satisfaction is precisely anticipating the demand and rebalancing the system to serve it. 

In this project, we apply techniques from geometric/balanced clustering to identify and analyse patterns in the usage data of shared mobility providers e.g. in order to provide a basis for such tasks.

Participating Researchers

Peter Gritzmann, Stefan Minner, Anja Kirschbaum

Micro-Hubs in City Logistics

Logistics decisions can potentially play a critical role in sustainable development of cities. One of the pressing issues facing urban areas is last-mile delivery that can be addressed by city logistics concepts for urban freight transport. In this project, micro-hubs, i.e., small (partly mobile) logistics facilities are used in the heart of urban areas to consolidate goods for end-customer delivery and we aim to find suitable micro-hub locations with tour planning aspects of last-mile delivery taken into account. We propose an exact algorithmic approach based on a Benders' decomposition algorithm to solve this problem.

Participating Researchers

Ramin Barzanji, Stefan Minner, Maximilian Schiffer

Minimization of Weighted Completion Times in Path-based Coflow Scheduling

Parallel computing frameworks are a central element of today’s IT architecture and services, especially in the course of Big Data. Coflow Scheduling models communication requests in such frameworks where multiple data flows between shared resources need to be completed before computation can continue. We study Path-based Coflow Scheduling, a generalized problem variant that considers coflows as collections of flows along fixed paths on general network topologies with node capacity restrictions. Applications of this generalized approach arise in grid computing projects and inter-datacenter communications.

Participating Researchers

Alexander Eckl, Luisa Peter, Maximilian Schiffer, Susanne Albers

Online Matching

Ride sharing platforms like Uber, Lift or Didi use mathematical algorithms to match customers requesting trips with drivers offering rides. The problem of matching drivers and customers without knowing future requests in advance is known as the online matching problem. In recent years, online matching has gained a lot of attention and different variants of the problem have been studied. In this project, we work towards improved approximation algorithms and lower bounds for some of these variants.

Participating Researchers

Alexander Eckl, Anja Kirschbaum, Marilena Leichter, Kevin Schewior

Online Matching Market Analysis

Due to the emergence of online platforms in recent years, the online matching market has subverted the traditional market mechanisms. For example, Uber's matching platform has a big impact on traditional taxi rides. We are committed to researching and comparing the different matching policies between different platforms, and designing and analyzing efficient algorithms on specific issues, such as pricing.

Participating Researchers

Donghao Zhu, Martin Bichler, Stefan Minner

Optimal Placement of Recharging Infrastructure for Electric Vehicles in the Urban Environment

In recent years, there were various governmental efforts to promote electric vehicles in order to cut (local) emissions in the transport sector. In particular in the urban environment, the recharging cycle for those vehicles cannot be compared to the traditional refueling methods in the private transport sector - thus, the placement of charging infrastructure is a wide open field of research. We focus on an agent-based approach for solving this problem for both big cities and a large penetration rate of electric vehicles in order to evaluate, whether current dimensioning and positioning strategies are realistic.

Participating Researchers

Stefan Kober, Stefan Weltge

Parallelization Models for Cluster Computing

As a result of the technological developments and breakthroughs of the past decades, large and extensive data sets are available to us today. In order to benefit from these big data sets, e.g. by predicting natural disasters or investigating new medical treatment methods, we face a number of challenges. Amongst them is the question of how to store and transfer data in general. MapReduce, Spark and Dyrad are frameworks developed for the efficient processing of such large data sets. MapReduce, for example, does so by distributing the data to multiple systems, processing the tasks in parallel and aggregating the results afterwards.

We are investigating a mathematical framework that models the parallelization and distribution of data processing tasks across multiple clusters.

Participating Researchers

Marilena Leichter, Andreas S. Schulz

Production planning for seasonal and uncertain demand

Matching supply and demand is especially difficult when demand has a strong seasonal pattern and resources and capacity have to be used efficiently. To manage uncertainty and integrate the evolution of demand forecasts, we investigate data-driven stochastic programming methods and implement them in optimization models. The performances of the methods in terms of costs and customer satisfaction are investigated on a real-world case study in the chemical industry.

Participating Researchers

Alexandre Forel, Martin Grunow

Re-ranking Search Results in a Web Search

Web search engines like Google, Yahoo! Search, Bing and Ecosia display their search results for a specific key word in an ordered list. Users are not necessarily interested in the same search results, but only in a particular subset. To meet the needs of the users, a good ranking should minimize the average time to find the desired search result over all user types. In this research project, we study a mathematical framework for re-ranking search results in a web search. The aim is to develop new approximation algorithms and to study variants and mathematical generalizations of the problem.

Participating Researchers

Felix Happach, Marilena Leichter, Andreas S. Schulz

Robust Auction Design

Optimal auction design is one of the most well-studied and fundamental problems in (algorithmic) mechanism design. In the standard Bayesian approach, it is assumed that the bidders draw their valuations for an item from a prior joint distribution, which is known to the seller. In many applications though, completely determining the actual distribution would require enormous resources. Motivated by this, we study the problem of revenue maximization in settings where the seller has limited information about the valuation distribution.

Participating Researchers

Alexandros Tsigonias-Dimitriadis, Yiannis Giannakopoulos, Diogo Poças

Sample-Based Prophet Inequalities

Posted-price mechanisms are probably the simplest and most common mechanisms for selling goods in practice. Around a decade ago, the first exciting connections between posted pricing and the prophet inequality were introduced.  Combining and extending ideas from the secretary problem and the prophet inequality, two important results in optimal stopping theory, we develop new models and explore their connections to pricing.

Participating Researchers

Alexandros Tsigonias-Dimitriadis, José Correa, Laurent Feuilloley, Tim Oosterwijk

Scheduling Jobs to Minimize Active Time

In this research project we investigate a mathematical problem, that provides an abstract framework for several scheduling problems. For example, it models the impact of maintenance work on railway traffic or the active time of servers, given a set of tasks that needs to be processed. We develop new combinatorial approximation algorithms, study the computational complexity and give polynomial-time algorithms for several classes of instances motivated by the two applications mentioned above.

Participating Researchers

Marinus Gottschau, Marilena Leichter, Andreas S. Schulz

Scheduling with Explorable Uncertainty

In scheduling environments, uncertainty is a common consideration for optimization problems. Sometimes, unknown information can be attained through investing some additional resources, computing power or money. Explorable uncertainty models obtaining additional information for a problem at a given cost during the runtime of an algorithm. In this project, we consider a natural extension where non-unit costs allow for a wider range of problems. Applications include for example cost and duration estimates in construction work, medical consultation or user survey predictions.

Participating Researchers

Susanne Albers, Alexander Eckl

Teams Formation and Routing for Ground Handling at Airports

The efficient management of ground handling at airports is crucial to avoid flight delays. Ground workers are grouped into teams and assigned to an aircraft, which they have to handle after landing or prepare for the next flight. In this project, we propose an algorithm for optimizing the execution of the ground handling tasks on an operational level.

Participating Researchers 

Giacomo Dall'Olio, Rainer Kolisch, Maximilian Schiffer

Trading Airport Timeslots

Access to major airports is granted through the assignment of airport time slots. Market mechanisms need to take into account synergistic valuations of airlines for departure and arrival time slots, as well as financial constraints of the participating airlines for the many time slots available. We introduce bilevel integer optimization models for airport time slot trading and compute core-stable outcomes, i.e. allocations and prices such that no coalition can beneficially deviate.

Participating Researchers

Martin Bichler, Richard Littmann, Stefan Waldherr

Value of Autonomous Vehicles in Mobility-as-a-Service Solutions

During the 2010’s, many car manufacturers as well as technology companies have developed prototypes for self-driving cars, and mass-production is to be expected in the next decade. For operators of carsharing and ridesharing services, autonomous vehicles can help to reduce total costs, if operational benefits due to lower personnel requirements  compensate for higher investment costs. In this project, we study optimal fleet sizing and composition, while catering for optimal rebalancing of the fleet.

Participating Researchers

Layla Martin, Stefan Minner, Maximilian Schiffer, M. Pavone