Heuristic Algorithms for Combinatorial Optimization ProblemsFDA157, 2003HT
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.
· Introduction to combinatorial optimization problems.
· Basic principles of heuristic techniques.
· Simulated annealing.
· Tabu search.
· Genetic algorithms
· Application of heuristic techniques in design automation.
The course is given in an intensive format ("crash course") at Linköping
The course consists of two parts. Part I will introduce the area and the basic concepts of heuristics. It will then presents mainly 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 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. A. H. Gerez, "Algorithms for VLSI Design Automation," John Wiley & Sons, 1999.
Zebo Peng and Petru Eles
For each part of the course, a written report based on project work is required.
6 points (Part I: 3; Part II: 3)
The course is given at IDA.
Page responsible: Director of Graduate Studies
Last updated: 2012-05-03