Solving Combinatorial Problems using Stochastic Local Search (Spring 2005)

Preliminary 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

Module 6: SAT and Constraint Satisfaction

Module 7: Combinatorial Problems in Bioinformatics

• Phylogenetic tree inference
• Protein structure prediction
• RNA Secondary structure design
• DNA Code Design