[an error occurred while processing this directive]
Efficient Simulation for Rare Events and Combinatorial Optimization
Center for Telematics and Information Technology (CTIT)
University of Twente
July 15-16, 1999
For location and time schedule, click here.
LECTURER
Professor Reuven Y. Rubinstein
William Davidson Faculty of Industrial Engineering and Management
Technion, Haifa, Israel
Telephone: 972-4-8294458
Fax: 972-4-823-5194
E-mail: ierrr01@ie.technion.ac.il
WWW: http://iew3.technion.ac.il:8080/ierrr01.phtml
SCOPE
Stochastic systems abound in real-world applications. Examples include
traffic systems, flexible manufacturing systems, computer-communications
systems, inventory systems, production lines, coherent lifetime systems,
PERT networks and flow networks. Most of these systems can be modeled
in terms of discrete events whose occurrence causes the system to change
from one state to another. Such systems are called `discrete-event
systems' (DES). For most real-world DES, analytical methods are not
available and they must be studied via simulation. In designing,
analyzing and operating such complex DES, one is interested, however,
not only in performance evaluation but also in sensitivity analysis
and optimization. Sensitivity analysis is concerned with evaluating
sensitivities (gradients, Hessians, etc.) of performance measures
with respect to parameters of interest. It provides guidance for design
and operational decisions and plays a pivotal role in identifying the
most significant system parameters, as well as bottleneck subsystems.
Optimization is concerned with a DES as a whole; in particular, it makes
use of sensitivity analysis to find the optimal solution with respect to
parameters of interest.
The goal of this course is to present a number of efficient (smart) Monte
Carlo techniques for performance evaluation, sensitivity analysis with an
emphasis to probability of rare event estimation in stochastic networks.
In particular the audience will learn:
-
How a single simulation run can be used to estimate an entire
response surface and the associated gradient (sensitivity) curves
in an efficient way.
-
How the calculation of simulation output statistics can be speeded up
by factors of tens and hundreds, for typical performance measures,
and by factor of thousands, for rare event simulations.
-
How to solve combinatorial optimization problem, like the maximal cut
problem, traveling salesman problem, etc., using efficient rare event
techniques and information theory.
It will be shown that all the above are feasible due to the fact that the
simulation experiments to be performed on a digital computer are largely
computational and not purely statistical. It will also be explained how
to use the cross-entropy method to extract the most valuable information
obtained during the course of simulation.
A research software package demonstrating the efficacy and efficiency of
the proposed techniques will be made available for the participants of
this course, as well as a number of case studies. Participants are
encouraged to bring along their own examples and case studies and
run them during and after the course.
WHO SHOULD ATTEND
Simulation practitioners, computer scientists, industrial, electrical
and financial engineers, graduate students and anyone interested in
fast simulation of discrete event systems.
TOPICS OUTLINE
-
Fast estimation of performance measures for both static and dynamic
models via simulation.
-
Fast estimation of derivatives (sensitivities) from a single
simulation run.
-
Fast estimation of probabilities of rare events via exponential
change-of-measure and cross-entropy.
-
Combinatorial optimization problems via rare events and cross-entropy.
-
Case studies and software presentation.
EXPECTED BENEFITS
Participants will learn the key ideas and features of modern simulation.
Special emphasis will be placed on sensitivity analysis, probability
of rare-event estimation and randomized algorithms for combinatorial
optimization. Participants will be shown how to take advantage of simple
change-of-measure ideas and cross-entropy so as to reduce the time
complexity required by statistical computations in Monte Carlo simulations.
These ideas will then extended to the speeding up of computations in
stochastic and deterministic combinatorial optimization models.
PARTICIPATION
All interested are invited to participate at no charge!
Each participants is responsible for his own arrangements
to attend the course (e.g., accommodation, meals, etc.)
For admission (on a FCFS basis) and other details,
please e-mail to:
resim99@cs.utwente.nl.
PROGRAM AND TIME SCHEDULE
Thursday, July 15th, 10:00-12:30 and 14:00-17:30 :
- Performance evaluation, sensitivity analysis and optimization
of computer simulation models
- Introduction to estimation of rare event probabilities
Friday, July 16th, 9:00-13:00 :
- Advanced topics on rare events and their application to optimization
of stochastic networks
LOCATION
Room INF-U2,
Computer Science building ("Informatica-gebouw")
University of Twente, Enschede, The Netherlands
Travelling information to the university is available
here.
A map of the campus showing the "INF-gebouw" is available
here.
[an error occurred while processing this directive]