Berechnung von Optimalitätszertifikaten für konvexe gemischt-ganzzahlige nichtlineare Probleme

Jedes Optimierungsproblem hat ein entsprechendes Verifizierungsproblem, das überprüft, ob eine gegebene optimale Lösung tatsächlich optimal ist. In der Literatur gibt es viele Möglichkeiten, die Optimalität einer gegebenen Lösung zu überprüfen, beispielsweise den Branch-and-Bound-Baum. Um diese Aufgabe zu vereinfachen, wurden Optimalitätszertifikate für konvexe gemischt-ganzzahlige nichtlineare Programme eingeführt, und es wurde gezeigt, dass die Größen der Zertifikate in Bezug auf die Anzahl der ganzzahligen Variablen begrenzt sind. Wir führen einen Algorithmus zur Berechnung der Zertifikate ein und führen rechnergestützte Experimente durch. Durch die Experimente zeigen wir, dass die Optimalitätszertifikate überraschend klein sein können. Geschichte: Akzeptiert von Andrea Lodi, Fachredakteur für Entwurf & Analyse von Algorithmen — Diskret. Finanzierung: Diese Arbeit wurde von der Deutschen Forschungsgemeinschaft CRC 154 Teilprojekt A05, CRC 154 Teilprojekt B07 und SFB Transregio 154 sowie dem Bundesministerium für Wirtschaft und Energie unterstützt. Ergänzendes Material: Die Software, die die Ergebnisse dieser Studie unterstützt, ist im Artikel und den ergänzenden Informationen ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0099 ) sowie im IJOC GitHub Software-Repository ( https://github.com/INFORMSJoC/2022.0099 ) verfügbar. Das vollständige IJOC Software- und Daten-Repository ist unter https://informsjoc.github.io/ verfügbar.