Abhishek Abhishek
University of Amsterdam

Abhishek@uva.nl

Supervisor Marko Boon, Michel Mandjes, Onno Boxma, Rudesindo Nunez Queija

Title Congestion analysis of unsignalized intersections: The impact of impatience and Markov platooning

Abstract This paper considers an unsignalized intersection used by two traffic streams. A stream of cars is using a primary road, and has priority over the other stream. Cars belonging to the latter stream cross the primary road if the gap between two subsequent cars on the primary road is larger than their critical headways. Several questions that naturally arise. A first relates to the capacity of the secondary road: given the arrival pattern of the cars on the primary road, what is the maximum arrival rate of low-priority cars such that the number of such cars does not explode? In the second place, what can be said about the delay experienced by a typical car at the secondary road? This paper addresses such issues by considering a compact model that sheds light on the dynamics of the considered unsignalized intersection. The model, which is of a queueing-theoretic nature, reveals interesting insights into the impact of the user behavior on the above stability issues.

The contributions of this paper are threefold. First, we obtain new results for the aforementioned model that includes driver impatience. Secondly, we reveal some surprising aspects that have remained unobserved in the existing literature so far, many of which are caused by the fact that the capacity of the minor road cannot be expressed in terms of the mean gap size; instead more detailed characteristics of the critical headway distribution play a crucial role. The third contribution is the introduction of a new form of bunching on the main road, called Markov platooning. The tractability of this model allows us to study the impact of various platoon formations on the main road.

Murtuza Ali Abidini
Eindhoven University of Technology

ali.murtaza121@gmail.com

Supervisors O.J. Boxma, A.M.J. Koonen, J.A.C. Resing

Title Polling systems with retrials and reservation periods

Abstract In this talk we discuss the performance analysis of polling systems with retrials and reservation periods. Here, reservation periods are periods during which customers can make a reservation for service at a station in the subsequent visit period of the server to that station. Customers arriving at any other point in time at a station go in orbit and have to retry to obtain service later on. Amongst others we will discuss queue length analysis at embedded and arbitrary time points, mean value analysis, workload decomposition and pseudo-conservation law. The talk is based on joint work with Onno Boxma and Jacques Resing.

Angelos Aveklouris
Eindhoven University of Technology

a.aveklouris@tue.nl

Supervisors Maria Vlasiou, Bert Zwart, Sem Borst

Title A diffusion approximation in a two-Layered Network

Abstract Motivated by a web-server model, we present a queueing network consisting of two layers. The first layer incorporates the arrival of customers at a network of two single-server nodes. We assume that the inter-arrival and the service times have general distributions. Customers are served according to their arrival order at each node and after finishing their service they can re-enter at nodes several times (as new customers) for new services. At the second layer, active servers act as jobs who are served by a single server working at speed one in a Processor-Sharing fashion. Also, we assume that the degree of resource sharing is limited by choice. This is a Limited Processor-Sharing discipline. Our main result is a diffusion approximation for the process describing the number of customers in the system. Assuming a single bottleneck node and studying the system as it approaches heavy traffic, we prove a state-space collapse property. The key to derive this property is to study the model at the second layer and to prove a diffusion limit theorem, which yields an explicit approximation for the customers in the system.

Joint work with Maria Vlasiou (TU/e), Jiheng Zhang (HKUST) and Bert Zwart (CWI, TU/e).

Xinwei Bai
University of Twente

x.bai@utwente.nl

Supervisor Jasper Goseling,, Richard Boucherie

Title Error bounds for stationary performance of random walks in the quarter plane based on inhomogeneous perturbations
Abstract Random walks in the quarter plane with homogeneous transition probabilities are considered in this work. Given a non-negative reward function on the state space, we are interested in the expected stationary performance. Due to the difficulty of direct derivation of this performance for general random walks, upper and lower bounds are constructed based on the performance of a perturbed random walk.

We consider inhomogeneous transition probabilities for the perturbed random walks, which means that the transition probabilities are different at every state. The bounds are constructed using the Markov reward approach. In the end, an explicit expression for the error bound is given. The error bound result does not depend on the values of the inhomogeneous transition probabilities. Therefore, only the existence of those probabilities is needed. Numerical experiments indicate that inhomogeneous perturbed random walks can give better bounds than perturbations based on homogeneous random walks.

