Abstracts presentations phd students

ANGÜN, EBRU
BIK
Tilburg University
P.O. Box 90153
5000 LE Tilburg
m.e.angun@uvt.nl

Supervisors
Kleijnen, Den Hertog and Gürkan

Title
Black box simulation-based optimization for multiple responses
 

Abstract
This research considers simulation-based optimization problems with a stochastic objective function and stochastic constraints. It generalizes classic Response Surface Methodology (RSM), as it accounts for multiple responses. Like RSM, it treats the simulation model as a black box. Moreover, this research assumes that simulation requires much computer time. Whereas classic RSM uses the estimated steepest descent (ESD) that is only suitable for a single response, this research generalizes the ESD through ideas from interior point methods, especially affine scaling. The new search direction is scale independent. Furthermore, this research provides a heuristic for iterative use of this search direction. This heuristic proceeds towards the solution point through the interior of the feasible region, and it aims at reaching a neighborhood of the solution point in a few simulation runs. The heuristic stops when the Karush-Kuhn-Tucker optimality conditions are satisfied statistically.
 

BEKKER, RENÉ
Department of Mathematics and Computer Science
Eindhoven University of Technology
P.O. Box 513
5600 MB Eindhoven
rbekker@win.tue.nl

Supervisor
Boxma

Title
Queues with workload-dependent service and arrival rates

Abstract
State-dependent release or service rates are often encountered in dam-type models. Furthermore, in production systems, workload management may be realized by controlling the arrival rate of new jobs. Motivated by similar workload control mechanisms in communication networks, we consider the single-server M/G/1 queue, with workload-dependent arrival rate and/or speed of the server. We compare the steady-state distribution of the workload (both at arbitrary epochs and just before arrival epochs) in two models, in which the ratio of arrival rate and service speed are equal. Level crossings and the Volterra approach play a key role in determining the steady-state distributions. Finally, we allow the interarrival time to be generally distributed and determine the dynamics driving the workload process.
 

BLANC, IEKE LE
CentER, Applied Research
Tilburg University
P.O. Box 90153
5000 LE Tilburg
h.m.leblanc@uvt.nl

Supervisors
Fleuren, Krikke

Title
Redesign of a recycling system for LPG-tanks

Abstract
The presentation is based on a study performed for Auto Recycling Nederland on the redesign of a recycling system for LPG-tanks. The study resulted in a publication in the handbook of reverse logistics (in Dutch) and an extended English version is submitted to OR-Spektrum.
The old system for the recycling of LPG-tanks didn’t function properly; it was a pure efficiency-focused chain, which in practice resulted in high safety risks. In the new system the focus lies more on responsiveness so that safety can be guaranteed. In the study the network design of the new system is optimized. Uncertainty in systems behavior and the difficulty in gathering reliable data are common in reverse logistics network design questions. In this real-life situation the total costs consist for almost 50% of transportation costs, therefore reliable estimations of the transportation costs are crucial. A vehicle routing model is used to solve this data problem and feed the estimations to a mathematical programming model. The mathematical program is a variant of a  location-allocation model and is applied for the actual redesign of the network. System uncertainty is taken into account by performing extensive sensitivity analysis.
 

DIEKER, TON
CWI
P.O. Box 94079
1090 GB Amsterdam
ton.dieker@cwi.nl

Supervisor
Mandjes

Title
On asymptotically efficient simulation of large deviations probabilities

Abstract
Probabilities that decay according to a large deviations principle are encountered in a variety of applications. Direct Monte Carlo simulation,  however, is often practically infeasible, particularly if the probabilities of  interest are extremely small. Importance sampling is a technique in which samples are drawn from an alternative distribution, and an unbiased estimate is found after a likelihood ratio correction. An exponentially twisted distribution was shown to be a good sampling distribution under fairly general circumstances.
In my talk, I present necessary and sufficient conditions for asymptotical efficiency of a single exponentially twisted distribution. This makes it possible to rederive and sharpen many results obtained for specific problems. Moreover, from a theoretical point of view, the conditions are better than the most general previously known conditions.
 

