186.860 Metaheuristics and Hybrid Methods for Combinatorial Optimization
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2017S, VU, 2.5h, 4.0EC, wird geblockt abgehalten

Merkmale

  • Semesterwochenstunden: 2.5
  • ECTS: 4.0
  • Typ: VU Vorlesung mit Übung

Ziele der Lehrveranstaltung

* To learn about the basic ideas behind metaheuristics
* To learn how to apply different metaheuristics to different problems
* To learn the basics of how to model combinatorial problems in terms of integer linear programs (ILPs)
* To learn how to use the general purpose ILP solver CPLEX
* To learn how to make use of CPLEX within metaheuristics
* To learn about the experimental evaluation of metaheuristics

Inhalt der Lehrveranstaltung

Combinatorial optimization problems arise in many aspects of human activities. Examples concern packing and cutting problems, timetabling problems, and vehicle routing problems. Many of these problems are computationally very difficult to be solved to optimality. Therefore, simple heuristics (such as greedy algorithms) and metaheuristics (such as tabu search, evolutionary algorithms, and simulated annealing) have achieved a lot of attention from the optimization community during the last decades. At the same time, the operations research community has invested considerable efforts into both exact techniques (such as algorithms based on branch & bound) and general purpose solvers that implement these state-of-the-art exact techniques. Example are CPLEX and Gurobi. This course will give an introduction to these topics. Attendees should bring a laptop with a recent Linux operating system (e.g. Ubuntu) and the GNU g++ compiler installed.

Weitere Informationen

ECTS Breakdown:

* 20 hours of theory classes (0.8 ECTS)
* 10 hours of reading homework (0.4 ECTS)
* 70 hours work on the practical project: 2.8 ECTS. Approximate division of these 70 hours:
  + Getting familiar with the given problem and the required tasks: 5 hours
  + Design and implementation of the heuristics and metaheuristics: 20 hours
  + Design and implementation of the hybrid metaheuristics: 10 hours
  + Experimental evaluation: 15 hours
  + Writing the report: 20 hours

Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
10:00 - 12:0006.03.2017 - 17.03.2017 Seminarraum Techn. Informatik (Operngasse 9)Metaheuristics and Hybrid Methods for Combinatorial Optimization
Metaheuristics and Hybrid Methods for Combinatorial Optimization - Einzeltermine
TagDatumZeitOrtBeschreibung
Mo.06.03.201710:00 - 12:00 Seminarraum Techn. Informatik (Operngasse 9)Metaheuristics and Hybrid Methods for Combinatorial Optimization
Di.07.03.201710:00 - 12:00 Seminarraum Techn. Informatik (Operngasse 9)Metaheuristics and Hybrid Methods for Combinatorial Optimization
Mi.08.03.201710:00 - 12:00 Seminarraum Techn. Informatik (Operngasse 9)Metaheuristics and Hybrid Methods for Combinatorial Optimization
Do.09.03.201710:00 - 12:00 Seminarraum Techn. Informatik (Operngasse 9)Metaheuristics and Hybrid Methods for Combinatorial Optimization
Fr.10.03.201710:00 - 12:00 Seminarraum Techn. Informatik (Operngasse 9)Metaheuristics and Hybrid Methods for Combinatorial Optimization
Mo.13.03.201710:00 - 12:00 Seminarraum Techn. Informatik (Operngasse 9)Metaheuristics and Hybrid Methods for Combinatorial Optimization
Di.14.03.201710:00 - 12:00 Seminarraum Techn. Informatik (Operngasse 9)Metaheuristics and Hybrid Methods for Combinatorial Optimization
Mi.15.03.201710:00 - 12:00 Seminarraum Techn. Informatik (Operngasse 9)Metaheuristics and Hybrid Methods for Combinatorial Optimization
Do.16.03.201710:00 - 12:00 Seminarraum Techn. Informatik (Operngasse 9)Metaheuristics and Hybrid Methods for Combinatorial Optimization
Fr.17.03.201710:00 - 12:00 Seminarraum Techn. Informatik (Operngasse 9)Metaheuristics and Hybrid Methods for Combinatorial Optimization
LVA wird geblockt abgehalten

Leistungsnachweis

Students will have to work on a practical project. Tasks include the implementation of heuristics, metaheuristics and hybrid techniques for a given combinatorial optimization problem. A basic C++ framework for doing so will be provided. Moreover, an experimental evaluation on a set of given problem instances must be performed, and a report about the implemented techniques and the experimental evaluation must be written. This report has to be delivered at most 4 weeks after then completion of the theory classes.

LVA-Anmeldung

Von Bis Abmeldung bis
06.03.2017 03:30 19.03.2017 03:30 12.03.2017 03:30

Anmeldemodalitäten:

Please register for this course via TISS.

Curricula

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Sprache

Englisch