Aleksander Banasik
Wagenigen University

olek.banasik@wur.nl

Supervisors Argyris Kanellopoulos, Frits Claassen, Jacqueline Bloemhof, Jack van der Vorst

Title Eco-efficient mushroom production: dealing with uncertain model parameters
Abstract Until recently food production focused mainly on delivering high quality products at low costs and gave only secondary attention to environmental impact and depletion of natural resources. This trend is changing due to the growing awareness of climate change, shrinking resources, and increasing world population. Multi-objective optimization models have been proposed to quantify trade-offs between conflicting objectives and to derive eco-efficient solutions, i.e. solutions for which environmental performance can only be improved at higher costs. In practice, not all the required information is available in advance due to various sources of uncertainty in food production. In this research a Multi-Objective Optimization model is proposed to support decision making in mushroom production and to evaluate the impact of uncertainty on decision support. The advantages and disadvantages of using two-stage scenario based stochastic programming and a deterministic variant of the model are analyzed and discussed.

Roel van den Broek
Utrecht University

r.w.vandenbroek@uu.nl

Supervisors Hans Bodlaender, Han Hoogeveen, Marjan van den Akker

Title Train Shunting and Service Scheduling: an integrated local search approach
Abstract Trains have to be maintained and cleaned regularly to ensure high passenger safety and satisfaction. These service tasks must be performed outside the rush hours, when the trains are parked off the main railway network at dedicated service sites. The activities on a service site are currently scheduled by hand; a difficult and time-consuming task that consists of matching incoming and outgoing trains, scheduling the service tasks, assigning trains to parking tracks and routing the trains over the service site. We propose a local search approach for the automated construction of such shunt plans that integrates these four planning aspects. This heuristic is compared with a state-of-the-art MIP formulation in a case study for the Dutch Railways (NS).

Bohan Chen
CWI

B.Chen@cwi.nl

Supervisor Bert Zwart

Title Importance sampling of heavy-tailed iterated random functions
Abstract We consider the problem of constructing efficient rare-event simulation algorithm for estimating the tail of a stochastic perpetuity. Stochastic perpetuity can be found in the analysis of probabilistic algorithms and financial mathematics. It also arises naturally when we consider the steady-state distribution of a Markov chain constructed by iterated random affine functions. In this work, we provide a consistent simulation estimator using state-dependent importance sampling for the case, where the increments of the underlying random walk are heavy-tailed, and hence, the so-called Cramer condition is not satisfied. We show that under natural conditions, our estimator is strongly efficient. Furthermore, we extend our method to a more general case, where the underlying Markov chain is constructed by iterated random Lipschitz functions.

Joni Driessen

Eindhoven University of Technology

J.P.C.Driessen@tue.nl

Supervisor Joachim Arts, Geert-Jan van Houtum

Title Optimal Commonality and Reliability - An After-Sales Services Perspective
Abstract We consider a capital goods Original Equipment Manufacturer (OEM) who sells systems with complementary service contracts, and uses a platform strategy to reduce her costs. Her systems consist of components, belonging to a certain family. A component family is a collection of components that are very similar in their function, but not identical. For a repairable component family, the OEM has to determine: (1) whether to use a common component (one-for-all-systems) or dedicated components (one-for-each-system), (2) the reliability and (3) the turnaround stock levels for the components. The OEM's objective is to minimize the Life Cycle Costs (LCC).

We present two models: the common component model and the dedicated components model, and provide a detailed analysis of both. However, both models are not amenable for further analysis in their original form. Hence, we study two asymptotically equivalent models, as the spare part unavailability cost approaches infinity. In our subsequent analysis, we derive a threshold for the relative costs of a common component, such that commonality yields lower LCC than dedicated components. Secondly, we analyze this threshold to show when it attains its maximum value. Finally, we prove the existence of a threshold that determines monotonicity in the optimal reliability levels of the common and dedicated components, for two practical special cases.

Annette Ficker

KU Leuven

annette.ficker@kuleuven.be

Supervisor Frits Spieksma

