Der Artikel "Convex mixed-integer optimization with Frank–Wolfe methods" von Deborah Hendrych, Hannah Troppens, Mathieu Besançon und Sebastian Pokutta vom Interactive Optimization and Learning Lab am ZIB und der TU Berlin wurde als Outstanding Paper of the Year 2025 des Journals Mathematical Programming Computation (MPC), dem führenden Journal für Computational Mathematical Optimization, das in Zusammenarbeit mit der Mathematical Optimization Society veröffentlicht wird, ausgezeichnet. Mathieu Besançon ist inzwischen als Fakultätsmitglied an das Inria-Zentrum an der Université Grenoble Alpes gewechselt.
Die gemischt-ganzzahlige nichtlineare Optimierung umfasst eine breite Klasse von Problemen, die sowohl theoretische als auch rechnerische Herausforderungen mit sich bringt. Das ausgezeichnete Paper schlägt einen neuen Typ von Verfahren für diese Probleme vor, basierend auf einem Branch-and-Bound-Algorithmus mit konvexen Relaxationen der Knoten. Diese Relaxationen werden mit einem Frank–Wolfe-Algorithmus über der konvexen Hülle der gemischt-ganzzahligen zulässigen Punkte gelöst (statt über der kontinuierlichen Relaxation), wobei ein gemischt-ganzzahliger linearer Löser als lineares Minimierungsorakel dient. Das Verfahren berechnet zulässige Lösungen, während es mit einer einzigen Darstellung der polyedrischen Nebenbedingungen arbeitet, nutzt die volle Leistungsfähigkeit gemischt-ganzzahliger linearer Löser ohne Outer-Approximation-Schema und kann ungenaue Lösungen von Teilproblemen ausnutzen. Die Abbildung zeigt eine schematische Darstellung der neuen Methode, welche als open-source Julia Paket Boscia.jl verfügbar ist.
Die Forschung wurde vom Exzellenzcluster Math+ und dem Forschungscampus MODAL finanziert.
Herzlichen Glückwunsch!
