helmut g. katzgraber
  Optimization Problems and Algorithms
  in Physics

general information

The class will be held at ETH Hoenggerberg, HPP H7 every Tuesday from 13:45 to 15:30h followed by one hour exercises (6 KP). Date and time of the exercises is negotiable. Note that the class will be held in English. For further information see the ETH Vorlesungsverzeichnis.

General information about the class will be posted in this section. Be sure to check back periodically as most announcements will be made here.

  • 07/08: The lecture starts Tuesday October 02, 2007.

  • 08/08: Exercise sections will be held by Brigitte Surer.

  • 16/10: Visit of the ETH cluster facilities. Leave right after class at 15:30h to the Zentrum.

  • 15/10: There will be no lecture on October 23, 2007.



The lecture will cover optimization problems in physical systems with an emphasis on optimization algorithms. Some combinatorial as well as typical optimization problems (such as k-SAT, traveling salesman, number partitioning, ...) will also be discussed. Furthermore, some topics such as complexity theory as well as finite-size scaling will be reviewed. Most of the examples will be based on physics spin models (e.g., Ising model).

Lecture Notes

If you would like to access the lectures notes (pdf) please send me an email to email and you might receive the username and password. Students can find the username and password on the first handout.

Recommended books

  • Optimization Algorithms in Physics, A. K. Hartmann and H. Rieger (Wiley-VCH).

  • New Optimization Algorithms in Physics, A. K. Hartmann and H. Rieger (Wiley-VCH).

  • Algorithms and Computations, W. Krauth (Oxford University Press).

  • Phase Transitions in Combinatorial Optimization Problems, A. K. Hartmann and M. Weigt (Wiley-VCH).

  • Quantum Annealing and Related Optimization Methods, A. Das and B. K. Chakrabarti (Springer).


The exercise sections will be held by Brigitte Surer every Tuesday at 15:45 - 16:30 in HPP H7. Feel free to contact me or her if you have any questions about the homework sets. You will have one week to solve the problems. To obtain the testat for the exercises you will need to solve at least 70% of the problems in a satisfactory manner You will have to hand in your source code if the homework requires programming. Please try to write the programs in C/C++.

Homework Sets & Solutions

HW 1 Monte Carlo methods due 16/10/2007 Solution
HW 2 Simulated annealing and the Cologne server due 30/10/2007 Solution
HW 3 Genetic algorithms due 06/11/2007 Solution
HW 4 Hysteretic optimization due 13/11/2007 Solution
HW 5 Directed polymers due 27/11/2007 Solution
HW 6 Max flow mapping due 04/12/2007 Solution
HW 7 Max flow algorithm implementation due 11/12/2007 Solution
HW 8 Probing tails of your favorite problem due 18/12/2007 Solution