Title Transportation Problem with two-sided Conflicts
Abstract The transportation problem is a fundamental problem in OR, where items need to be transported from supply nodes (each with a given supply) to demand nodes (each with a given demand) in the cheapest possible way. Here, we are interested in a generalization of the transportation problem where, each supply node has a (possibly empty) set of conflicting pairs of demand nodes, and each demand node a (possibly empty) set of conflicting pairs of supply nodes. Each supply node may only receive supply from at most one demand node of each conflicting pair. Likewise each demand node may only send supply to at most one supply node of each conflicting pair. We call the resulting problem the transportation problem with two-sided conflicts, and we are interested in the complexity and approximability of this problem.

Ruben van de Geer
University of Amsterdam

r.vande.geer@vu.nl

Supervisor Sandjai Bhulai

Title Numerical Methods for Approximate Optimal Pricing under Latent Class Logit Customer Choice
Abstract The problem of pricing a range of differentiated products is very common from a business perspective, but at the same time very challenging, since a price change in one product, not only changes the demand of that particular product, but is expected to also change the demand for the other products (so called, substitution). In an attempt to give substance to this problem, customer choice models have recently been adopted to describe choice behavior across differentiated products and optimize prices accordingly. These customer choice models, also known as discrete choice models, assume that customers assign utility to products based on the products' attributes and, subsequently, maximize their utility and purchase accordingly (or, possibly, choose not to purchase after all). The focus of our work is on maximizing the expected revenue with respect to prices in a multi-product setting when the customer's decision making process is modelled according to a particular customer choice model, namely the latent class logit model. The latent class logit model belongs to the class of mixed logit models, which generalize the multinomial logit model by assuming that the model coefficients are stochastic of nature.

Sander Gribling
CWI

S.J.Gribling@cwi.nl

Supervisor Monique Laurent, Ronald de Wolf

Title Matrix factorization and polynomial optimization

Abstract In this talk we discuss the topic of matrix factorizations. In particular, we study the cone of completely positive semidefinite matrices. This cone consists of all symmetric n-by-n matrices A for which there exists a factorization by positive semidefinite d-by-d matrices X_1,..., X_n (for some d >= 1), that is, A = (Tr(X_i X_j)). The parameter of interest is the completely positive semidefinite rank (cpsd-rank) of A defined as the smallest integer d for which these matrices exist. Note that if one restricts the positive semidefinite matrices to be diagonal then we recover the well-known cone of completely positive matrices consisting of the matrices A for which there exist real nonnegative vectors x_1,..., x_n in some dimension d>=1 such that A= (x_i^T x_j). The smallest d for which such vectors exist is the completely positive rank.

As a motivation for the study of the cpsd-rank we mention the following: if an upper bound on the cpsd-rank exists (in terms of n) then the cone of completely positive semidefinite matrices is closed which in turn implies that the set of quantum correlations is closed (the latter is an important open question in quantum information theory). It is a natural question to ask for the existence of an upper bound on the cpsd-rank. After all, it is known that the completely positive rank is at most quadratic, and in the asymmetric setting (where different factors for the rows and columns are allowed) it is easy to show that the minimum dimension of a factorization by nonnegative vectors or positive semidefinite matrices is at most n.

In recent work, for a particular class of completely positive semidefinite matrices, it has been shown that the factors need to be of a size exponential in the matrix size. We aim to find good lower bounds on the cpsd-rank of any completely positive semidefinite matrix.

In this talk we discuss a method that allows to obtain hierarchies of lower bounds on matrix factorization ranks. These hierarchies are based on the non-commutative analogue of the Lasserre hierarchy and the observation that the trace of the identity matrix of size d-by-d is equal to d. As an example, we show that our lower bound on the completely positive rank is tight for a class of matrices.

This is based on joint (ongoing) work with David de Laat and Monique Laurent.

Mariska Heemskerk

University of Amsterdam

mariskaheemskerk@uva.nl

Supervisor Johan van Leeuwaarden, Michel Mandjes

