| TDDC82 | Heuristic algorithms for combinatorial optimization problems, 9 ECTS credits. /Heuristic algorithms for combinatorial optimization problems/ |
|||
OBS! |
Only open for students admitted to the Computer Science Master programme |
|||
Prel. scheduled
hours: |
||||
|
Area of Education: Technology Subject area: Computer Science |
||||
| Advancement level
(G1, G2, A): A
|
||||
| Aim: 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: (valid for students admitted to programmes within which the course is offered) Basic knowledge of system design in software or hardware. Algorithms and their complexity. Note: Admission requirements for non-programme students usually also include admission requirements for the programme and threshhold requirements for progression within the programme, or corresponding. |
||||
| Organisation: 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. |
||||
| Course 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. |
||||
| Course 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. |
||||
| Examination: | ||||
| A written report based on project work or case studies |
6 p |
/ |
9 ECTS |
|
| Grades are givens as â?TFailâ?T or â?TPassâ?T. | ||||
Course language is English. Department offering the course: IDA. Director of Studies: Examiner: Zebo Peng Course Syllabus in Swedish |
||||
|
|
 |
|||||
| ||||||