|
|
Abstracts presentations phd studentsASADI, ALIREZA Faculty EWI Supervisor 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).
BIJVANK, MARCO Vrije Universiteit Amsterdam Supervisor 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.
BOMHOFF, MATTHIJS Faculty of EWI
Supervisor 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.
BOULAKSIL, YOUSSEF Eindhoven University of Technology Supervisor 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.
BRUIN, JOSINE EURANDOM Supervisor 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.
DIMITROVA, DESISLAVA Faculty of EWI
Supervisor 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.
DOBRE, CRISTIAN Tilburg University
Supervisor 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.
EGGERMONT, CHRISTIAN Eindhoven University of Technology Supervisors 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.
FIRAT, MURAT Eindhoven University of Technology Supervisor 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.
GU, GUOYONG Faculty EWI Supervisor 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.
KAYNAR, BAHAR Faculty of Economic Sciences Supervisor 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.
KOK, LEENDERT University of Twente Supervisors 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).
KRUSHINSKY, DMITRY Department of Econometrics and Operations Research
Supervisor 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.
MARCHAL, BERT Maastricht University Supervisor 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.
POTTHOFF, DANIEL Econometric Institute
Supervisor 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.
SILALAHI, BIB PARUHUM Faculty EWI Supervisor 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.
TALLA NOBIBON, FABRICE Faculty of Business and Economics Supervisor 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.
VERHOEF, CHRÉTIEN CWI Supervisor 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.
YANG, RAN Vrije Universiteit Amsterdam
& CWI Supervisors 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.
ZANGIABADI, MARYAM Faculty EWI Supervisor Full Nesterov-Todd step primal-dual interior-point methods for second-order cone optimization Abstract Clich here for pdf file of the abstract
|