Title Queueing systems in a random environment: asymptotic analysis and MOL staffing
Abstract We extend the standard Poisson process in three ways in order for the resulting model to reflect the key features of a real-life arrival process. As a first step, we generalize to a nonhomogeneous process by introducing a time-varying arrival rate. Second, to induce overdispersion we multiply this deterministic trend by a (time-dependent) busyness factor, which is a stochastic process that takes on different values each fixed-size interval such that contributions to the rate from different time intervals are independent. Implementing dependence between rates of different time intervals completes the construction; the resulting nonhomogeneous stochastic arrival rate allows for contributions from the past to the current rate.

We are interested in the effect of such an arrival process on the performance of an infinite-server system. As it turns out, in a rapidly changing random environment the overdispersion of the arrival process hardly affects system behavior, whereas in a slowly changing random environment it is fundamentally different; this general finding applies to both the central limit and the large deviations regime. Having studied these effects, we do an attempt to apply MOL staffing for the corresponding

finite-server counterpart.

Irving van Heuven van Staereling

CWI

I.I.van.Heuven@cwi.nl

Supervisor Guido Schäfer

Title Length-bounded path covering algorithms for transportation problems
Abstract Optimizing timetables in transport is an extensively studied problem in combinatorial optimization due to its practical significance and theoretical elegance. However, little attention has been given to the variant where departure and arrival times of trips are given and fixed (rather than variable). Within this framework, the problem can simply be formulated as finding an optimal assignment of trips to vehicles and drivers subject to a wide range of possible constraints.

In this presentation will be formalized how this problem can be reduced to a path covering problem in a directed acyclic graph, and shown how it can be solved efficiently under the most basic constraints. However, the problem becomes strongly NP-hard if every path has a length bound (i.e., drivers have a maximum duty time), which will be shown by a reduction from 3-Partition. In practice though, the underlying directed acyclic graph includes an additional property, a specific variant of transitivity, making the problem considerably more structured. After introducing this notion, an algorithm will be given for the conditions under which the problem can be solved efficiently. The presentation will conclude by specifying the conditions for the problem remains open and other future work.

Rutger Kerkkamp

Erasmus University Rotterdam

kerkkamp@ese.eur.nl

Supervisor W. van den Heuvel , A.P.M. Wagelmans

Title Robust Pooling for Contracting Models with Asymmetric Information
Abstract In principal-agent contracting models, a principal wants to persuade an agent to perform a certain action. In order to do so, the principal offers a contract to the agent, describing the action to be taken with a suitable incentive for the agent. For example, the action is to buy a product from the principal and the incentive is a price discount. The contract design must balance the value of the contract for both parties, since the agent can refuse a disadvantageous contract.

The complexity of designing the contract increases significantly when the agent has private information on his valuation of contracts. In terms of mechanism design, the agent's so-called "type" is unknown to the principal. In this case, the principal offers a menu of contracts, where each contract is specifically designed for one of the possible agent's types. The agent then either chooses any contract of the menu or refuses the offer, depending on what is the most beneficial for the agent. Here, the agent can lie about his true type and choose any contract, which complicates the design of contracts.

The modelling of the agent's type is crucial for the menu of contracts. In the literature there are two typical choices: the agent's type lies in a finite discrete set (discrete distribution) or in a bounded interval (continuous distribution). In case of a discrete distribution, the menu consists of one contract for each possible type. Hence, the agent chooses from a finite number of contracts. In case of a continuous distribution, the menu is a function that maps every possible type to a contract. In other words, infinitely many contracts are offered.

We present a different approach which we call "robust pooling". The agent's type lies in a bounded interval, but only finitely many contracts are offered. First, the principal chooses how many contracts will be offered. Second, he partitions the interval of possible agent's types into that many subintervals. Third, he designs a single contract for each subinterval. This is the pooling aspect of our approach. Furthermore, the menu is designed such that it is robust against the uncertainty in the agent's type, i.e., the agent always accepts a contract from the menu.

Compared to the discrete approach, our model allows us to vary the number of contracts without changing the distribution of the agent's type. Moreover, if the discrete distribution is actually an approximation of a continuous distribution, the discrete approach is not robust. Compared to the continuous approach, our model handles both finitely and infinitely many contracts in a natural way. In practice, offering finitely many contracts is often easier to implement.

