Université de Montréal

Faculté des arts et des sciences
Departément d'informatique et de recherche opérationnelle

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 report.

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 simultaneously.

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 control.

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), 5 weeks.
Stage 2: Getting acquainted with the simulation of one single switch, polling and cell arrival sensitivities, 2 weeks (concurrent with stage 1).
Stage 3: Surrogate Gradient Estimation: polling, cell arrival rate, call arrival rate, 12 weeks (concurrent with stage 1).
Stage 4: 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 learning mecanisms.

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.

Stage 1: Understand the basic structure of optimal allocation problems subject to simplex constraints. Derivation of Kuhn-Tucker conditions for optimality. 2 weeks
Stage 2: 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
Stage 3: 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. 6 weeks.
Stage 4: 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. Experimental 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 be acquired.

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 Dufresne).
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 virtual competition. 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.

Telecom 1: Blocking in Loss Networks
Telecom 2: 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 for CDMA.
Finance: Option Pricing via Simulation.
Risk Theory: Ruin Probabilities and VaR.
Web Sites: BestNet
Web Sites: SimSpiders

Felisa J. Vázquez-Abad
Département d'informatique et recherche opérationnelle
Université de Montréal
C.P. 6128 Succursale Centre-Ville
Montréal, Québec H3C 3J7
Tel: (514) 343-6951, Fax (514) 343-5834
e-mail vazquez@iro.umontreal.ca
More information about the Department
Pour plus d'information sur le laboratoire d'optimisation