Efficient Computation of the Prokhorov Metric for Finitely Supported Distributions (joint work with C. Drescher and J. Schwinn)

18.03.2019 17:00 - 18:00 | HS 7 OMP1 (#1.303)


On the space of probability measures on a metric Polish space, the Prokhorov metric is among the most popular distances between probability distributions. As it is the sole metric equivalent to the weak topology without further assumptions, it is usually mainly considered from a theoretical point of view. In this presentation, we want to highlight that although the definition of the Prokhorov metric seems rather stodgy, its computation is noticeably not more involved than the computation of the much more popular Wasserstein metric. For this purpose, we investigate the computation of the Prokhorov metric for finitely supported distributions. We especially compare our approach to the only other related work by Garel and Masse (2009). Specifically, we demonstrate that their fixed point approach fails for specific problems, while their max flow approach can be significantly improved. By distinguishing different settings, we are able to provide algorithms with proven correctness, together with worst case complexities. We conclude with a quasilinear algorithm for the most important case of real numbers with the usual metric. If time allows we will also briefly cover known and unknown inequalities concerning the Prokhorov metric, as well as its asymptotic behavior. Finally, we also shed some light on the connection of the Prokhorov metric to the Wasserstein infinity metric. 


01.04.2019 17:00 - 18:00 | HS 7 OMP1 (#1.303)

 Stable Matching Models with Applications to Junior Doctor Allocation and Children Adoption

06.05.2019 16:45 - 17:45 | HS 7 OMP1 (#1.303)

In a stable matching problem, we are given two sets of agents, each of whom ranks some (or all) the members of the other set in order of preference, indicating their level of desire to be matched to each other. A solution to the problem is a pairing of all agents such that no two agents form a blocking pair, that is, a pair that are not currently matched together, but would prefer to be matched to each other rather than to their currently assigned partners. In this talk I will introduce new models for the Stable Marriage problem with Ties and Incomplete lists, with applications to pairing children with adoptive families, and for its many-to-one generalization, the Hospitals/Residents Problem with Ties, with applications to the allocation of junior doctors. 

 An Exact Solution Framework for Multi-Trip Vehicle Routing Problems with Time Windows

13.05.2019 16:45 - 17:45 | HS 7 OMP1 (#1.303)

Multi-Trip Vehicle Routing Problems (MTVRP) generalize the well-known VRP by allowing vehicles to perform multiple trips per day. MTVRPs have received a lot of attention lately because of their relevance in real-life applications, e.g., in city logistics and last-mile delivery. Several variants of the MTVRP have been investigated in the literature, and a number of exact methods have been proposed. Nevertheless, the computational results currently available suggest that MTVRPs with different side-constraints require ad-hoc formulations and solution methods to be solved. Moreover, solving instances with just 25 customers can be out of reach for such solution methods. In this talk, we proposed an exact solution framework to address four different MTVRPs proposed in the literature. The exact solution framework is based on a novel formulation that has an exponential number of variables and constraints. It relies on column generation, column enumeration, and cutting plane. We show that this solution framework can solve instances with up to 50 customers of four MTVRP variants and outperforms the state-of-the-art methods from the literature.

 A Kernel Search Heuristic for the Multi-Vehicle Inventory Routing Problem (joint work with G. Guastaroba, D. L. Huerta-Muñoz, M. Grazia Speranza)

20.05.2019 16:45 - 17:45 | HS 7 OMP1 (#1.303)

We study an inventory routing problem where the goal is to determine an opti-mal distribution plan to replenish a set of customers, by routing a limited fleet ofcapacitated vehicles over a discrete planning horizon. Each customer consumes aper period quantity of products and have a maximum inventory capacity. Productscan be distributed by a supplier to the customers in advance compared to theirconsumption, provided that their inventory capacity is not violated. The goal is tominimize the total distribution cost, that comprises the routing and the inventorycosts. We develop a novel matheuristic approach to solve this problem. The algo-rithm is based on Kernel Search (KS), a heuristic framework that has been shownto find high-quality solutions for a number of combinatorial optimization problems.The basic idea of KS is to identify subsets of the decision variables and then solving,using a general-purpose solver, a sequence of Mixed-Integer linear Programs (MIPs),each one restricted to a subset of variables. Extensive computational experimentsare conducted on a very large set of benchmark instances. The results show thatKS outperforms state-of-the-art heuristic algorithms. It finds 103 new best-knownsolutions out of 240 large-scale instances. 

 Two Resource Allocation Problems in Global Health

27.05.2019 16:45 - 17:45 | HS 7 OMP1 (#1.303)

This talk will focus on a resource allocation of healthcare resources in low and middle income countries. The talk is stimulated by consultancy work for a major donor of development aid. We will discuss two problems - one of balancing "vertical" investments in disease programmes (such as purchasing bednets for malaria) with investments which strengthen the health system as a whole (e.g. improving systems for vital registration); the other of deciding the correct balance of funding between a donor and a recipient. We will model these problems with quadratic and bilevel programmes respectively and discuss the structural behaviour of such models. 

INFORMS TSL Workshop 2019

Date: July 15-18, 2019
Location: Sky Lounge at the Faculty of Business, Economics and Statistics

The next INFORMS TSL Workshop will be held from July 15-18, 2019 at the University of Vienna. The topic of the workshop is "Transportation in the sharing economy". Sharing economy refers to collaborative consumption. It is typically organized through platforms that facilitate the exchange of goods or services. Given an increasing pressure to act economically and ecologically efficient, mechanisms that help to benefit from idle capacities are on the rise. Both transportation companies and heavy users of transportation services need to learn how to play in a world of shared idle capacities. We anticipate talks on various types of collaborations, crowd delivery, carsharing, carpooling, ridesharing, etc.