We apply our robust pooling model to value maximisation and cost minimisation problems with commonly used value/cost functions. First, we show that robust pooling models can be solved using similar techniques as for their discrete counterparts. Second, we focus on two specific models to derive performance guarantees of the optimal menu and insights into the optimal partition of the interval of the agent's types. We obtain both intuitive and counter-intuitive results.

Pieter Kleer
CWI
P.S.Kleer@cwi.nl

Supervisor Guido Schäfer

Title The impact of worst-case deviations in non-atomic network routing games
Abstract A non-atomic routing game is a multi-commodity (network) flow problem in which flow is controlled by selfish players, who are interested in minimizing their own latency through the network. This selfish behaviour give rise to the concept of a Nash (or Wardrop) flow, which is a flow configuration in which no player can switch to a different path in order to improve its latency. We study the impact of (worst-case) bounded perturbations on the latency functions of the arcs in the network. That is, we want to know how the average latency ("social cost") in the network changes as a result of players taking into account these perturbations (or deviations) in their path choice. These perturbations might, e.g., represent safety margins that players include as a result of uncertain latency functions on the arcs in the network.

The quality deterioration in social cost caused by such deviations is assessed by the Deviation Ratio, i.e., the worst-case ratio of the cost of a Nash flow with respect to deviated latencies and the cost of a Nash flow with respect to the unaltered latencies. This notion is inspired by the Price of Risk Aversion recently studied by Nikolova and Stier-Moses. Here we generalize their model and results. In particular, we derive tight bounds on the Deviation Ratio for multi-commodity instances with a common source and arbitrary non-negative and non-decreasing latency functions. These bounds exhibit a linear dependency on the size of the network (besides other parameters). In contrast, we show that for general multi-commodity networks an exponential dependency is inevitable.

We also study the Biased Price of Anarchy, which is the ratio between the social cost of a worst-case Nash flow with respect to deviated latencies and the social cost of an optimal flow (which minimizes the social cost over all feasible flows). In contrast to the Deviation ratio, the bounds on the Biased Price of Anarchy are given in terms of (properties of) the latency functions on the arcs in the network.

Joint work with Guido Schaefer.

Corine Laan
University of Twente, TNO
c.m.laan@utwente.nl

Supervisor Ana Barros, Richard Boucherie, Herman Monsuur

Title A partially observable agent-intruder game
Abstract We consider a game on a graph between an agent and an intruder. At each step of the game both players can move to an adjacent node. The intruder's goal is to reach a target node, while the agent aims at intercepting the intruder before he reaches a target node. In this game, the players do not know the position of the other player. However, both players do get some information about the other's position. For example, an underlying sensor network provides the agent with information on the intruder's position. If the intruder is at a sensor node, he is detected with a given probability.

In this presentation, we introduce a partially observable agent-intruder game (POAIG) to find optimal strategies for the agent and the intruder. This model can be used to explore the value of information, and can be used to decide the sensor's placement to obtain a certain detection level.

Tommaso Nesti
CWI
T.Nesti@cwi.nl

Supervisor Bert Zwart

Title Reliability of energy networks under uncertainty
Abstract The advent of renewable energy, like wind and solar power, has huge implications for the design and control of power grids. In order to avoid line tripping and potential blackouts, one has to impose constraint on the amount of power that can flow in a transmission line. Due to increasing supply-side uncertainty, however, traditional reliability constraints have to be replaced by probabilistic guarantees. In this talk we present analytic techniques, which are based on large deviations theory, to study the probability of line overloads in a power grid with stochastic power injections and develop corresponding safe capacity regions. In particular, we characterize the set of admissible power injections such that the probability of overloading of any line over a given time interval stays below a fixed small target (think of 10^-6), assuming a small-noise regime. We show how enforcing stochastic constraints on temperature, rather than on current, results in a less conservative approach and can thus lead to capacity gains in power grids. We conclude by presenting an extension of this work which yields non-asymptotic bounds for the overlaod probabilities.

Tim Oosterwijk
Maastricht University
t.oosterwijk@maastrichtuniversity.nl

Supervisor Tjark Vredeveld

