T-79.4201 Search Problems and Algorithms (4 cr)
The course provides an introduction to the fundamental
concepts, techniques and tools used in dealing with large,
weakly structured combinatorial search spaces. The topics
covered include: search spaces and search methods; backtracking,
local and heuristic search; representing and solving
search problems using propositional satisfiability,
constraint programming and integer programming techniques.
- [4 May 2006] Please provide feedback on the course via the
course feedback system.
The electronic questionnaires open Fri 5 May and close Mon 22 May.
- [4 May 2006] The course exam is on Monday 15 May, 9--12 a.m.
Check the time and place still from the departmental
exam schedule, and
remember to register for the exam via
TOPI by Wed 10 May.
- [4 Jan 2006] First lecture Thu 19 Jan, room TB353.
19 Jan - 4 May, Thu 10-12, room TB353.
Antti Rusanen, 20 Jan - 5 May, Fri 10-12, room TB353.
- Registration by
- Prerequisites: Basic knowledge of problem representations
and logic (T-79.1001, T-79.3001); facility in programming, data
structures and algorithms (T-106.1220 required, T-106.3100 recommended).
- Requirements: Examination and three programming assignments.
Scheduled for Mon 15 May,
registration by TOPI.
Check exact time and place from the DCSE department
- Grading: Exam max 50 points, programming assignments
max 3*2 = 6 points, tutorials max 4 points, total 60 points.
For the programming assignments, a correctly
functioning program, returned on time with appropriate
work description yields 2 points; each revision round
deducts 1 point from maximum. For the tutorials, credit
is awarded from problem set 3 onwards.
|Week ||Date ||Topic
||Course arrangements and overview of contents.
||Combinatorial search and optimisation problems.
||Search spaces and objective functions.
Complete vs. local search.
||Further local search techniques.
||Constraint satisfaction: formalisms and modelling.
||Constraint satisfaction: algorithms.
||Exam week: no lecture.
Constraint satisfaction: global constraints, local search
Linear and integer programming: formalism.
||Linear and integer programming: modelling and tools.
||Linear and integer programming: algorithms.
||Easter vacation: no lecture.
||Complexity of Search.
||Review and discussion of the course material. Feedback.
The weekly problem sets will be available here as the course progresses.
- Problem set 1: ps, pdf
- Problem set 2: ps, pdf
- Problem set 3: ps, pdf
- Problem set 4: ps, pdf
- Problem set 5: ps, pdf
- Problem set 6: ps, pdf
- Problem set 7: ps, pdf
- Problem set 8: ps, pdf
- Problem set 9: ps, pdf
- Problem set 10: ps, pdf
- Problem set 11: ps, pdf
- Problem set 12: ps, pdf
There will be three small programming assignments using Java.
The details will be announced later, but the aim is to gain
hands-on experience with the techniques learned in the course.
The first set of assignments will be handed out on 10 Feb,
the second on 24 Feb, and the third on 24 Mar.
A functioning program for each of the assignments must
be developed personally by each participant and submitted,
together with a brief description of the solution method used,
by e-mail to the tutorial assistant within three weeks of
the hand-out date.
Descriptions of the programming tasks, input formats, and
the programming environment are available
The course does not follow any existing textbook. Here are
some pointers to general literature covering material
discussed at the lectures in more depth:
- E. Aarts, J. K. Lenstra (Eds.),
Local Search in Combinatorial Optimization.
J. Wiley & Sons, Chichester UK, 1997.
- Krzysztof R. Apt:
Principles of Constraint Programming. Cambrigde University Press, 2003.
- T. Bäck,
Evolutionary Algorithms in Theory and Practice.
Oxford University Press, 1996.
- D. Corne, M. Dorigo, F. Glover (Eds.),
New Ideas in Optimization.
McGraw-Hill. London, 1999.
- H. H. Hoos, T. Stützle,
Stochastic Local Search: Foundations and Applications.
Morgan Kaufmann (Elsevier), Amsterdam, 2005.
- M. Mitchell,
An Introduction to Genetic Algorithms.
The MIT Press, Cambridge MA, 1996.
- C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization:
Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, 1982.
(Reprinted by Dover, Mineola NY, 1998.)
Some links to material related to topics discussed in course:
- Karl Sims' homepage.
(Contains links to the "Evolved Virtual Creatures"
animation and paper.)
Latest update: 06 June 2006.