Multikriterielle kombinatorische Optimierung in höheren Dimensionen

• Antragstellerin: Professorin Dr. Kathrin Klamroth
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 441310140

Bei Optimierungsproblemen im technischen, ingenieurwissenschaftlichen wie auch im wirtschaftswissenschaftlichen Bereich sind häufig verschiedene, sich widersprechende Optimierungskriterien zu berücksichtigen. Multikriterielle Modelle tragen dieser Tatsache Rechnung und sind darüberhinaus geeignet, zusätzliche Informationen zur Restriktionsbehandlung und zum Umgang mit unsicheren Daten bereitzustellen. Beispiele für multikriterielle kombinatorische Optimierungsprobleme sind multikriterielle Rucksackprobleme, multikriterielle Zuordnungsprobleme, und multikriterielle Netzwerkprobleme wie z.B. kürzeste Wege und spannende Baum Probleme.Die Anzahl der berücksichtigten Zielfunktionen hat entscheidenden Einfluss auf die Komplexität multikriterieller kombinatorischer Optimierungsprobleme. Während die Pareto Front bei bikriteriellen Problemen noch vollständig geordnet werden kann – wenn die erste Zielfunktion steigt, fällt die zweite und umgekehrt - ist dies bei drei und mehr Zielfunktionen nicht mehr möglich. Gleichzeitig mit der drastisch steigenden Zahl nichtdominierter Lösungen steigt damit auch die Komplexität der Pareto Menge und ihrer Beschreibung. In diesem Projekt wird die geometrische und kombinatorische Struktur der Pareto Menge genutzt, um sowohl auf theoretischer Ebene als auch auf algorithmischer Ebene entscheidende Fortschritte zu erzielen. Dies umfasst die Bestimmung repräsentativer Kandidatenmengen ebenso wie die Weiterentwicklung multikriterieller Branch and Bound Verfahren und die Analyse verschiedener Präferenzstrukturen und Qualiätsmaße.

• DFG-Verfahren: Sachbeihilfen