Title Posted Price Mechanisms for a Random Stream of Customers
Abstract Posted price mechanisms constitute a widely used way of selling items to strategic consumers. Although suboptimal, the attractiveness of these mechanisms comes from their simplicity and easy implementation. In this paper, we investigate the performance of posted price mechanisms when customers arrive in an unknown random order. We compare the expected revenue of these mechanisms to the expected revenue of the optimal auction in two different settings. Namely, the nonadaptive setting in which all offers are sent to the customers beforehand, and the adaptive setting in which an offer is made when a consumer arrives. For the nonadaptive case, we obtain a strategy achieving an expected revenue within at least a 1-1/e fraction of that of the optimal auction. We also show that this bound is tight, even if the customers have i.i.d. valuations for the item. For the adaptive case, we exhibit a posted price mechanism that achieves a factor 0.745 of the optimal revenue, when the customers have i.i.d. valuations for the item. Along the way, we prove a basic result about Bernoulli random variables that we believe can be of independent interest.

Dennis Prak
University of Groningen
d.r.j.prak@rug.nl

Supervisor Ruud Teunter

Title A general method for addressing estimation uncertainty in inventory models
Abstract The current inventory control literature exhibits a separation of forecasting and decision making. As a result, parameter estimates of the demand distribution are typically directly substituted for the unknown true parameters, which leads to suboptimal decisions. We derive a universally applicable method for properly addressing the estimation uncertainty. First, the parameters are efficiently estimated and their errors are modelled. Then, the point estimates and their error terms are substituted into the objective function, after which the expectation of this function is taken with respect to the estimation errors. We illustrate this method for a model with shortage and holding costs and normally distributed demand. When estimates are based on 10 observations, relative savings are typically between 10% and 30%. They are larger when parameter estimates are based on fewer observations, when backorders are costlier, and when the lead time is larger. Next to the exact approach to modelling the error distribution, we also discuss a robust, approximate method based on the asymptotic distribution of maximum likelihood estimators. This alternative method can be applied to any demand distribution, whereas the exact error distribution is not always available. We show that if there are very few (less than 10) demand observations available, then it is beneficial to derive the exact error distribution (if possible), whereas for 10 or more demand observations the approximate method yields results that are close to that of the exact approach.

Sajjad Rahimi-Ghahroodi
University of Twente
s.rahimighahroodi@utwente.nl

Supervisor Ahmad Al Hanbali, Henk Zijm, Jan-Kees van Ommeren

Title Integrated Planning of Spare Parts and Service Engineers; a Queueing Model Approach
Abstract We study a situation where systems installed in a service region are subject to random failures. Each failure (repair call) needs both a service engineer and a spare part to be available before it can be resolved. An inventory is located in the region to supply different types of spare parts. The objective is to determine close-to-optimal stock levels as well as the number of service engineers that minimize the total average costs under a maximum total average waiting time constraint. We model the system as a queueing network. An exact method and an approximation for the evaluation of a given policy are presented. For the exact method, we model the problem as a quasi-birth-death process and solve it numerically using a standard matrix-geometric method. This method does not scale computationally with the size of the problem. Hence, we develop a fast evaluation method where we decouple the spare parts inventory and service engineers queue in a smart way. We exploit evaluation methods in a greedy heuristic procedure to optimize this integrated planning. Then, we compare this method with separated optimization to investigate the impact of separating the capacity decisions of these two resources. In summary, using approximate evaluation is necessary for this problem as the exact method fails for problems with a large number of spare parts type. Furthermore, by using integrated planning of spare parts and service engineers, we obtain a result with the same service level (total average waiting time) but usually with much lower resources investment in comparison with separated planning.

Joost van Sambeeck
University of Twente
j.h.j.vansambeeck@utwente.nl

Supervisor Mart Janssen, Wim de Kort, Nico van Dijk

Title Deriving an optimal strategy for donor blood group typing
Abstract Due to an increasing awareness of adverse events that red blood cell (RBC) transfusions may induce, hospitals use more restrictive transfusion policies. This means that both the number of RBC transfusions has diminished, and whenever a transfusion is required more extensive matching strategies are applied. To satisfy the demand for extensively typed RBCs, targets are set for the proportion of donors that should have a known negative type for particular antigens. Since typing can be a costly procedure, the number of typings should be minimized.

