Thomas Stieltjes Institute for Mathematics

Operations Research 1997/98


Title: Course Stochastic Operations Research 1
Organisation: Landelijk Netwerk Mathematische Besliskunde.
for more information on the LNMB
Lecturers: H.C. Tijms (VU), Part a (6 sessions)
L.C.M. Kallenberg (RUG/RUL), Part b (6 sessions)
Time and place: Fall 97, 12 Mondays (September 22 until December 8)
CSB Zalenverhuur, Kromme Nieuwegracht 39, Utrecht
tel: 030-2312120
Contents: Part a (Tijms):
Renewal theory provides elegant and powerful methodes for analysing stochastic processes that generate themselves from time to time. The long-run behaviour of a regenerative stochastic process can be studied in terms of its behaviour during a simple regeneration cycle. The Markov chain model is the simplest generalization of the probability model independent trials. The Markov model is no exception to the rule that simple models are often useful for analysing practical problems. Applications are given for processes with discrete and continous time parameter. In this course the following issues are discussed:
  1. Renewal theory and regenarative processes: the renewal function; the renewal theorem; asymptotics; ergodicity; the compound Poisson process.
  2. Markov chains: discrete and continuous time processes; state classification; the equilibrium distribution; flow-in-flow-out technique; uniformization method.
Part b (Kallenberg):
Markov decision processes The Markov decision model is a powerful tool to analyse probabilistic sequential decision processes with finite or infinite planning horizon. Subjects to be discussed are:
  1. Introduction with examples;
  2. For discounted, undiscounted and sensitive optimality criteria: the optimality equation; the policy improvement method, the linear programmering method and the method of successive approximations.
  3. Applications: casino models; optimal stopping; replacement models; multi-armed bandit problems.
Literature:
  • Part a: H.C. Tijms, "Stochastic models - an algorithmic approach", John Wiley and Sons, New York, 1994 (ISBN 0-471-95123-4). The prize of this book is approximately Dfl. 75,-. The LNMB will give a discount of Dfl. 25,- for Ph.D. students who attend this course. If you will use this offer, please send an e-mail message to the secretary before September
  • Part b: Lecture notes will be provided (free of charge).
Prerequisites: Elementary knowledge of probability theory (for the parts a and b); elementary knowledge of linear programming (for part b).
Examination: Take home problems.
Adresses of the lecturers:

Prof.dr. H.C. Tijms
Vakgroep Econometrie
Faculteit Economische Wetenschappen en Econometrie
Vrije Universiteit Amsterdam
De Boelelaan 1105
1081 HV Amsterdam
Phone : 020 - 4446013
E-mail : tijms@econ.vu.nl

Prof.dr. L.C.M. Kallenberg
Afdeling Wiskunde en Informatica
Rijksuniversiteit Leiden
Postbus 9512
2300 RA Leiden
Phone : 071 - 5277144
E-mail : kallenberg@rulwinw.leidenuniv.nl


Title: Course Combinatorial Optimization 1
Organisation: Landelijk Netwerk Mathematische Besliskunde.
for more information about the LNMB
Lecturers: W. Kern (UT), Part a (6 sessions)
A.M.H. Gerards (CWI), Part b (6 sessions)
Time and place: Fall 97, 12 Mondays (September 22 until December 8)
CSB Zalenverhuur, Kromme Nieuwegracht 39, Utrecht
tel: 030-2312120
Contents: Theory and solution methods for combinatorial optimization problems are presented. Special attention is paid on methods that have a polynomial running time and on approaches based on graph theory, polyhedral combinatorics and matriod theory. The following subjects are discussed: Shortest paths and trees; polytopes and polyhedra; Farkas' lemma and linear programming; matchings and covers; Menger's theorem; flows and circulations; problems, algorithms and running times; cliques, cocliques and colouring; integer linear programming and totally unimodular matrices; multicommodity flows and disjoint paths; matroids.
Literature: Lecture notes will be provided (free of charge).
Prerequisites: No special prerequisites are necessary.
Examination: Take home problems.
Adresses of the lecturers:

Dr. W. Kern
Vakgroep Stochastiek en Operationele Research
Faculteit Toegepaste Wiskunde
Universiteit Twente
Postbus 217
7500 AE Enschede
Phone : 053 - 4893838
E-mail : w.kern@math.utwente.nl

Dr.ir. A.M.H. Gerards
CWI
Postbus 94079
1090 GB Amsterdam
Phone : 020 - 5924045
E-mail : bgerards@cwi.nl


Title:Course Stochastic Operations Research 2
Organisation: Landelijk Netwerk Mathematische Besliskunde.
for more information about the LNMB
Lecturers: J. Wessels (TUE) and I.J.B.F. Adan (TUE), Part a (6 sessions)
O.J. Boxma (CWI/KUB), Part b (6 sessions)
Time and place: Spring 97, 12 Monday mornings
(January 26 until April 27, no courses on April 6 and 13)
CSB Zalenverhuur, Kromme Nieuwegracht 39, Utrecht
tel 030-2312120
Contents: A number of important results in queueing theory is presented and their applicability for performance analysis of computer, communication and production systems is shown.
Topics to be covered include:
  • Part a: Queueing models; birth-and-death processes; Little's formula; M/G//1-queue; PASTA.
  • Part b: generating functions; Laplace-Stieltjes transform; detailed analysis M/G/1-queue; polling systems; product form networks; a machine repair model; the Erlang loss model; optimization in networks of queues; applications.
Literature: Lecture notes and articles will be provided (free of charge).
Prerequisites: Elementary knowledge of Markov chains, Markov processes, renewal theory and Markov decision processes.
Examination: Take home problems.
Adresses of the lecturers:

