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

Termine
Datum Von Bis Raum Lehrende
1 Fr, 13. Mai 2022 16:00 20:00 Prof. Dr. Stefan Voß
2 Fr, 13. Mai 2022 16:00 20:00 Prof. Dr. Stefan Voß
3 Sa, 14. Mai 2022 09:00 16:00 Prof. Dr. Stefan Voß
4 Sa, 14. Mai 2022 09:00 16:00 Prof. Dr. Stefan Voß
5 Fr, 20. Mai 2022 16:00 20:00 Prof. Dr. Stefan Voß
6 Fr, 20. Mai 2022 16:00 20:00 Prof. Dr. Stefan Voß
7 Sa, 21. Mai 2022 09:00 16:00 Prof. Dr. Stefan Voß
8 Sa, 21. Mai 2022 09:00 16:00 Prof. Dr. Stefan Voß
9 Fr, 10. Jun. 2022 16:00 20:00 Prof. Dr. Stefan Voß
10 Fr, 10. Jun. 2022 16:00 20:00 Prof. Dr. Stefan Voß
11 Sa, 11. Jun. 2022 09:00 16:00 Prof. Dr. Stefan Voß
12 Sa, 11. Jun. 2022 09:00 16:00 Prof. Dr. Stefan Voß
Veranstaltungseigene Prüfungen
Beschreibung Datum Lehrende Pflicht
1. Blockprüfung k.Terminbuchung Ja
Übersicht der Kurstermine
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  •  
  •  
  •  
Lehrende
Prof. Dr. Stefan Voß