Abstracts presentations phd students
ASADI, ALIREZA
Faculty EWI
Delft University of Technology
Mekelweg 4
2628 CD DElft
a.asadi@tudelft.nl
Supervisor
Kees Roos
A large-update infeasible interior-point algorithm for linear optimization based on logarithmic barrier function
Abstract
Recently, a full-Newton step O(n) infeasible interior-point method has been presented during which the iterates are forced to be in a small neighborhood of the central path of so-called perturbed problems. In this paper, we introduce a large-update version of the algorithm. The aim is to design a variant that allows a large amount of reduction on the infeasibility and the duality gap at each iteration. Unfortunately, it is on the same boat with its feasible counterpart in the sense that regardless of its higher practical performance, its theoretical convergence rate is worse, namely O(n^2) whilst its full-Newton step counterpart is O(n).
| Back to home page | Program | Parallel sessions |
BIJVANK, MARCO
Vrije Universiteit Amsterdam
De Boelelaan 1081a
1081 HV Amsterdam
mbijvank@few.vu.nl
Supervisor
Ger Koole
Inventory systems with periodic reviews and lost sales
Abstract
Different replenishment policies are considered for a periodic review inventory system with lost sales. A new policy is introduced in which the maximum order size is restricted. The performances of each policy are compared to the optimal policy for a cost and service objective. We also propose an approximation procedure to determine the reorder and order-up-to levels.
| Back to home page | Program | Parallel sessions |
BOMHOFF, MATTHIJS
Faculty of EWI
University of Twente
P.O. Box 217
7500 AE Enschede
m.j.bomhoff@ewi.utwente.nl
Supervisor
Georg Still
Network structure optimization: A case study on baggage handling systems
Abstract
We investigate the automatic generation of airport baggage handling networks conforming to predefined performance requirements. The design of airport baggage handling systems is usually performed by hand by experienced designers. Unfortunately, this is a time-consuming process that relies heavily on (possibly tacit) knowledge of human designers. As part of the Smart Synthesis Tools project, we investigate possibilities for the automation of this process.
Our approach consists of an algorithm that `grows' a suitable solution by iteratively applying graph transformations on parts of the network that are diagnosed as bottlenecks with respect to the requirements. We first address the concept of constructing a (logistical) network using graph transformations. After this, a brief explanation on how techniques from operations research are used to determine the bottlenecks for both total capacity (a network flow problem) and expected queueing time (a queueing theory problem) follows. Finally, as this is still ongoing research, we conclude by mentioning some of the problems we are still working on.
| Back to home page | Program | Parallel sessions |
BOULAKSIL, YOUSSEF
Eindhoven University of Technology
Faculty of Technology Management
P.O. Box 513
5600 MB Eindhoven
y.boulaksil@tue.nl
Supervisor
Jan Fransoo
A multi-period stochastic inventory model with capacity reservation
Abstract
Inspired by a real-life case, we consider a setting with an OEM (Original Equipment Manufacturer) that has outsourced the production activities to a CM (Contract Manufacturer). The CM produces on a non-dedicated capacitated production line, i.e. the CM produces for multiple OEMs on the same production line. The CM requires from all OEMs to reserve capacity slots before ordering. If the cumulative reservation quantities exceed the CM's production capacity (in a certain time period), then the CM allocates the (capacity) shortage(s) based on unknown rules and priorities. Therefore, the available capacity per time period for the OEM is uncertain, also because the OEM has no information about the reservations of the other OEMs.
We study this problem from the OEM's perspective that faces stochastic demand and stochastic capacity from the contract manufacturer. The order process is as follows. The OEM makes a capacity reservation for a certain time period. One period later, the contract manufacturer announces the available capacity for the OEM for that time period. The accepted reservation quantity is then the minimum of the reservation quantity and the available capacity. Immediately after the announcement, the OEM places an order which cannot exceed the accepted reservation quantity and which is delivered after a number of time periods.
A single-item, multi-period, periodic review inventory system (of the OEM) is considered with an order process as described above. We assume linear inventory holding, backorder, and reservation costs. We develop a stochastic dynamic programming model for this problem and show the structure of the optimal policy. Our numerical results reveal several interesting managerial insights.
| Back to home page | Program | Parallel sessions |
BRUIN, JOSINE
EURANDOM
P.O. Box 513
5600 MB Eindhoven
bruin@eurandom.tue.nl
Supervisor
Jan van der Wal
A dynamic control strategy for multi-item production systems
Abstract
A multi-item production system is considered, in which one machine can make N different types of products, but only one at a time. Demand arrives according to (compound) Poisson processes and setup or switch-over times are needed to switch from one product type to another. Production times are deterministic, so the system can be modeled in discrete time. Furthermore, unsatisfied demand can be backlogged or considered as lost. In the case of backlogged demand, a minimization of holding and backlogging costs can be obtained via MDP. The same approach can be used for the minimization of holding and penalty costs in the system with lost sales. However, this approach becomes numerically intractable if the system is large in the number of product types. Therefore, we perform a one step improvement approach based on a fixed cycle policy. In this policy, each item experiences both a production and a vacation period of fixed length. This structure of the fixed cycle control allows us to analyse the system as a combination of N independent product flows. Therefore, the relative values that are used as input for the improvement step can be decomposed into the sum of N separate relative values. Decision or base stock levels are used to decide whether a production should take place. The determination of these levels is done by using a news vendor type equation if unsatisfied demand is backlogged, and with a local search algorithm in the case of lost sales.
The dynamic one step improvement policy is compared with the existing policies exhaustive and gated base stock control. For small systems, the optimal policy is found.
| Back to home page | Program | Parallel sessions |
DIMITROVA, DESISLAVA
Faculty of EWI
University of Twente
P.O. Box 217
7500 AE Enschede
d.c.dimitrova@ewi.utwente.nl
Supervisor
Hans van den Berg
Flow level performance evaluation of UMTS-EUL scheduling schemes
Abstract
The Enhanced Uplink (EUL) is expected to provide higher capacity, increased data rates and smaller latency on the communication link from users towards a UMTS mobile network. A key mechanism in the EUL traffic handling is the packet scheduler. We analyze the performance of a number of basic channel oblivious scheduling schemes (one-by-one, partial parallel, and full parallel) under various network and traffic conditions. In the discussion we scale up from single cell with no interference to full scale network with inter-cell interference.
For our analysis, we have developed a hybrid analytical/simulation approach allowing for fast evaluation and still representing accurately scheduler specifics. This approach takes into account both the packet-level characteristics and the flow-level dynamics due to the random user behavior. A key element of the flow-level modeling is the application of continuous time Markov chains. As performance parameters we consider mean flow transfer times, fairness and coverage. Along with performance evaluation we also discuss particular decisions at the modeling stage.
Finally we will discuss possible modification of the concept of the system in order to be more power efficient. This includes making use of relaying and multi-hop transmissions within a single UMTS cell.
| Back to home page | Program | Parallel sessions |
DOBRE, CRISTIAN
Tilburg University
CentER
Department of Econometrics and Operations Research
P.O. Box 90153
5000 LE Tilburg
c.dobre@uvt.nl
Supervisor
Etienne de Klerk
Reduction of symmetric semidefinite programs using the regular *-representation and canonical block diagonalization
Abstract
We consider semidefinite programming problems for which the data matrices lie in a C* matrix algebra. We describe a general technique to reduce the size of such problems. The technique is based on a low order matrix *-representation of the matrix *-algebra that containes the data matrices. Further reduction, using canonical block diagonalization of the low order matrix *-representation is presented. This sequence of reduction is useful when the dimension of the problem is to big to be directly handled by canonical block diagonalization. We exemplify by applying it to extend a method of de Klerk et al. that gives a semidefinite programming lower bound to the crossing number of complete bipartite graphs. In this case a permutation group is acting on the initial data matrix of the problem. The permutation matrices generate a matrix algebra. We can restrict optimization to the commutant (centarlizer ring) of this algebra that has a low order matrix *-representation (regular*-representation) which can be further block diagonalized.
| Back to home page | Program | Parallel sessions |
EGGERMONT, CHRISTIAN
Eindhoven University of Technology
Department of Mathematics and Computer Science
P.O. Box 513
5600 MB Eindhoven
c.e.j.eggermont@tue.nl
Supervisors
Cor Hurkens and Gerhard Woeginger
Fixing a broken schedule
Abstract
Commercial airlines operate flights according to a published flight schedule that is optimized from a revenue standpoint. However, external events such as mechanical failures, personnel strikes, or inclement weather frequently occur, disrupting planned airline operations. In such cases, it is necessary to find in a short time efficient solutions that minimize the duration of the disruption, thus minimizing its impact.
Disruptions can take place at multiple airports and at different times within the planning horizon. The problem we consider was proposed by Operations Research Division of Amadeus S.A.S. and is part of the 2009 Challenge issued by the Societe Francaise de Recherche Operationnelle et Aide a la Decision. We present our approach to this complex problem and our results. This is joint work with Murat Firat, Cor Hurkens and Maciej Modelski.
| Back to home page | Program | Parallel sessions |
FIRAT, MURAT
Eindhoven University of Technology
Department of Mathematics and Computer Science
P.O. Box 513
5600 MB Eindhoven
m.firat@tue.nl
Supervisor
Cor Hurkens
Scheduling tasks with skill constraints
Abstract
The supervisor in the planning department of a telecommunication company is faced with a task scheduling problem in which tasks require certain skill qualifications and technicians are qualified at different skill levels. Required skill levels of tasks are specified in domains. On each day of the schedule, eligible technicians are grouped to perform a sequence of tasks with the total duration of at most one workday. Due to the limited number of cars compared to the number technicians, a team performs the assigned tasks together during the whole day. Depending on the customer, working conditions, timing etc. tasks have priorities. On the other hand the planning department has a limited budget to hire external companies for performing some tasks.
The time spent for determining the schedule is limited to 20 minutes, so time is precious in constructing a low-cost schedule. We developed a combinatorial approach to the real-world problem defined above. Our approach includes two elegant integer linear programming models. The first one, which we call the Lower Bound Model, runs for possible priority orderings to decide which tasks to abandon, in which priority order to perform the remaining tasks and to find lower bound values for the schedule cost. The second one, called the Bipartite Matching Model, is used to combine the technicians into teams while finding tasks whose skills requirements fit to the offered skills by the team. The approach is fully implemented in Java including CPLEX models. We present the formal descriptions of the models and finally we report the results obtained on given sets of instances provided by the telecommunication company.
| Back to home page | Program | Parallel sessions |
GU, GUOYONG
Faculty EWI
Delft University of Technology
Mekelweg 4
2628 CD Delft
g.gu@tudelft.nl
Supervisor
Kees Roos
Full Nesterov-Todd step interior-point methods for symmetric optimization
Abstract
Some Jordan algebras were proved more than a decade ago to be an indispensable tool in the unified study of interior-point methods. By using it, we generalize the infeasible interior-point method for linear optimization of Roos [SIAM J. Optim., 16(4): 1110--1136 (electronic), 2006] to symmetric optimization. This unifies the analysis for linear, second-order cone and semidefinite optimizations.
| Back to home page | Program | Parallel sessions |
KAYNAR, BAHAR
Faculty of Economic Sciences
Vrije Universiteit Amsterdam
De Boelelaan 1105
1081 HV Amsterdam
bkaynar@feweb.vu.nl
Supervisor
Ad Ridder
Markovian systems via cross entropy: patching algorithms
Abstract
There are various importance sampling schemes to estimate rare event probabilities in Markovian systems such as Markovian reliability models and Jackson networks. In this work, we present a method which partitions the state space and applies the cross entropy method to each partition. We give several examples of reliability and queuing models and for each example we compare our method with other importance sampling schemes. The performance of importance sampling schemes is measured by the relative error of the estimator and by efficiency. The results from experiments show considerable improvements both in running time of the algorithm and the variance of the estimator.
| Back to home page | Program | Parallel sessions |
KOK, LEENDERT
University of Twente
Faculty of EWI
Department of Mathematics
P.O. Box 217
7500 AE Enschede
a.l.kok@utwente.nl
Supervisors
Marco Schutten and Erwin Hans
Restricted dynamic programming: a flexible framework for solving realistic VRPs
Abstract
Vehicle routing problems (VRP) have been extensively studied in the past decades. Since transportation costs constitute a significant part (4 to 10 percent) of a product selling price, efficient vehicle routing methods are highly valuable in practice. In order to cope with real life restrictions, many generalizations of the VRP have been proposed. Local search methods have proven to be very successful in solving these variants of the VRP. However, a major drawback of local search methods is that they require careful tailoring for each VRP variant in order to obtain high quality solutions. Therefore, incorporating new restrictions is a difficult task. We present a flexible framework for solving VRPs based on restricted dynamic programming. We demonstrate its flexibility by showing how a wide range of real-life restrictions can easily be incorporated in the framework, including some hard restrictions such as time-dependent travel times and driving hours regulations, which are generally ignored in the VRP-literature. The quality of the restricted dynamic programming method is demonstrated by solving a set of benchmark instances for the capacitated vehicle routing problem (CVRP).
| Back to home page | Program | Parallel sessions |
KRUSHINSKY, DMITRY
Department of Econometrics and Operations Research
University of Groningen
P.O. Box 800
9700 AV Groningen
d.krushinsky@rug.nl
Supervisor
Boris Goldengorin
Experimental study on cellular automata models of pedestrian traffic
Abstract
Movement of large-scale pedestrian crowd is a complex phenomenon that leads to computationally intractable models. Cellular automata (CA) proved to be an effective tool for the construction of realistic models; however existing CA-based models do not take into account mental properties of pedestrians. In this presentation a framework for introduction of such mental property as anticipation into CA models of pedestrian crowd movement is developed. By the term "anticipation" we mean pedestrian's ability to foresee the situation in his neighbourhood and to adjust his current behaviour so as to ensure the most desirable future. The results of computational experiments with the proposed framework are presented.
| Back to home page | Program | Parallel sessions |
MARCHAL, BERT
Maastricht University
Department of Quantitative Economy
P.O. Box 616
6200 MD Maastricht
b.marchal@ke.unimaas.nl
Supervisor
Stan van Hoesel
Finding good tree decompositions using local search
Abstract
The treewidth of a graph equals the minimum width over all tree decompositions of the graph. The problem of determining treewidth has been proven to be NP-complete. Nevertheless, it does play a central role in algorithmic graph theory, since many algorithmic problems that are otherwise intractable become polynomial time solvable when restricted to graphs of bounded treewidth. These problems include classical problems like Independent Set, Hamiltonian Circuit, Chromatic Number, Vertex Cover, Steiner Tree and many others. To solve these problems, dynamic programming methods must be applied to bounded width tree decompositions of the input graph. Since both the running time and memory consumption of those DP algorithms are exponential in the width of the tree decomposition, they require good tree decompositions, i.e. decompositions that have a width as low as possible. Several constructive (in the sense that they deliver tree decompositions) approximation algorithms exist for the treewidth problem, but they take too much time to be of great practical use. There are some quick constructive upper bound heuristics for treewidth as well, but the width of the tree decompositions generated by them is often far away from the actual treewidth of the graph. We present a local search algorithm for generating tree decompositions of graphs. The algorithm exploits a new neighborhood structure that operates directly on tree decompositions, contrary to earlier work that generally used derived notions such as triangulations or elimination orders of the vertices. As a side result, we obtain an algorithm for making tree decompositions minimal.
| Back to home page | Program | Parallel sessions |
POTTHOFF, DANIEL
Econometric Institute
Erasmus University
P.O. Box 1738
3000 DR Rotterdam
potthoff@few.eur.nl
Supervisor
Albert Wagelmans
An algorithm for railway crew rescheduling
Abstract
The Dutch railway network experiences on average 3 large disruptions per day. These disruptions can be caused by the infrastructure malfunctions, the weather, third parties, and the operator itself. In the Dutch situation, the infrastructure manager ProRail is responsible for modifications in the timetable. However, the rolling stock circulation and the crew schedules are the responsibility of the operators. The main Dutch railway operator, NS, changes these schedules in its Operational Control Centers. Currently, there is no decision support at all in these centers. We will present an algorithm that we have developed for crew rescheduling. We formulate the crew rescheduling problem as a set covering model with side constraints considering a subset of duties and tasks. Although choosing a good subset is a far from trivial task, we were able to do so and in this way the required computation time is in the order of magnitude of a couple of minutes. Our solution approach consists of a combination of Lagrangian Relaxation and column generation techniques. The Lagrangian Dual problem is solved with a subgradient algorithm, where in each iteration a trivial Lagrangian subproblem is solved. Moreover, a Lagrangian heuristic is applied to obtain feasible solutions. This heuristic replaces greedily every original duty with a new one. To generate new duties, a so-called pricing problem is solved, which selects duties based on dual information from the Lagrangian problem. In this case, the pricing problem can be solved as a resource constrained shortest path problem. In this presentation, we will present computational experiments with our crew rescheduling algorithm on some real-world instances.
| Back to home page | Program | Parallel sessions |
SILALAHI, BIB PARUHUM
Faculty EWI
Delft University of Technology
Mekelweg 4
2628 CD Delft
b.p.silalahi@ewi.tudelft.nl
Supervisor
Kees Roos
On pathological central paths in the Klee-Minty cube
Abstract
In the recently developed polynomial time interior point methods for optimization, the so-called central path is used as guide line to the set of optimal solutions. For the Klee-Minty problem, by adding appropriate redundant constraints, the central path can be forced to visit all the vertices of the feasible domain of the problem. This has been achieved by adding redundant constraints to the Klee-Minty problem. In this paper we achieve the same phenomenon by using fewer redundant constraints.
| Back to home page | Program | Parallel sessions |
TALLA NOBIBON, FABRICE
Faculty of Business and Economics
KU Leuven
Naamsestraat 69
B-3000 Leuven
België
fabrice.tallanobibon@econ.kuleuven.be
Supervisor
Frits Spieksma
Heuristics for deciding collectively rational consumption behavior
Abstract
We consider the computational problem of testing whether observed household consumption behavior satisfies the Collective Axiom of Revealed Preferences (CARP). We propose a graph such that the existence of a node-partitioning giving rise to two induced subgraphs that are acyclic implies that the data satisfy CARP. Furthermore, we propose and implement heuristics that are quite fast, that can be used to check reasonably large datasets for CARP and that can be of particular interest when used prior to computationally demanding approaches. Finally, from the computational results we conclude that these heuristics can be effective in testing CARP.
| Back to home page | Program | Parallel sessions |
VERHOEF, CHRÉTIEN
CWI
Kruislaan 413
1098 SJ Amsterdam
c.g.verhoef@cwi.nl
Supervisor
Rob van der Mei
Performance analysis of coordination systems using Reo
Abstract
We describe a method to quantify the performance of complex coordination systems using the Reo coordination language. Reo is a channel-based exogenous coordination language which has a formal basis and supports loose coupling, distribution, dynamic reconfiguration and mobility. We consider the inherent stochastic behavior of those complex coordination systems. Reo allows compositional construction of models for these systems using architecturally meaningful primitives. One way to quantify performance is by using Continuous Time Markov Chains (CTMCs). Constructing the appropriate CTMC for complex distributed systems is often a complicated task, and it is regularly difficult to find their appropriate state space and transitions. We propose a stepwise approach using Stochastic Reo and Quantitative Intentional Automata (QIA) to model coordination systems as CTMC for a given Reo circuit by adding performance properties to functional Reo primitives. Hereby it is possible to automaticly generate the resulting CTMC.
| Back to home page | Program | Parallel sessions |
YANG, RAN
Vrije Universiteit Amsterdam
& CWI
De Boelelaan 1081a
1081 HV Amsterdam
ryang@cs.vu.nl
Supervisors
Rob van der Mei, Ger Koole and Sandjai Bhulai
Optimal resource allocation for time reservation systems
Abstract
In recent years new real-time multimedia services have triggered a tremendous growth in data volumes and computational demands. Typical services include iris scan systems and fingerprint systems, that make high-resolution scans and require processing of the data to identify the person; these services operate in a real-time environment and run under very strict time constraints. To adhere to such constraints, these large-scale services typically use centralized computing clusters to execute on. In large-scale systems, the applications can reserve a number of processing resources to process the data. This gives rise to a new class of models in which the application has to decide when to reserve the processing resources and how many. In this decision making there is a trade-off between the lead time on the one han d and the costs on the other hand. Making a reservation too early leads to inefficiency, since the processing resources have to wait on the data gathering/scanning process. Also, allocating too many processing resources results in a short lead time, but comes at high allocation costs. We show via dynamic programming that the optimal number of processors follows a step-function with as extreme policy the bang-bang control. Moreover, we study the dependence of the two service stations, under different service distributions, when a time constraint on the total sojourn time in the system is enforced.
| Back to home page | Program | Parallel sessions |
ZANGIABADI, MARYAM
Faculty EWI
Delft University of Technology
Mekelweg 4
2628 CD Delft
maryam@st.ewi.tudelft.nl
Supervisor
Kees Roos
Full Nesterov-Todd step primal-dual interior-point methods for second-order cone optimization
Abstract
Clich here for pdf file of the abstract
| Back to home page | Program | Parallel sessions |