T-79.250 Combinatorial Models and Stochastic Algorithms (4 cr)

Spring 2003

Stochastic methods such as MCMC sampling, simulated annealing and genetic algorithms are currently at the forefront of approximate techniques for dealing with computationally demanding problems. This course presents these algorithms and their underlying theory, with the goal of learning to apply the methods to novel problems and achieving a broad understanding of their common foundations.

[Current] [General] [Lectures] [Tutorials] [Exams] [Literature]

Current

• A nicely typeset version of the lecture notes (ps.gz) has kindly been made available by Vesa Hölttä. The notes have not yet been proofread, but are surely already in this form much preferable to the lecturer's handwritten scribbles. Be reminded that you may also bring this text with you to the exam.
• New exam date: Wed 14 May 9-12.
• Bring a short description of your programming assignment (what model do you intend to simulate/optimise & using which method) with you to the lecture on Wed 9 April, or if you cannot attend then, send the description by e-mail to the lecturer.
• No lecture on Fri 11 April due to lecturer's business trip.
• Some really cool applets illustrating the Propp-Wilson algorithm from Jim Propp's home page.
• Master copy of lecture notes available in the rack next to the Theory Lab office (TB336).

General

• Lectures: Pekka Orponen 22 Jan - 25 Apr, Wed 14-16 room TA328, Fri 12-14 room TB353.
• Tutorials: Emil Falck, Fri 10-12, room TB353.
• Examination: Wed 14 May 9-12, T1.
• Grading: Tutorials, programming assignment and/or examination.
• Registration by TOPI or by attending the first two lectures
• Prerequisites: First two years' mathematics courses including introductory probability theory (e.g. Mat-2.090), and programming skills (e.g. T-106.230). Familiarity with stochastic processes (Mat-2.111), discrete mathematics (Mat-1.128), algorithm design (T-106.410) and computational complexity theory (T-79.240) an asset.
• Grading: Exam 30 points, tutorial assignments 10 points, programming assignment (to be handed out later) 20 points, total 60 points.
• Course brochure (in Finnish): ps/pdf

Lecture schedule (tentative)

• Part I: Combinatorial Models
  Spin glasses, NK landscapes, random formulas
  Random graphs
  Fitness landscapes
  
• Part II: Stochastic Algorithms
  Markov chains and random walks
  Monte Carlo simulation and MCMC sampling
  MCMC-based approximation algorithms
  Simulated annealing
  Genetic algorithms
  Other local search techniques: tabu search, record-to-record travel
• Part III: Special Topics
  Structure of fitness landscapes
  Combinatorial phase transitions
  Current issues

Lecture notes

Tutorial problems

• Problem Set 1 (ps/ pdf)
• Problem Set 2 (ps/ pdf)
• Problem Set 3 (ps/ pdf)
• Problem Set 4 (ps/ pdf)
• Problem Set 5 (ps/ pdf)
• Problem Set 6 (ps/ pdf)
• Problem Set 7 (ps/ pdf)
• Problem Set 8 (ps/ pdf)
• Problem Set 9 (ps/ pdf)
• Problem Set 10 (ps/ pdf)
• Problem Set 11 (ps/ pdf)
• Problem Set 12 (ps/ pdf)

Exams

• 14 May 2003 (pdf)

Literature

• General
  E. Aarts, J. Lenstra (Eds.), Local Search in Combinatorial Optimization. John Wiley & Sons, New York, NY, 1997.
  Y. Bar-Yam, Dynamics of Complex Systems. Addison-Wesley, Reading MA, 1997. (Available online at http://www.necsi.org/publications/dcs/.)
  M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed (Eds.), Probabilistic Methods for Algorithmic Discrete Mathematics. Springer-Verlag, Berlin, 1998.
  D. L. Stein (Ed.), Lectures in the Sciences of Complexity. Addison-Wesley, Reading MA, 1989.
  
• Statistical mechanics, Ising model, spin glasses
  R. Kindermann, J. L. Snell, Markov Random Fields and Their Applications. American Mathematical Society, Providence RI, 1980.
  M. Mezard, G. Parisi, M. A. Virasoro (Eds.), Spin Glass Theory and Beyond. World Scientific, Singapore, 1987.
  L. E. Reichl, A Modern Course in Statistical Physics, 2nd Ed.. J. Wiley & Sons, New York NY, 1998.
  C. F. Stevens, The Six Core Theories of Modern Physics. The MIT Press, Cambridge MA, 1995.
• Graph theory, random graphs, small world networks
  B. Bollobás, Modern Graph Theory. Springer-Verlag, New York NY, 1998.
  B. Bollobás, Random Graphs, 2nd Ed. Cambridge University Press, 2001.
  R. Diestel, Graph Theory, 2nd Ed. Springer-Verlag, New York NY, 2000. (Available online at http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/.)
  S. Janson, T. Luczak, A. Rucinski, Random Graphs. J. Wiley & Sons, New York NY, 2000.
  M. Karonski, "Random graphs." Handbook of Combinatorics, Vol. 1 (R. L. Graham, M. Grötschel, L. Lovász, eds.), pp. 351-380. Elsevier, Amsterdam, 1995.
  D. J. Watts, Small Worlds: The Dynamics of Networks Between Order and Randomness. Princeton University Press, Princeton NJ, 1999.
• Markov chains, rapid mixing
  E. Behrends, Introduction to Markov Chains, with Special Emphasis on Rapid Mixing. Vieweg & Sohn, Braunschweig/Wiesbaden, 2000.
  P. Brémaud, Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer-Verlag, New York NY, 1999.
  O. Häggström, Finite Markov Chains and Algorithmic Applications. Cambridge University Press, 2002.
  D. G. Luenberger, Introduction to Dynamic Systems: Theory, Models, and Applications. J. Wiley & Sons, New York NY, 1979.
• MCMC approximation algorithms
  M. Jerrum, A. Sinclair, "The Markov chain Monte Carlo method: An approach to approximate counting and integration." Approximation Algorithms for NP-Hard Problems (D. Hochbaum, ed.), pp. 482-520. PWS Publishing, Boston MA, 1997.
  A. Sinclair, Algorithms for Random Generation & Counting: A Markov Chain Approach. Birkhäuser, Boston MA, 1993.
• Simulated annealing, genetic algorithms
  E. Aarts, J. Korst, Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. J. Wiley & Sons, Chichester, 1989.
  L. Kallel, B. Naudts, A. Rogers (Eds.), Theoretical Aspects of Evolutionary Computing. Springer-Verlag, Berlin, 2001.
  C. R. Reeves, J. E. Rowe, Genetic Algorithms - Principles and Perspectives. Kluwer Academic, Boston MA, 2003.
  P. Salamon, P. Sibani, R. Frost, Facts, Conjectures, and Improvements for Simulated Annealing. Soc. Industrial & Applied Mathematics, Philadelphia PA, 2002.
  M. D. Vose, The Simple Genetic Algorithm. The MIT Press, Cambridge MA, 1999.
• Combinatorial phase transitions, fitness landscapes and related topics
  O. C. Martin, R. Monasson, R. Zecchina, "Statistical mechanics methods and phase transitions in optimization problems." Theoretical Computer Science 265 (2001), 3-67.
  C. M. Reidys, P. F. Stadler, "Combinatorial landscapes." SIAM Review 44 (2002), 3-54.
  Seminar T-79.300 Postgraduate Course in Theoretical Computer Science (Spring 2002)

  ---

  [TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]

  ---

  Latest update: 23 December 2004. Pekka Orponen.