Prof.dr. J. Wessels
Faculteit Wiskunde en Informatica
Technische Universiteit Eindhoven
Postbus 513
5600 MB Eindhoven
Phone : 040 - 2472608
E-mail : wessels@win.tue.nl

Prof.dr.ir. O.J. Boxma
CWI
Postbus 94079
1090 GB Amsterdam
Phone : 020 - 5924049
E-mail : onno@cwi.nl

Dr.ir. I.J.B.F. Adan
Faculteit Wiskunde en Informatica
Technische Universiteit Eindhoven
Postbus 513
5600 MB Eindhoven
Phone : 040 - 2472932
E-mail : iadan@win.tue.nl


Title: Course Combinatorial Optimization 2
Organisation: Landelijk Netwerk Mathematische Besliskunde.
for more information about the LNMB
Lecturers: J.K. Lenstra (TUE), Part a (6 sessions)
C.P.M. van Hoesel (UM), Part b (3 sessions)
L. Stougie (UvA), Part c (3 sessions)
Time and place: Spring 97, 12 Monday afternoons
(January 26 until April 27; no courses on April 6 and 13).
CSB Zalenverhuur, Kromme Nieuwegracht 39, Utrecht
tel: 030 - 2312120.
Contents: Theory and solution methods for combinatorial optimization problems are presented. Special attention is paid on NP-hard problems. Exact and approximative algorithms are discussed. Also probabilistic analysis of algorithms is included. The following topics are covered:
  • Complexity theory: 'easy' (polynomial time solvable) problems and 'hard' (NP-hard) combinatorial problems; consequences of this classification for the solution strategy of combinatorial problems.
  • Optimization algorithms: optimization algorithms for NP-hard problems apply some kind of implicit enumaration (dynamic programming; branch-and-bound); special attention is paid on the computation of bounds (state relaxation; Lagrange relaxation; LP relaxation with cuts).
  • Approximation algorithms: approximation algorithms for NP-hard problems provide often quickly a good, but not necessary optimal, solution. Methods are discussed which provide a performance guarantee for the quality of the approximate solution. Also local search methods are considered.
  • Probabilistic analysis of algorithms: introduction; the partition problem; the multi-knapsack problem and the traveling salesman problem.
Literature: Lecture notes and a reader will be provided (free of charge).
Prerequisites: Knowledge of the course Combinatorial Optimization 1 is desirable, but not necessary.
Examination: Take home problems.

Adresses of the lecturers:

Prof.dr. J.K. Lenstra
Faculteit Wiskunde en Informatica
Technische Universiteit Eindhoven
Postbus 513
5600 MB Eindhoven
Tel : 040 - 2474770
E-mail : jkl@win.tue.nl

Dr.ir. C.P.M. van Hoesel
Vakgroep Kwantitatieve Methoden
Faculteit der Economische Wetenschappen
Universiteit Maastricht
Postbus 616
6200 MD Maastricht
Phone : 043 - 3883727
E-mail : s.hoesel@ke.unimaas.nl

Dr. L. Stougie
Vakgroep Econometrie en Actuariaat
Faculteit der Economische Wetenschappen en Econometrie
Universiteit van Amsterdam
Roeterstraat 111
1018 WB Amsterdam
Tel : 020 - 5254318
E-mail : leen@fee.uva.nl


Title: Course Constructive Methods for Transient Behaviour of Stochastic Networks and Applications
Organisation: Landelijk Netwerk Mathematische Besliskunde.
for more information about the LNMB
Lecturer: F.M.Spieksma, (spieksma@wi.leidenuniv.nl)
Time and place: Spring 97 - wednesday 14-17, once per two weeks, 8 lectures.
Dates: Febr 4, Febr 18, March 4, March 18, April 1, April 22, May 6, May 20
(there are of course possibilities to shift this one or two weeks in front)
Mathematical Institute, Leiden
Aim: To study constructive methods for investigating transient behaviour of stochastic networks, in particular random walks on Z^p_+ with maximal homogenity. Of main interest are stability and exponential stability properties of such walks.
Contents: We will study the so-called Euler limit of fluid limit of random walks. The Euler limit is the limiting distribution of the scaled position (by N) of the random walk after tN time units, when starting initially at the point xN. Inside the positive orthant Z^p_+, by the Law of Large Numbers this limit is deterministic and equal to x+tv, where v is the expected jump from a point. At the boundaries the limiting behaviour is more complicated: counterintuitively, it may even be stochastic. With this Euler limit one can associate dynamical systems, i.e. the paths of the limiting dynamics. In general, sufficiently general dynamical systems arise from the Euler limit. Therefore, even though it is always intuitively clear how the Euler limit looks like formally, it is not simple to prove convergence in general to the Euler limit.

In the course we will show convergence to the Euler limit under some simplifying conditions.

The Euler limits will then be used for understanding (exponential) stability and transience of the walk by the construction of suitable Lyapunov functions based on the Euler limits. In the case of transience, from the Euler limit it also follows ``how'' the walk becomes unstable.

To explicitly calculate the Euler limit, is in general a complicated problem. We will study simple conditions under which the Euler limits for particular models in the field of queueing and neural networks can be calculated and we will study properties of the associated dynamical systems. For the studied queueing models we will connect the construction of the Euler limit to the so-called oblique reflection mapping.

Structure: the course will consist of 7 lectures of 3 hours each. In the second half of the semester, participating (PhD) students will be asked to study papers with applications and to discuss these in the third hour of the lecture.

The amount of workload is approximately 80 hours in case of active participation.

Literature: the author is preparing a book on this topic. The literature for this course will consist of a number of chapters of this book plus a number of papers from the literature. The material will be distributed during the course.
Prerequisites: For this course only elementary probability theory and elementary knowledge of discrete time (countable) Markov chains is needed.

This page is constructed by B. Planque', date: 28/10/1997