Hide menu

Heuristic Algorithms for Combinatorial Optimization Problems

FDA157, 2007VT

Status Archive
School National Graduate School in Computer Science (CUGS)
Division ESLAB
Owner Zebo Peng
Homepage http://www.ida.liu.se/~zebpe/heuristic/

  Log in  




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: Webmaster
Last updated: 2012-05-03