Projets de recherche au laboratoire d'optimisation
Felisa J. Vázquez-Abad
Performance Evaluation of Loss Networks with Dr. Lachlan Andrew,
(Melbourne University) postdoctoral research project.
We have studied efficient simulation methods for estimation of blocking
probability in WDM Optical networks and cellular networks. We have proposed a
Monte Carlo Markov Chain method, which we call the Filtered Gibbs sampler (see
our paper, presented at ESM 2000).
As well, we have implemented Importance
Sampling for efficiency improvement, by embedding the A-cycles in the Standard
clock formulation. Our results appear in this paper for
a cellular network with dynamic channel assignment.
Our techniques can be found in the technical
Intelligent Allocation of Lightpaths in a WDM Network
(with Lachlan Andrew, Melbourne University) possible PhD research project.
- We have proposed an adaptive control technique to groom the traffic into
the lightpaths for WDM networks that contain few wavelengths per fibre, but
each wavelength is assumed to suppor enough bandwidth to carry several calls
We propose to study the behaviour of such controls, wich we call "birth and
death of lightpaths" when fairness measures are incorporated to drive the
stochastic approximation algorithms.
Adaptive Frequency Allocation in a Subway network
Fabrice Plaçon, projet IFT3051 Hiver 2000. M Sc IFT6561 projects, 2001:
Francis Forget, Dominique Tourillon,
Alexandre Desrosiers and Jean-Robert Quevillon.
The goal of this project is to write, validate and test the model
of a subway network for global adjustment of frequencies to track the
optimal allocation as traffic patterns change seasonally, which we have
proposed in this paper. The students
will learn the basics of renewal processes, stochastic optimisation
and review gradient-based methods for adaptive control. In addition,
they will become proficient in event-driven simulation models.
Our first results show that a local ersatz model for the stations
accurately reproduces the statistical performance measurements. Based
on the local model, several formulas for the local sensitivitity will
be compared and used to incorporate a global model for adaptive
Stage 1: Literature review for the
problem formulation as well as derivative estimation. Programming code for
network. (Team 1)
Stage 2: Reproduction of the global
derivatives from the local derivatives, analytically as well as
implementation of the corresponding estimates. Statistical analysis
of the model with day segments. (Team 2)
Stage 3: Extension of the results to
realistic modeling: fixed amount of trains on each line, finite wagon
capacity, and (time permitting)
study of the extension to bi-level modelling.
Call vs Cell Sensitivities for an ATM Switch Katerine
Martin, été 2000 et projet IFT3051 2001.
- The goal of this project is to execute statistical
tests of simulations of an ATM based network to compare the sensitivity
of perfomance measures to changes in call arrival rates and a surrogate
approximation via the local sensitivities to changes in the local cell
arrival rates. Based on theoretical results for some Markovian arrival
models, our ersatz estimation via local quantities can be used
to create an efficient, robust global control of the network which is completetely
decentralized and asynchronous. See our paper,
presented at CDC 1999.
Preliminary work done in this direction has shown
good results. The students that undertake this project
will review (or learn) the basis of Queueing
Theory, adaptive control, and gradient estimation techniques. A good statistical
basis is preferable, and excellent knowledge of C is mandatory.
Stage 1: Getting
acquainted with the problem. Reading the basic references (3 research articles
and a reference book),
Getting acquainted with the simulation of one single switch, polling
and cell arrival sensitivities, 2 weeks (concurrent with stage 1).
Surrogate Gradient Estimation: polling, cell arrival rate, call arrival
rate, 12 weeks (concurrent with stage 1).
Extending Results to a Small Network, 4 weeks. (To do)
Adaptive Search Methods. Katerine Martin and Irina Baltcheva,
research projet 2002 (collaboration with Vikram Krishnamurthy).
The long term goal of this project is to apply stochastic approximation techniques to
solving large Markov Decision Process problems, with particular interest in
adaptive search problems. Actions can be taken at each stage of the evolution of
the process. For many models, it can be shown that the optimal choice is a
strategy that assigns one choice that depends on the current state. Neuro-dynamic
moethods can be used to solve the problem but they may be very costly when the
state-action space is large.
In this research the student will become aquainted with the problem and basic
solution techniques. We propose to use a randomized strategy where choices are
taken at random, yet the probabilities for making decisions will be subject to
The first stage of the project is to implement a modified search method and
compare the convergence rate with that of our previous algorithms reported in this
paper. Next the student will compare convergence
effort with that of neuro-dynamical programming techniques.
Understand the basic structure of optimal allocation problems subject to simplex
constraints. Derivation of Kuhn-Tucker conditions for optimality. 2 weeks
Program the direct solution of the ODE driven by the updating directions
(generalised gradient) for a queueing model with closed solution. Program the
solution of the corresponding steepest descent method for the indirect problem
under a variable transformation. Comparison of convergence rates of the two
problems. 5 weeks
Implementation of the simulation of the queueing model and implementation of the
phantom method for the evaluation of the gradients. Comparison of the
performance of the simulations for the direct and the indirect updating methods.
Implementation of the above techniques to a Markov Decision Process, using the
filtered phantom method. Comparison of results with Lagrange-based equations
for the soft constrained and the gradient approximation method for truncation.
comparisons will cover models for searching in GSM mobile networks, where the MDP
is subject to partial observations only.
Estimation of Blocking in Mobile CDMA Networks. Irina Baltcheva,
été 2000 et projet IFT3051, 2001
The goal of this project is to implement a model developed for the
stationary state of a cellular urban network and apply Importance
Sampling for an efficient estimation of blocking probabilities.
The student will become acquainted with the basic properties of spacial
Poisson processes as well as the basic notions of CDMA models. In
addition, she will learn the principles of the change of measure
approach for efficient estimation. Knowledge of probability is desired,
and if the student has a mathematical background, an introduction to
large deviations and their relationship to Importance Sampling will also
The last phase of development involves implementation of the intelligent search
method to optimise on-line the parameters of Importance Sampling.
Évaluation des options exotiques. (collaboration avec Daniel
- The goal of this project is to implement the method called
"accelerated simulation" to the estimation of option prices. See our paper, presented at WSC 1998. (6 weeks)
Estimation of ruin probabilities.
- The goal of this project is to implement ersatz formulas for the
estimation of the ruin probabilities and the value at risk of a
stratified insurance portfolio, following the canonical model of Risk
Theory. Then, extend the model for the case where the surplus is
invested at a fixed interest rate. ( 4 weeks)
Development of BestNet
Maryse Boisvert, Arnoldo Rodríguez PhD (jointly with
Esma Aimëur and Moshe
Zukerman, Melbourne University).
- BestNet is a web site for enhancing teaching of network design
in postgraduate level. It was originally developped to support a Master's course
at the Dept of Electrical and Electronic Engineering in
Melbourne University. The site proposes a new model for bridging theoretical
concepts with realistic decision making skills, through the
integration of mathematical models into practical situations. To achieve this we
propose a model of tasks with incremental difficulty and an environment of a
It is conceived as an aid to complement traditional teaching and offers
teachers a virtual office where they can edit and modify the tasks according to
their pedagogical goals. This feature endows the site with flexibility. Maryse
Boisvert is in charge of the database management and the functioning of the
server. A summer project could undertake the adaptation of the currrent graphical
interface (in shockwave) to java. The PhD project undertakes the creation of a
model for such sites, work done in the HERON lab.
Development of SimSpiders.
- An on-going project to create a tutorial on stochastic simulation.
For the moment, SimSpiders is a static turorial with a couple of
java simulators to show the stochastic trajectories of a process and illustrate
some basic statistical concepts. Our goal is to enhance the site with more
efficient simulations and perhaps also incorporate interactivity.
Web Sites: SimSpiders
Blocking in Loss Networks
Dynamic control for WDM Nets
Transport: Adaptive metro network
Telecom 3: Intelligent ATM Switch
Adaptive Search: Learning methods for
optimal MDP's with applications to search problems.
Telecom 4: Efficient estimation
Finance: Option Pricing via
Risk Theory: Ruin Probabilities
Web Sites: BestNet