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:
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:
|
Literature: |
|
Prerequisites: | Elementary knowledge of probability theory (for the parts a and b); elementary knowledge of linear programming (for part b). |
Examination: | Take home problems. |
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. |
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:
|
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. |
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:
|
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. |