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
lowpriority 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
queueingtheoretic 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 pseudoconservation 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 twoLayered Network
Abstract Motivated
by a webserver model, we present a queueing network consisting of two
layers. The first layer incorporates the arrival of customers at a network of
two singleserver nodes. We assume that the interarrival 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
reenter 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 ProcessorSharing fashion. Also, we assume that the
degree of resource sharing is limited by choice. This is a Limited
ProcessorSharing 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 statespace 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
nonnegative 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 Ecoefficient
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. Multiobjective
optimization models have been proposed to quantify tradeoffs between
conflicting objectives and to derive ecoefficient 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
MultiObjective 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 twostage 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
timeconsuming 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 stateoftheart 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 heavytailed iterated random functions
Abstract We consider the problem of
constructing efficient rareevent 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 steadystate distribution of a Markov
chain constructed by iterated random affine functions. In this work, we
provide a consistent simulation estimator using statedependent importance
sampling for the case, where the increments of the underlying random walk are
heavytailed, and hence, the socalled 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, GeertJan van Houtum
Title Optimal
Commonality and Reliability  An AfterSales 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 (oneforallsystems) or dedicated components
(oneforeachsystem), (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 twosided 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 twosided 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
multiproduct 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 nbyn matrices A for which there exists a factorization by
positive semidefinite dbyd 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 (cpsdrank)
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 wellknown 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 cpsdrank we
mention the following: if an upper bound on the cpsdrank
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 cpsdrank. 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 cpsdrank
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
noncommutative analogue of the Lasserre hierarchy
and the observation that the trace of the identity matrix of size dbyd 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 reallife arrival
process. As a first step, we generalize to a nonhomogeneous process by
introducing a timevarying arrival rate. Second, to induce overdispersion we multiply this deterministic trend by a
(timedependent) busyness factor, which is a stochastic process that takes on
different values each fixedsize 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 infiniteserver 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
finiteserver
counterpart.
Irving van Heuven van Staereling
CWI
I.I.van.Heuven@cwi.nl
Supervisor Guido Schäfer
Title Lengthbounded
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 NPhard if every path has a length bound (i.e., drivers have a
maximum duty time), which will be shown by a reduction from 3Partition. 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 principalagent 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 socalled "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 counterintuitive results.
Pieter Kleer
CWI
P.S.Kleer@cwi.nl
Supervisor Guido Schäfer
Title The impact of worstcase
deviations in nonatomic network routing games
Abstract A nonatomic routing game is a multicommodity (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
(worstcase) 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 worstcase 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 StierMoses. Here we generalize their model and results.
In particular, we derive tight bounds on the Deviation Ratio for
multicommodity instances with a common source and arbitrary nonnegative and
nondecreasing latency functions. These bounds exhibit a linear dependency on
the size of the network (besides other parameters). In contrast, we show that
for general multicommodity networks an exponential dependency is inevitable.
We also study the Biased Price of Anarchy, which is the ratio between the
social cost of a worstcase 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 agentintruder 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 agentintruder 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
supplyside 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 smallnoise 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
nonasymptotic 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 11/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 RahimiGhahroodi
University of Twente
s.rahimighahroodi@utwente.nl
Supervisor Ahmad Al Hanbali,
Henk Zijm, JanKees 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
closetooptimal 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 quasibirthdeath process and solve
it numerically using a standard matrixgeometric 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, GeertJan 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 wellknown
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 smallsized 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 nonemptiness.
Fiona Sloothaak
Eindhoven University of Technology
f.sloothaak@tue.nl
Supervisor Sem Borst, Bert Zwart
Title Powerlaw
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 powerlaw 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 knockon effects,
resulting in a severe blackout. We consider which load functions yield
powerlaw 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 playerspecific 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
integrallysplittable 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 GeertJan 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
NPhard and provide a twostage robust programming formulation. The second
stage decision is a maintenance routing problem with similarity to a minimum
costflow 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 rowandcolumn 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 realtime 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 timewindows, 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 realtime, 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 realworld 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 3SAT and thus
falsify the Exponential Time Hypothesis (ETH).
Many NPhard problems remain NPhard 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 NPhard 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 3SAT 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 HMinor Free Graphs" (ICALP 2016) which is
joint work with Hans Bodlaender and Jesper Nederlof.
