Heuristic Algorithms for Combinatorial Optimization ProblemsFDA157, 2007VT
20 h + 20 h seminars
Graduate students in Computer Science and Computer Systems.
The course was last given
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.
Basic knowledge of system design in software or hardware.
Algorithms and their complexity.
· 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.
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.
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.
Petru Eles and Zebo Peng
For each part of the course, a written report based on project work
or case studies is required.
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).
Page responsible: Director of Graduate Studies
Last updated: 2012-05-03