87-052 Matheuristics

Veranstaltungsdetails
Lehrende: Prof. Dr. Stefan Voß
Veranstaltungsart:
Seminar
Anzeige im Stundenplan:
bwl--prom-meth2
Semesterwochenstunden:
2
Credits:
5,0
Unterrichtssprache:
Englisch
Min. | Max. Teilnehmerzahl:
- | -
Kommentare/ Inhalte: Course Overview:

  • Introduction
  • Heuristics
  • Local Search and Metaheuristics
  • Foundation (Complexity, Maths, Dantzig-Wolfe etc.)
  • Matheuristics: Hybridizing Metaheuristics and Mathematical Programming
  • Various Approaches (POPMUSIC, Feasibility Pump etc.)
  • Applications
  • Conclusions
  • In between: Interludes /
  • How to compare numerical results?
  • Student Presentations


Course Contents:

After World War 2 the main application area for optimization shifted from the military to the industry. Industrial activities, and related functions, yield a cornucopia of applications for optimization algorithms, often backed by substantial money for finding good solutions. Unsurprisingly therefore, we have records of several decades of efforts dedicated to the solution of the induced problems. And unfortunately almost all of them are NP-hard.

How do we deal with NP-hardness, when a good solution is needed with limited computational resources? By means of heuristics. So we have several decades of research on heuristic algorithms to exploit. As the limit on the available computational resources has been increasingly lifted, the set of utilizable methodologies progressively widened. First heuristics were very simple, constructive and local search, then we had metaheuristics. Now, we are moving forward, and one of the pursued paths leads to including mathematical programming techniques into the solution framework, giving rise to matheuristic algorithms.

The course will feature some hands-on experience on these progressively complex approaches to the solution of some (one? two? many?) combinatorial optimization problems, arising in an industrial context, presumably logistics, unless the attendants wish otherwise. Given the no free lunch theorem, and the deriving relevance of the instance source, we will utilize or generate real world (-like) instances to work upon. Simple heuristics and metaheuristics for the problem will be sketched and the corresponding code will be applied to the instance of concern.

Then, some matheuristic approaches will be introduced, with reference to the example problem. As matheuristics methods are deeply rooted into mathematics, we will agree whether to delve into the maths and justify few approaches, or to be shallow and present more approaches.

Matheuristcs of interest include decomposition methods, for example Lagrangian or Dantzig-Wolfe / column generation, MIP constraining, for example local branching or the corridor method, kernel problem identification, very large neighborhood search, POPMUSIC and possibly others. For some of these, the implemented code will be shown and validated.

Student evaluation:

Participation in the course, written term paper.
 
Zusätzliche Hinweise zu Prüfungen: Student Presentations
Übersicht der Kurstermine
1
2
3
4
5
6
7
8
9
10
11
12
 
 
 
Lehrende
Prof. Dr. Stefan Voß
Termine
Datum Von Bis Raum Lehrende Termine
1
Datum Fr, 13. Mai 2022
Bis 16:00
Bis 20:00
Lehrende Prof. Dr. Stefan Voß
2
Datum Fr, 13. Mai 2022
Bis 16:00
Bis 20:00
Lehrende Prof. Dr. Stefan Voß
3
Datum Sa, 14. Mai 2022
Bis 09:00
Bis 16:00
Lehrende Prof. Dr. Stefan Voß
4
Datum Sa, 14. Mai 2022
Bis 09:00
Bis 16:00
Lehrende Prof. Dr. Stefan Voß
5
Datum Fr, 20. Mai 2022
Bis 16:00
Bis 20:00
Lehrende Prof. Dr. Stefan Voß
6
Datum Fr, 20. Mai 2022
Bis 16:00
Bis 20:00
Lehrende Prof. Dr. Stefan Voß
7
Datum Sa, 21. Mai 2022
Bis 09:00
Bis 16:00
Lehrende Prof. Dr. Stefan Voß
8
Datum Sa, 21. Mai 2022
Bis 09:00
Bis 16:00
Lehrende Prof. Dr. Stefan Voß
9
Datum Fr, 10. Jun. 2022
Bis 16:00
Bis 20:00
Lehrende Prof. Dr. Stefan Voß
10
Datum Fr, 10. Jun. 2022
Bis 16:00
Bis 20:00
Lehrende Prof. Dr. Stefan Voß
11
Datum Sa, 11. Jun. 2022
Bis 09:00
Bis 16:00
Lehrende Prof. Dr. Stefan Voß
12
Datum Sa, 11. Jun. 2022
Bis 09:00
Bis 16:00
Lehrende Prof. Dr. Stefan Voß
Veranstaltungseigene Prüfungen
Beschreibung Datum Lehrende Pflicht
1. Blockprüfung k.Terminbuchung Ja