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

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

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

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

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

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

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

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

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

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

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

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

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

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