A mathematical model was developed that allows derivation of the number of typings required to fulfill the demand for (extensively) typed products. This model was extended to calculate costs of typing for various typing strategies, which allows cost minimization. This optimization problem is solved using a simulated annealing method.

The results indicate that the current typing procedure can be improved. Also, comparing the proportion of typed donors for several matching strategies confirms that the matching strategy has a substantial influence on the proportion of typed donors required.

Mathematical modelling allows optimizing the donor typing scheme. This optimum depends on the number of patients matched according to the selected strategy.

Loe Schlicher
Eindhoven University of Technology

l.p.j.schlicher@tue.nl

Supervisor Marco Slikker, Geert-Jan van Houtum

Title Maximal Covering Location Games
Abstract In the maximal covering location problem a single decision maker has to position a predetermined number of resources in order to maximize profit of the covered demand points, where a demand point is covered if a resource is positioned within a certain radius. This well-known location model has proven to be useful in many settings, e.g., for positioning of emergency vehicles, cell towers and retail stores. Another interesting setting is the one with several small-sized regions, e.g., villages or municipalities, that each may or may not own a single resource to cover their region completely. When those regions pool their resources a maximal covering location problem arises. Typically, additional coverage, and so additional profit, can be realized and a joint profit allocation issue arises amongst the collaborating regions. In this talk, we will investigate this allocation aspect by introducing a maximal covering location (MCL) situation wherein regions are represented by single demand points that may or may not keep a single resource. For such an MCL situation, an associated MCL game is formulated. For this game, we provide several sufficient conditions (in terms of the number of players, the number of resources, and the underlying integer linear program) for core non-emptiness.

Fiona Sloothaak

Eindhoven University of Technology

f.sloothaak@tue.nl

Supervisor Sem Borst, Bert Zwart

Title Power-law behavior in cascading failure models
Abstract As electric transmission networks continue to increase in complexity and volatility, there is a growing potential for cascading failure effects to cause major blackouts. Understanding these effects and assessing the risks involved is of critical importance in operating the electric grid and maintaining high reliability. Analysis of empirical data suggests that the blackout sizes obey a power-law distribution with exponents that vary over data sets. In this talk, we consider a stylized cascading failure model that captures the additional loading of the remaining lines when a line failure occurs. This may potentially cause more lines to fail as well. A single initial line failure can therefore trigger massive knock-on effects, resulting in a severe blackout. We consider which load functions yield power-law behavior for the blackout size, and address the impact of network splitting.

Marijn ten Thij

VU University of Amsterdam

m.c.ten.thij@vu.nl

Supervisor Sandjai Bhulai

Title Modelling trend progression in online networks
Abstract We model user behaviour in Twitter to capture the emergence of trending topics. For this purpose, we first extensively analyse tweet datasets of several different events. In particular, for these datasets, we construct and investigate the retweet graphs. We find that the retweet graph for a trending topic has a relatively dense largest connected component (LCC). Next, based on the insights obtained from the analyses of the datasets, we design a mathematical model that describes the evolution of a retweet graph by three main parameters. We then quantify, analytically and by simulation, the influence of the model parameters on the basic characteristics of the retweet graph, such as the density of edges and the size and density of the LCC. Finally, we put the model in practice, estimate its parameters and compare the resulting behavior of the model to our datasets.

Veerle Timmermans
Maastricht University

v.timmermans@maastrichtuniversity.nl

Supervisor Tobias Harks

Title Equilibrium Computation in Atomic Splittable Singleton Congestion Games
Abstract We devise the first polynomial time algorithm computing a pure Nash equilibrium for atomic splittable congestion games with singleton strategies and player-specific affine cost functions. Our algorithm is purely combinatorial and computes the exact equilibrium assuming rational input. The idea is to reduce equilibrium computation to the problem of computing an equilibrium for an associated integrally-splittable singleton congestion game in which the players can only split their demands in integral multiples of a common packet size. While these integral games have been considered in the literature before, no polynomial time algorithm computing an equilibrium was known. Also for this class, we devise the first polynomial time algorithm and use it as a building block for our main algorithm.

Denise Tönissen
Eindhoven University of Technology

D.D.Tonissen@tue.nl