DOGRU, MUSTAFA KEMAL
Faculty of Technology Management
Eindhoven University of Technology
P.O. Box 513
5600 MB Eindhoven
m.k.dogru@tm.tue.nl

Supervisors
de Kok and van Houtum

Title
Linear programming based planning concept for a serial, two-echelon inventory system

Abstract
Mathematical Programming based planning approaches for multi-stage inventory/production systems are widely used in practice due to the fact that many restrictions in the planning environment can be represented as constraints. However, an important disadvantage of MP based approaches is that they are deterministic and lacks the uncertanities in the planning environments. In this study, we develop an LP formulation for the inventory control of a serial, two-echelon inventory system which incorporates stochastic demand information. It is shown that when appropriate safety stocks are assigned to each stock point, the LP developed can duplicate the ordering behavior of base stock policy, which is known to be optimal.
 

GOOSSENS, JAN-WILLEM
Department of Quantitative Economics
Maastricht University
P.O. Box 616
6200 MD Maastricht
j.goossens@ke.unimaas.nl

Supervisor
Kolen

Title
On solving multi-type railway line planning problems

Abstract
An important strategic element in the planning process of a railway operator is the development of a line plan, i.e.  a set of routes (paths) on the network of tracks, operated at a given hourly frequency. The models described in the literature have thus far considered only lines that halt at all stations along their route. In this paper we introduce  several (mixed) integer programming models for solving line planning problems in which lines can have different halting patterns. Correctness and equivalence proofs for these models are given, as well as an evaluation using several real-life instances.

This paper is joint work with Stan van Hoesel (Universiteit Maastricht) and Leo Kroon (Erasmus University Rotterdam / Nederlandse Spoorwegen). This research is partly sponsored by the Human Potential Program of the European Union under contract no. HPRN-CT-1999-00104 (AMORE).
 

GRIGORIEVA, ELENA
Department of Quantitative Economics
Maastricht University
P.O. Box 616
6200 MD Maastricht
e.grigorieva@ke.unimaas.nl

Supervisors
Herings and Muller

Title
The private value single item bisection auction.

Abstract
In this paper we present a new iterative auction, the bisection auction, which can be used for the sale of a single indivisible object. The underlying principle of this auction is based on the bisection method, a well-known fast algorithm that can be used e.g. for the determination of realizations of random variables on a given interval. The auction starts with a lower and upper bounds on the bidders valuations that determine the initial interval. The price sequence starts at the middle of the initial interval. Bidders report their demand at a current ask price by sealed bids. As a function of these bids, the auctioneer announces the price of the next round. If more than one bidder announces demand, the price increases to the middle of the upper half interval. If at most one bidder announces demand at the current price, the price decreases to the middle of the lower half interval.

Modelling the bisection auction as an extensive form game with incomplete information we analyzed its equilibrium properties. First, we have shown that in the bisection auction, threshold strategies are sufficient from a strategic point of view. Furthermore, we have shown that this auction is incentive compatible, that is truth-telling (choosing your threshold equal to your valuation) is a weakly dominant strategy and the equilibrium that results when everyone tells the truth is efficient in the sense that the player with the highest valuation gets the object.

So, we have proved that under private value setting our bisection auction is strategically equivalent to the classical English and Vickrey auctions. However, the proposed auction is preferred over the Vickrey auction because of its iterative nature and over the English auction because of its speed. In the bisection auction the query of announced prices converges to the smallest Walrasian price in logarithmic time. This guarantees a fast and predictable termination of the auction, while the running time of the English auction is of exponential size relative to the length of the binary representation of the valuations of the buyers. Furthermore, participation in the bisection auction is less demanding than in the Vickrey and the English auctions. In the bisection auction less information needs to be revealed to the auctioneer to decide on an allocation and a payment.
 

KRAAIJ, ANTON VAN DER
Department of Quantitative Economics
Maastricht University
P.O. Box 616
6200 MD Maastricht
a.vanderkraaij@ke.unimaas.nl

Supervisor
Van Hoesel and Kolen

Title
Tariff optimization in telecommunication networks

