Metaheuristics for combinatorial optimization ( forår 2008 - 10 ECTS )
Rammer for udbud
-
Uddannelsessprog:
(se under Undervisnings- og arbejdsform)
-
Niveau:
Advanced course.
-
Semester/kvarter:
3rd and 4th quarter (Spring 2008).
-
Timer per uge:
4
-
Deltagerbegrænsning:
-
Undervisningssted:
Århus
-
Hovedområde:
Det Naturvidenskabelige Fakultet
-
Udbud ID:
7961
Formål
An important major branch of Operations Research is integer programming
and combinatorial optimization. Combinatorial optimization is concerned
with resolving decision problems that are characterized by a finite solution
space, especially optimization problems where the objective is to find an optimal subset, an optimal partitioning of a ground set, an optimal sequence or
an optimal assignment. The range of applications of such types of problems
is immense. Combinatorial optimization techniques have proven to be successful in many fields, e.g, staff resource planning, logistics, transportation,
production planning, supply chain management, and many many more.
Most combinatorial optimization problems are however NP-hard and very
difficult to solve to optimality. For practical problem solving it is thus often required to resort to heuristics. Especially meta-heuristic solution approaches, which try to coordinate sub-ordinate heuristics, were shown to be
promising methods. This course tries to provide an overview on the most
important techniques in this area that can be applied for practical problem
solving.
Indhold
Term, purpose and application fields of heuristics; basics of complexity theory; greedy methods; local search; simulated annealing and variants; guided
local search; variable neighbourhood search; variable depth search and very
large-scale neighbourhoods; greedy randomized adaptive search; ant colonies;
genetic and evolutionary algorithms; scatter search and path relinking; tabu
search.
Læringsmål
The students should after finishing the course be able to:
(a) apply major meta-heuristic solution techniques to a given combinatorial optimization problem;
(b) compare the pros and cons of alternative meta-heuristic solution approaches if applied to a specific problem;
(c) evaluate the potential benefit from using a specific meta-heuristic solution approach for a given combinatorial optimization problem with respect to solution quality, computational effort, implementational effort, generalizability of the method.
Faglige forudsætninger
Mathematical Programming.
Underviser
Andreas Klose.
Undervisnings- og arbejdsform
2 x 2 hours of lecture per week.
English.
Litteratur
Aarts EH, Lenstra JK (1997) Local Search in Combinatorial Optimization.
Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, New York.
Glover F, Kochenberger GA (2003) Handbook of Metaheuristics. Kluwer International Series in Operations Research and Management Science, Kluwer, London.
Reeves CB (1993) Modern Heuristic Techniques for Combinatorial Problems.
Advanced Topics in Computer Science, Blackwell, Cambridge MA and Oxford UK.
Eksamensterminer
Examination: 4th quarter.
Re-examination: Contact the teacher.
Udbyder
Departmenmt of Mathematical Sciences.
Tilmelding til undervisning
Information Office, Department of Mathematical Sciences.
Bedømmelse
-
Hj.opg., bedømt efter 7-skala med ekstern censur
5 xxxxx
After the 3rd and 4th quarter, an assignment is given. Workload:
Approximately 20 hours for each of the two assignments. External examination.
One mark after the Danish 7-grades scale is given based on the written
assignments.