Supervisor Geert-Jan van Houtum, Joachim Arts

Title Robust Maintenance Location Routing for Rolling Stock
Abstract Rolling stock needs regular maintenance in a maintenance facility. Rolling stock from different fleets needs to be routed to maintenance facilities using interchanges between train lines and possible empty drives. We consider the problem of locating maintenance facilities in a railway network under uncertain or changing line planning, fleet planning and other factors. These uncertainties and changes are modeled by a discrete set of scenarios. We show that this new problem is NP-hard and provide a two-stage robust programming formulation. The second stage decision is a maintenance routing problem with similarity to a minimum cost-flow problem. We prove that the facility location decisions remain unchanged under a simplified routing problem and this gives rise to an efficient mixed integer programming formulation. We also provide an efficient decomposition algorithm based on row-and-column generation that improves the computational time and can handle larger instances due to more efficient memory usage. Finally, we apply our algorithms to a case study at Nedtrain.

Thomas R. Visser

Erasmus University Rotterdam

t.r.visser@ese.eur.nl

Supervisors Remy Spliet, Niels Agatz, Albert Wagelmans

Title A Rich Vehicle Routing Framework for Dynamic Time Slot Management in attended home delivery

Abstract The focus of this presentation is the problem of managing the availability of time slots for attended home delivery in real-time during the customer ordering process, called the Dynamic Time Slot Management (DTSM) problem. Many online retailers providing attended home delivery offer customers to choose from a set of narrow delivery time-windows, called time slots. Since the customers' choice affects the efficiency of the delivery routes, it is crucial to manage how much demand is accepted for each time slot. DTSM exploits dynamic routing to, in real-time, evaluate and update available time slot capacity based on already placed customer orders and available vehicles. In our DTSM problem, we include rich vehicle routing characteristics as heterogeneous fleet, multiple satellite hubs and time dependent travel times. Further, we introduce the by practice inspired concept of time slot reservations. The customer can reserve a time slot for a limited time before they build and finalize their order. This poses additional challenges, since at reservation it is unknown if the order will materialize and its order size. We propose a rich vehicle routing framework and test its performance on real-world data from our industry partner. Our study is part of a large research project in which we collaborate with software developer ORTEC and the largest online grocery retailer of the Netherlands, Albert Heijn Online.

Tom van der Zanden

Utrecht University

T.C.vanderZanden@uu.nl

Supervisor Hans Bodlaender

Title Subgraph Isomorphism in Planar Graphs in Subexponential Time
Abstract In this talk, we give a subexponential time algorithm for the Subgraph Isomorphism problem on planar graphs, which is to decide whether a given planar graph G contains another (planar) graph P as a subgraph. The algorithm has running time 2^O(n/log n), where n=|V(G)|. We also show that this is optimal, in the sense that an algorithm running in time 2^o(n/log n) would imply a 2^o(n)-time algorithm for 3-SAT and thus falsify the Exponential Time Hypothesis (ETH).

Many NP-hard problems remain NP-hard when restricted to planar graphs. However, in planar graphs they can usually be solved significantly faster than in general graphs. For instance, assuming the ETH, Vertex Cover can not be solved in 2^o(n) time on general graphs, but admits a 2^O(sqrt(n))-time algorithm on planar graphs and this is (again assuming the ETH) tight. In fact, this behaviour of a square root appearing in the exponent of the optimal running time occurs in many NP-hard problems on planar graphs and has been dubbed the "Square Root Phenomenon". Our result provides a surprising exception to this rule.

The algorithm is based on dynamic programming. The key technique is that we can reduce the number of options that need to be considered by exploiting isomorphism between candidate solutions. For the lower bound, we use the technique of identifying each variable and clause in a 3-SAT formula with a number, which can be represented as a string of O(log n) bits, and these bitstrings are encoded in connected components of the graphs created in the reduction.

The running time of 2^O(n/log n) appears to be the "right" running time for several other graph embedding problems (when restricted to planar graphs), such as induced subgraph, intervalizing coloured graphs and graph minor.

This talk is based on the paper "Subexponential Time Algorithms for Embedding H-Minor Free Graphs" (ICALP 2016) which is joint work with Hans Bodlaender and Jesper Nederlof.