Abstract
We consider the problem of determining a set of optimal tariffs for an operator, who owns a subset of the arcs of a telecommunications network, and who wishes to maximize his revenues. In the network multiple rational clients are active, who route their demands on the cheapest paths from source to destination. The cost of a path is determined by fixed costs and tariffs on the arcs of the path.
With regard to the complexity of the problem, we show NP-hardness of the set tarification version, and we identify a polynomially solvable special case: the equal tariffs problem. The main concept of our approach is a remodelling of the network, using shortest paths. Combined with model specific graph reduction methods this model enables us to solve the problem to optimality, for fairly large instances. We develop two algorithms based on this shortest path graph model, namely a combinatorial branch and bound algorithm and a path oriented mixed integer program. We provide computational results for both methods and compare them with the results on the arc oriented mixed integer programming formulation of the problem.

This paper is joint work with Mustapha Bouhtou (France Telecom), Stan van Hoesel (Universiteit Maastricht) and Jean-Luc Lutton (France Telecom).
 

Supervisors
Fleuren, Peeters

Title
Solving set partitioning problems

Abstract
Many real-life problems can be written as set partitioning problems. Applications can be found for example in airline scheduling and facility location problems. Unfortunately, the set partitioning problem is an NP-hard problem. However, much attention has been given in the literature on algorithms that solve the set partitioning problem to optimality.
Our research focusses on a hybrid approach of solving set partitioning problems. To this end a solver is being developed that uses several techniques, like preprocessing, lagrangean relaxation, dual heuristics and, finally, branch and bound. In this presentation some of the modules of the solver will be highlighted and the results that have been gathered so far will be presented and compared to the results of the well-known mathematical optimization solver CPlex. Moreover, brief attention will be given to possible extensions and enhancements of the solver that will be examined in the future course of this research project.
 

LUTGENS, FRANK
Department of Quantitative Economics
Maastricht University
P.O. Box 616
6200 MD Maastricht
f.lutgens@ke.unimaas.nl

Supervisor
Kolen, Schotman

Title
Robust portfolio optimization

Abstract
In her quest for a model that describes the stochastic process of some state variables, an economic agent realizes that the many competing model specifications combined with the limited amount of available data, make it hard to be certain about the correctness of the model and its estimates.
Indeed she acknowledges that other models and parameters also have a considerable degree of plausibility. If the agent has to base decisions on these state variables, e.g. by solving an optimization model with state variables as coefficients, she is confronted with uncertainty in the optimization model coefficients. The robust paradigm is to use the worst case coefficients within the set of coefficients that have sufficient degree of plausibility.
We present a study of the robust approach to portfolio optimization. We use econometric methods to quantify uncertainty and use these to derive plausible optimization coefficients. Subsequently we formulate the robust optimization problem and demonstrate how such problems can be solved.
 

OLIEMAN, NIELS
Operations Research and Logistics
Wageningen University
Hollandseweg 1
6706 KN Wageningen
niels.olieman@wur.nl

Supervisor
Ridder

Title
Stability of coalitions in a Nash-Cartel game: a probability analysis

Abstract
In this paper, a methodology is presented for specifying the robustness of model conclusions in relation to uncertain model parameters. This methodology is applied to a mathematical model of world regions forming a coalition, for cooperatively reducing CO2  emissions. This model first determines the world regions' payoffs for each possible coalition structure. Then the model verifies coalition stability by selecting the Nash-equilibrium coalition structures from the set of all possible coalition structures.

The applied methodology considers all uncertain model parameters as stochastic variables. As a consequence, the stability of a specific coalition structure can be interpreted as a bernoulli variable. For estimating this stability probability, monte carlo simulation can be applied independent of the probability distribution type of the the stochastic model parameters. An efficient algorithm is discussed for the specific case when model parameters have a symmetric probability distribution, such as the multivariate normal- and multivariate t probability distribution.
 

PAK, KEVIN
Econometric Institute
Erasmus University Rotterdam
P.O. Box 1738
3000 DR Rotterdam
kpak@few.eur.nl

Supervisor
Dekker

Title
Airline revenue management with convertible seats

