Heuristic Algorithms for Combinatorial Optimization Problems
Goals:
To give an introduction to the combinatorial optimization problems and
heuristic techniques which can be used to solve them. A set of
heuristic algorithms, including simulated annealing, tabu search, and
genetic algorithms, together with their practical applications to
system design and software engineering, will be discussed.
Contents:
· Introduction to combinatorial optimization problems.
· Basic principles of heuristic techniques.
· Simulated annealing.
· Tabu search.
· Genetic algorithms.
· Application of heuristic techniques.
· Case studies or project work.
Organization:
The course consists of two parts, the lecture part and the project
part. The lecture part will introduce the area and the basic concepts of
heuristics. It will then presents several meta-heuristic techniques
including simulated annealing, tabu search, and genetic
algorithms. In the project part, a student will implement one
or two heuristic algorithms for a practical problem. The implementation
and the experimental results will be documented in a term paper.
Teachers:
Petru Eles and Zebo Peng
Examiner:
Zebo Peng
Lecture Notes and Articles
Lecture notes:
- Introduction to combinatorial optimization and heuristics.
- Simulated annealing.
- Tabu search: basic principle and algorithm.
- Application of Tabu search.
- Stochastic combinatorial optimization.
- Genetic algorithms.
Reference Articles:
- A. Colorni et. al., Heuristics from nature for hard combinatorial optimization problems.
- S. Kirkpatrick et. al., Optimization by simulated annealing.
- F. Glover, Tabu Search: A Tutorial.
- F. Glover, A user's guide to tabu search
- M. Malek et. al., Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem
- M. Srinivas and L. M. Patnaik, Genetic algorithms: a survey
- J. L. R. Filho et. al., Srinivas and L. M. Patnaik, Genetic-algorithm programming environments
Last modified: Monday November 08, 2010