Heuristic Algorithms for Combinatorial Optimization ProblemsFDA157, 2007VT
|
|
Course plan
Lectures
20 h + 20 h seminars
Recommended for
Graduate students in Computer Science and Computer Systems.
The course was last given
2003 HT
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
design automation and software engineering, will be discussed.
Prerequisites
Basic knowledge of system design in software or hardware.
Algorithms and their complexity.
Contents
· Introduction to combinatorial optimization problems.
· Basic principles of heuristic techniques.
· Simulated annealing.
· Tabu search.
· Genetic algorithms.
· Lagrangean relaxation.
· Application of heuristic techniques.
· Case studies or project work.
Organization
The course consists of two parts. Part I 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. This part will give 3 credit points.
The second part will be a set of seminars dealing with the
application of the heuristics in practical design problems, which
will give also 3 credit points.
Literature
1. C. R. Reeves, "Modern Heuristic Techniques for Combinatorial
Problems", Blackwell Scientific Publications, 1993
2. P. Mazumder, E. M. Rudnick, "Genetic Algorithms for VLSI Design,
Layout & Test Automation," Prentice Hall, 1999
3. Selected research articles in different application areas.
Lecturers
Petru Eles and Zebo Peng
Examiner
Zebo Peng
Examination
For each part of the course, a written report based on project work
or case studies is required.
Credit
6 points. Part I: 3; Part II: 3 (It is also possible to participate
in only one part of the course, and get 3 points).
Organized by
ESLAB
Comments
Page responsible: Director of Graduate Studies