Abstract
Revenue management is a practice that has been applied in the airline industry for many years. It is aimed at generating as much revenue as possible from a flight by finding the right passenger mix on the plane. Airlines typically offer many different fare classes on a flight. Because the time to sell the tickets is finite and capacity is fixed, a low fare booking request can be either accepted in order to fill the plane, or rejected in favor of a possibly more profitable future booking request. In this research we extend the original revenue management problem by introducing convertible seats on the planes. By a simple procedure, a row of these seats can be converted from business class seats to economy class seats and vice versa. This means that a plane will be better able to generate revenues by adjusting its capacity configuration to the demand pattern at hand. We present a booking control policy that takes into account the shifting capacity opportunity and show that it can indeed improve revenues.
 

SITTERS, RENÉ
Department of Mathematics and Computer Science
Eindhoven University of Technology
P.O. Box 513
5600 MB Eindhoven
r.a.sitters@win.tue.nl

Supervisor
Stougie

Title
A 2833307565-competitive algorithm for the general CNN-problem.

Abstract
The CNN-problem takes its name from the following example. A team of the CNN news channel drives through the streets of Manhattan to shoot any interesting scene. The camera is so strong that the team can make a good shot as long as they are on the same street or avenue as the scene. If a scene happens to be at an intersection, then the team has two options: move to the street or to the avenue. Of course the team must make this choice without knowing where future events take place. The goal is to minimize the total travelled distance.

This online optimization problem is an interesting variant of the well-known k-server problem and is the simplest version of a very general class of online server problems. It is regarded as one of the most intriguing problems in online optimization. The definition is very simple but until now no algorithms at all are known. We present the first constant competitive algorithm for the problem. Although the constant is huge we believe that our result is an initial step towards good algorithms for the problem.
 

SPITTER, JUDITH
Faculty of Technology Management
Eindhoven University of Technology
P.O. Box 513
5600 MB Eindhoven
j.m.spitter@tm.tue.nl

Supervisor
de Kok

Title
Setting planned lead time in multi-item multi-echelon systems

Abstract
Today, production planning in a manufacturing environment is usually carried out according to Material Requirement Planning (MRP) logic. However, MRP logic does not take capacity constraints into account. As MRP planning systems does not provide a solution to this fundamental issue, planners have to adjust the planning manually. As an alternative to the MRP logic, we propose linear programming approaches to integral planning, which are able to cope with capacity constraints and material availability constraints. We still use the MRP logic, that is, we derive dependent demand for components from the production schedules of their parents and offset replenishment with their planned lead time. Others have also developed linear programming models for general production structures. Compared to their models, our approach differs essentially with respect to the interpretation of lead times. We use fixed lead times for every item, and require that any reasonable order should be finished within that time, instead of having lead times as the output of the optimization procedure.

So, we have fixed the lead time for every item, and an order should be finished within that time. Only at the end of the lead time the complete order becomes available for further use. Since the actual production time is shorter than the lead time, you can shift with the start of production. We have compared the situation of producing immediately after a request is made and the situation in which we start the production as late as possible.  To be able to shift, the lead time must be longer than one period. Longer lead times result in more work-in-process inventory costs, but can also result in lower safety stocks. Hence, we have also investigated the influence on the cost of having longer lead times.
 

UITERT, MIRANDA VAN
CWI
P.O. Box 94079
1090 GB Amsterdam
m.j.g.van.uitert@cwi.nl

Supervisor
Borst

Title
Sample-path large deviations for tandem (and priority) queues with Gaussian inputs

Abstract
This talk considers Gaussian flows multiplexed in a queueing network. A single node being a useful but often incomplete setting, we examine more advanced models. We focus on a (two-node) tandem queue, fed by a large number of Gaussian inputs. With service rates and buffer sizes at both nodes scaled appropriately, Schilder's sample-path large deviations theorem can be applied to calculate the asymptotics of the overflow probability of the second queue. More specifically, we derive a lower bound on the exponential decay rate of this overflow probability and present an explicit condition for the lower bound to match the exact decay rate. Examples show that this condition holds for a broad range of frequently-used Gaussian inputs. We show that the analysis of the tandem queue directly carries over to a priority queueing system.