Solving Combinatorial Problems using Stochastic Local Search (Spring 2007)

Course outline (subject to adjustments)

Part 1: Foundations and Basics

Module 1: Introduction

• Combinatorial Problems (SAT, TSP, etc.)
• Computational Complexity (P vs. NP, etc.)
• Search Paradigms (systematic vs. local search, etc.)
• Stochastic Local Search (definition, general issues, etc.)

Module 2: "Simple" SLS Algorithms

• Iterative Improvement and Variants
• Simulated Annealing
• Tabu Search
• Dynamic Local Search, Guided Local Search

Module 3: Hybrid SLS Algorithms

• Iterated Local Search
• Variable Neighbourhood Search
• Adaptive Iterated Construction Search

Module 4: Population-based SLS Algorithms

• Ant Colony Optimisation
• Evolutionary Computation (Genetic Algorithms, etc.)

Module 5: Empirical Analysis of Stochastic Search Algorithms

• Las Vegas Algorithms (LVAs)
• Run-time Distributions (RTDs)
• RTD-based Analysis of LVA Behaviour

Part 2: Applications and Advanced Topics

Module 6: SLS algorithms for SAT

Module 7: Search Space Analysis

Module 8: Automated Parameter Optimisation

• (brief introduction and selected research result)

Module 9: SLS for Continuous Optimisation Problems

• (a brief overview)