CPSC 532D - Stochastic Search Algorithms (Spring 2003)

Latest News:

03/04/24 - Mini-Workshop tomorrow, 9:00-17:00 in FSC 1613.

Instructor: Holger Hoos

[Current official information on graduate courses in 2002/03 Term 2 can be found here]

Why Take This Course?

If you always wondered how hard problems from many domains, including AI, Bioinformatics, and Electronic Commerce, are solved in practice, this course will introduce you thoroughly to at least one very popular and successful general approach.

And if you want to learn (more) about one of the hottest topics in AI, Operations Research, and Empirical Algorithmics research, you've found the right place!

The course will introduce many basic stochastic search methods and their most relevant variants, point out and discuss connections and differences between them, tell you implementation tricks and details which are hardly ever explained but essential to obtain good performance, and show you how these algorithms can be applied to many hard combinatorial problems from various domains, including AI, Operations Research, and Bioinformatics! The course will introduce you to the foundations of stochastic search and many of its very successful applications. It will provide you with a good balance of abstract and theoretical contents as well as with hands-on-experience (including implementation).

To date, designing stochastic search algorithms and applying them successfully to hard combinatorial problems is as much an art or a craft as it is a science. I will introduce you to both aspects of this exciting research area, and share many of my secrets with you ;-) There is no single book that offers the material covered by course (I am currently writing it, and will share drafts with you), and in many ways we will go beyond what you can easily find in the research literature.

Interested? Check out the in information in the following sections ...

Course Description & Prequisites

Preliminary Course Outline

04/25, 9:00-17:30: project presentations (Mini-Workshop), FSC 1613.

Preparation and Submission of Final Reports

Preparation and Format of Workshop Talks

Class 1, 03/01/09, Thu:

Course Overview, Formalities (all information can be found on this webpage)

Class 2, 03/01/14, Tue:

Module 1. Discussion facilitator: Holger Hoos.
Assigned reading:

• Chapter 1 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.5-34);
• Selman, B.; Levesque, H.; Mitchell, D. A New Method for Solving Hard Satisfiability Problems. Proceedings AAAI-92.

Class 3, 03/01/17, Fri:

Module 1 (continued). Discussion facilitator: Holger Hoos.
Assigned reading:

• Chapter 1 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.35-47);

Class 4, 03/01/21, Tue:

Module 2 (Iterative Improvement, Simulated Annealing). Discussion facilitators: Mirela / Diana.
Assigned reading:

• Chapter 2 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.51-68);
• P. Hansen and B. Jaumard. Algorithms for the maximum satisability problem. Computing, 44:279-303, 1990.

Class 5, 03/01/24, Fri:

Module 2 (Tabu Search, Dynamic Local Search). Discussion facilitator: Ladan.
Assigned reading:

• Chapter 2 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.68-75);

Class 6, 03/01/28, Tue:

Module 3 (Iterated Local Search, GRASP). Discussion facilitators: Markus / Kelvin.
Assigned reading:

• Chapter 2 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.75-84);
• Martin O.; Otto, S.W.; Felten, E.W. Large-step markov chains for the traveling salesman problem. Complex Systems, 5(3):299--326, June 1991.
  (Please read and prepare the entire paper.)

Class 7, 03/01/31, Fri:

Module 3/4 (AICS, ACO). Discussion facilitator: Bobby.
Assigned reading:

• Chapter 2 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.84-92);

Class 8, 03/02/04, Tue:

Module 4 (ACO, EA). Discussion facilitators: Baharak / Sanja.
Assigned reading:

• Chapter 2 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.92-104);
• Di Caro, G.; Dorigo, M. AntNet: Distributed Stigmergetic Control for Communications Networks. Journal of Artificial Intelligence Research, 9:317-365, 1998.
  (Please read and prepare Sections 1-4 and 8-10.)

Note: There is no class on 03/02/07, Fri.

Class 9, 03/02/11, Tue:

Module 5 (Generalised Local Search Machines). Discussion facilitators: Max / Iryna.
Assigned reading:

• Chapter 3 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.105-136).
• (No paper this time.)

Class 10, 03/02/14, Fri:

Module 6 (Empirical Analysis). Discussion facilitator: Jacek.
Assigned reading:

• Chapter 4 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.139-162);

Note: There are no classes during Reading Week.

Class 11, 03/02/25, Tue:

Module 6 (Empirical Analysis). Discussion facilitators: Fred / James S.
Assigned reading:

• Chapter 4 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.162-194).
• Schuurmans, D.; Southey, F.; Holte, R.C. The exponentiated subgradient algorithm for heuristic boolean programming. Proceedings IJCAI-01, pp. 334-341, 2001.
  (Focus on Sections 3 and 4.)

Class 12, 03/02/28, Fri:

Module 7 (Search Space Analysis). Lecture by HH (no discussion / reading).

Class 13, 03/03/04, Tue:

Project presentations (10+5min per group). No reading.

Class 14, 03/03/07, Fri:

Module 8 (SAT). Discussion facilitator: Jonathan.
Assigned reading:

• Chapter 6 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.203-229 = beginning - Section 6.3);

Class 15, 03/03/11, Tue:

Module 8 (SAT continued, CSP). Discussion facilitators: James C / Mirela.
Assigned reading:

• Chapter 6 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.229-259 = Section 6.4 - end);
• Hirsch, E; Kojevnikov, A. UnitWalk: A new SAT solver that uses local search guided by unit clause elimination. Annals of Mathematics and Artificial Intelligence. (To appear).
  (We won't cover Section 4.3; you don't have to prepare Section 5 in detail)

