NATCOR

DATE: 12th - 16th April 2010

LOCATION: University of Nottingham

Heuristics and Approximation Algorithms are Operational Research tools that provide solutions to real-world problems across a wide range of application areas despite their inherent complexity and uncertainty. Heuristics are ‘rules of thumb’ and other clever algorithms that despite being relatively simple to implement can provide good (though not necessarily optimal) and fast solutions to otherwise intractable problems. This course features the main techniques and also practical sessions, so that participants leave with the capabilities to start implementing their own heuristics.

Main contributors: Prof Sanja Petrovic (University of Nottingham, UK), Professor Edmund Burke (University of Nottingham, UK), Professort Graham Kendall (University of Nottingham, UK), Professor Erwin Pesch (University of Siegen, Germany), Professor Chris Potts (University of Southampton, UK), Dr Greet Vanden Berghe (KaHo Sint-Lieven, Belgium).

Every participant will get a book:

Search Methodologies - Introductory Tutorials in Optimization and Decision Support Techniques”, eds. E. Burke and G. Kendall, Kluwer, 2005.

PRE-REQUISITES

TBA soon

AIM

On completion of the block, the student should have a working knowledge of the theory, applications and implementation issues of the main heuristic approaches to combinatorial optimization and their practical application.

LEARNING OUTCOMES

Knowledge and Understanding

On completion of the block, the student will be expected to

• understand the basic theory underlying the main heuristic approaches to optimization, such as local search, genetic algorithms and their variants;
• be aware of the strengths and limitations of each approach.

Intellectual Skills

On completion of the block, the student is expected to give evidence of the following intellectual skills

• be able to critically evaluate the quality of different heuristic optimization approaches;
• be capable of applying their knowledge and understanding to develop an appropriate heuristic for a new problem.

Practical Skills

On completion of the block, the student is expected to have developed the following subject-specific practical skills

• be familiar with at least one software tool in the area;
• be able to apply an appropriate range of optimization heuristics to a given problem.

CONTENTS

1. Heuristics

   What are heuristics? Classification of heuristic search, When to use heuristic search? Local search, Design of local search algorithms (representation of solutions, neighbourhood, search process, escaping from local optima, Multistart Local Search, GRASP, Variable Neighbourhood Search), Constraint handling, Parameter tuning, Analysis of heuristic search performance, Complexity theory Meta-Heuristic approaches

2. Simulated Annealing

   Basic concepts, Algorithm, Practical considerations (initial temperature, equilibrium state, cooling schedule, stopping condition), Simulated Annealing inspired algorithms (Threshold Accepting, Great Deluge Algorithm)

3. Tabu Search

   Basic concepts, Algorithm, Memories (short-memory, intermediate memory, long term memory), Diversification techniques, Practical considerations

4. Evolutionary Computation

   Basic concepts, Components of Evolutionary Computation, Classification of Evolutionary Computation algorithms, Genetic Algorithm, Practical considerations

5. Approximation Algorithms
   

6. Multiobjective Evolutionary Algorithms

   Basic concepts, Multiobjective applications, Classification, Evolutionary Multiobjective Optimisation (fitness assignment, diversity preserving, elitism), Weighted Sum Approach, VEGA, Procedure for finding the approximation of Pareto set, NSGA-II, Performance evaluation

7. Real-world problems solved by heuristics/meta-heuristics
   

8. Lab session (4 hours)