186.112 Heuristic Optimization Techniques
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2021W, VU, 2.0h, 3.0EC

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung
  • Format der Abhaltung: Distance Learning

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage verschiedene heuristische Algorithmen zur Lösung schwieriger Optimierungsprobleme zu verstehen, anzuwenden und für neue Probleme zu adaptieren.

Inhalt der Lehrveranstaltung

This lecture deals with heuristic methods to solve optimization problems. The presented approaches are especially suitable for problems arising in practice. On the one hand such problems are often too complex to be solved in an exact way because of the increasing amount of computation time needed by conventional exact techniques. On the other hand it is often sufficient or even required to come up with a good solution in reasonable time.

In this course we primarily focus on discrete appilcation problems and application in areas such as transport optimization, scheduling, network design, cutting and packing.

The methods considered in the course include:

  • Construction Heuristics
  • Local Search
  • Simulated Annealing
  • Tabu-Search
  • Guided Local Search
  • Variable Neighborhood Search
  • Very Large Neighborhood Search
  • Greedy Randomized Adaptive Search Procedure
  • Genetic Algorithms
  • Evolutionary Strategies
  • Ant Colony Optimization
  • Hybridization of different approaches, parallelization
  • Analysis and Tuning of metaheuristics

Beside the theoretical basics this lecture focuses on practical applications and the connection of metaheuristics with problem-specific heuristics as well as some examples of suitable combinations with exact methods.

Also we will discuss how to properly tune heuristics and to evaluate and compare them by means of experiments and appropriate statistical methods.

Methoden

Introduction and explanation of general methods, discussion of examples, theoretical exercises, hands-on programming exercises, presentation and discussion of solutions.

Prüfungsmodus

Prüfungsimmanent

Weitere Informationen

ECTS-Breakdown

20h Lectures
33h Exercises and recap of the lecture contents
20h Programming exercises
  2h Exercise interviews / Examination
----
75h

Hotline for any questions concerning this course: heuopt (at) ac.tuwien.ac.at

Vortragende Personen

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Di.11:00 - 13:0005.10.2021 - 25.01.2022 Zoom (LIVE)Vorlesung
Mi.11:00 - 13:0027.10.2021 - 03.11.2021 Zoom (LIVE)Vorlesung
Heuristic Optimization Techniques - Einzeltermine
TagDatumZeitOrtBeschreibung
Di.05.10.202111:00 - 13:00 ZoomVorlesung
Di.12.10.202111:00 - 13:00 ZoomVorlesung
Di.19.10.202111:00 - 13:00 ZoomVorlesung
Mi.27.10.202111:00 - 13:00 ZoomVorlesung
Mi.03.11.202111:00 - 13:00 ZoomVorlesung
Di.09.11.202111:00 - 13:00 ZoomVorlesung
Di.16.11.202111:00 - 13:00 ZoomVorlesung
Di.23.11.202111:00 - 13:00 ZoomVorlesung
Di.30.11.202111:00 - 13:00 ZoomVorlesung
Di.07.12.202111:00 - 13:00 ZoomVorlesung
Di.14.12.202111:00 - 13:00 ZoomVorlesung
Di.11.01.202211:00 - 13:00 ZoomVorlesung
Di.18.01.202211:00 - 13:00 ZoomVorlesung
Di.25.01.202211:00 - 13:00 ZoomVorlesung

Leistungsnachweis

Assignments / Oral Exam / Grading

During the course five assignments are given out:

  • Three pen & paper exercise sheets with theoretical tasks and
  • two programming exercises where you solve an optimization problem by implementing optimization algorithms.

The pen & paper exercises should be solved alone while the programming exercises are meant to be solved in teams of two students. For all five assignments concise reports should be prepared and handed in.

The five assignments are discussed in three online interview sessions:

  • First interview session in the week beginning with 8th of November: pen & paper sheet 1
  • Second interview session in the week beginning with 6th of December: pen & paper sheet 2 + programming exercise 1
  • Third interview session in the week beginning with 17th of January: pen & paper sheet 3 + programming exercise 2

In each of the interview sessions, the assignments are discussed - based on the uploaded reports. Additionally, in the course of the discussion of the pen & paper sheets, questions about the corresponding course topics are asked. Each of the five assignments contributes 20% to the final grade and each of them has to be positive to successfully complete the lecture.

LVA-Anmeldung

Von Bis Abmeldung bis
14.09.2021 00:00 19.10.2021 23:55 19.10.2021 23:55

Curricula

Literatur

  • F. Glover, G. A. Kochenberger: Handbook of Metaheuristics, Kluwer Academic Publishers, 2003
    (comprehensive, recent standard work on metaheuristics)
  • M. Gendreau, J.-Y. Potvin: Handbook of Metaheuristics, 2nd edition, Springer, 2010
    (describes various methods in addition to the first version)
  • E. Talbi: Metaheuristics: From Design to Implementation, J. Wiley and Sons, 2009
    (new and detailed work about metaheuristics)

Vorkenntnisse

Basic knowledge in algorithms and data structures, programming skills

Vorausgehende Lehrveranstaltungen

Begleitende Lehrveranstaltungen

Vertiefende Lehrveranstaltungen

Weitere Informationen

Sprache

Englisch