Class 16, 03/03/14, Fri:

Module 9 (MaxSAT). Discussion facilitator: Bobby.
Assigned reading:

• Chapter 7 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.261-283 = beginning - Section 7.2);

Class 17, 03/03/18, Tue:

Module 9 (MaxCSP) / Module 10 (TSP). Discussion facilitators: James S / Jacek.
Assigned reading:

• Chapter 7 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.283-296);
• Chapter 8 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.299-326).

[Note: Since we used the second half of this class to discuss organisational issues (final project reports, workshop), we'll start Module 10 on Friday.]

Class 18, 03/03/21, Fri:

Module 10 (TSP). Discussion facilitator: Jacek.
Assigned reading:

• Chapter 8 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.299-326);

Additional reading (optional, not covered in class):

• Stützle, T.; Hoos, H. Analyzing the Run-time Behaviour of Iterated Local Search for the TSP. Proc. of the III Metaheuristics Conference, pp.449-453, 1999.

Class 19, 03/03/25, Tue:

Module 10 (continued), Module 11 (Scheduling - Basics). Discussion facilitators: Diana, Iryna.
Assigned reading:

• Chapter 8 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.326-357).
• Anderson, E.J.; Glass, C.A.; Potts, C.N. Machine Scheduling. Chapter 11 of E.Aarts and J.K.Lenstra (eds): Local Search in Combinatorial Optimisation. Wiley, 1997.
  (For this class, please prepare Sections 1-3.)

Class 20, 03/03/28, Fri:

Module 11 (Scheduling - Neighbourhoods, Single-Machine Problems). Discussion facilitator: James C.
Assigned reading:

• Anderson, E.J.; Glass, C.A.; Potts, C.N. Machine Scheduling. Chapter 11 of E.Aarts and J.K.Lenstra (eds): Local Search in Combinatorial Optimisation. Wiley, 1997.
  (For this class, please prepare Sections 4+5.)

Note: Class cancelled on 03/04/01, Tue (additional class will be held on 03/04/15, Tue).

Class 21, 03/04/04, Fri:

Module 11 (Scheduling - Parallel-Machine and Multistage Problems) Discussion facilitator: Baharak.
Assigned reading:

• Anderson, E.J.; Glass, C.A.; Potts, C.N. Machine Scheduling. Chapter 11 of E.Aarts and J.K.Lenstra (eds): Local Search in Combinatorial Optimisation. Wiley, 1997.
  (For this class, please prepare Sections 6-9.)

Class 22, 03/04/08, Tue:

Module 12 (QAP, Combinatorial Auctions) Discussion facilitator: Fred, Kelvin.
Assigned reading:

• Chapter 10, Section 10.2 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.371-384).
• Chapter 10, Section 10.4 from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (pp.396-405).

Class 23, 03/04/15, Tue:

Module 13 (Randomised Systematic Search). Lecture by HH.
Suggested reading:

• Gomes, C.P.; Selman, B.; Kautz, H. Boosting Combinatorial Search Through Randomization. Proc. AAAI-98, pp.431-437, 1998.

• Chapters from Hoos, H; Stützle, T. Stochastic Local Search - Foundations and Applications (to appear, Morgan Kaufmann Publishers, USA)
• Slides from Module 7 (Search Space Analysis)
• Slides from Module 13 (Randomised Tree Search)

Papers:

• Selman, B.; Levesque, H.; Mitchell, D. A New Method for Solving Hard Satisfiability Problems. Proceedings AAAI-92.
• Hansen, P.; Jaumard, B. Algorithms for the maximum satisability problem. Computing, 44:279-303, 1990
• Martin O.; Otto, S.W.; Felten, E.W. Large-step markov chains for the traveling salesman problem. Complex Systems, 5(3):299--326, June 1991.
• Di Caro, G.; Dorigo, M. AntNet: Distributed Stigmergetic Control for Communications Networks. Journal of Artificial Intelligence Research, 9:317-365, 1998.
• Schuurmans, D.; Southey, F.; Holte, R.C. The exponentiated subgradient algorithm for heuristic boolean programming. Proceedings IJCAI-01, pp. 334-341, 2001.
• Hirsch, E; Kojevnikov, A. UnitWalk: A new SAT solver that uses local search guided by unit clause elimination. Annals of Mathematics and Artificial Intelligence. (To appear).
• Stützle, T.; Hoos, H. Analyzing the Run-time Behaviour of Iterated Local Search for the TSP. Proc. of the III Metaheuristics Conference, pp.449-453, 1999.
• Gomes, C.P.; Selman, B.; Kautz, H. Boosting Combinatorial Search Through Randomization. Proc.~AAAI-98, pp.431-437, 1998.
• Holte, R.C. Combinatorial Auctions, Knapsack Problems, and Hill-climbing Search. Proc. AI'2001, Lecture Notes in Artificial Intelligence 2056, pp. 57-66, Springer Verlag, 2001.

Links / Webpages:

• Guided Local Search (GLS): http://cswww.essex.ac.uk/CSP/gls.html
• The Reactive Search (RS) Home Page: http://rtm.science.unitn.it/~battiti/reactive.html (reactive tabu search, etc.)
• Ant Colony Optimization Home Page: http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html
• The Genetic Algorithms Archive: http://www.aic.nrl.avy.mil/galist
• Memetic Algorithms' Home Page: http://www.densis.fee.unicamp.br/~moscato/memetic_home.html (Genetic Local Search)
• (more coming soon)