Lower bounds for binary quadratic minimization problems using nonconvex separable underestimators
Final Report Abstract
Kombinatorische Optimierungsprobleme entstehen in zahlreichen Anwendungen, z.B. im Verkehr und Transport oder in der Produktion. Während viele dieser Probleme in der linearen Version sehr gut untersucht sind und auch oft effiziente Algorithmen existieren, sind die entsprechenden Varianten mit quadratischer Zielfunktion weniger gut untersucht und in aller Regel sowohl praktisch als auch theoretisch sehr viel schwieriger optimal zu lösen. Im geförderten Projekt haben wir daher ein Verfahren entwickelt, das mit Hilfe eines Orakels für das lineare Problem auch das quadratische Problem lösen kann. Dabei liefert die Anwendung des Orakels duale Schranken, die in einem Branch-and-Bound-Verfahren eingebettet werden können. Der orakelbasierte Ansatz hat nicht nur den Vorteil, dass das Verfahren sehr allgemein anwendbar ist trotzdem das algorithmische Wissen über ein spezifisches Problem in Form des Orakels ausnutzt, sondern auch, dass eine Implementierung für neue Problemklassen sehr einfach ist, da nur das Orakel durch einen konkreten Algorithmus ersetzt werden muss. Die Effektivität des Verfahrens ist im Wesentlichen durch die Grundidee der separablen Unterschätzer gegeben, basiert aber auch auf vielen weiteren algorithmischen Ideen, die im Laufe der Förderung des Projekts entwickelt und verfeinert wurden. Dazu gehören insbesondere die deutliche Beschleunigung durch ein geeignetes Preprocessing und die Entwicklung eines maßgeschneiderten Verfahrens für die Lösung der dort auftretenden semidefiniten Programme. In der Summe ergibt sich ein Ansatz, der sowohl IP- als auch SDP-basierte State-of-the-art Software wie CPLEX und BiqCrunch auf den meisten Instanzklassen leistungsmäßig übertrifft, sofern die Variablen binär sind. Im Falle allgemeiner ganzzahliger Variablen muss festgehalten werden, dass sich der Ansatz als weniger erfolgreich herausgestellt hat, so dass hier andere Methoden besser geeignet sind. Für spezifische zugrunde liegende Problem lassen sich die Schranken weiter verbessern, indem die Forderung der Separabilität aufgeweicht wird. Hier ist jedoch zu beachten, dass die resultierende Unterschätzerfunktion noch effizient minimiert werden muss, um ein praktikables Verfahren zu erhalten. Im Falle der binären quadratischen Optimierung ohne Nebenbedingungen haben wir gezeigt, dass dieser Ansatz deutlich stärkere Schranken liefert als der ursprüngliche Ansatz. Eine ähnliche Verbesserung ist auch für das quadratische Kürzeste-Wege-Problem möglich. Ob der gesamte Algorithmus am Ende schneller läuft, hängt jedoch auch davon ab, wie schnell die komplexere Unterschätzerfunktion (in der Praxis) minimiert werden kann. Während sich etwa beim Kürzeste-Wege-Problem in unseren Untersuchungen herausgestellt hat, dass sich dieser Mehraufwand trotz der besseren Schranken nicht lohnt, führt der Ansatz bei der unrestringierten quadratischen binären Optimierung insgesamt zu schnelleren Lösungen.
Publications
- (2019) SDP-based branch-and-bound for non-convex quadratic integer optimization. J Glob Optim (Journal of Global Optimization) 73 (3) 485–514
Buchheim, Christoph; Montenegro, Maribel; Wiegele, Angelika
(See online at https://doi.org/10.1007/s10898-018-0717-z) - Separable Non-convex Underestimators for Binary Quadratic Programming. 12th International Symposium on Experimental Algorithms – SEA 2013, Lecture Notes in Computer Science 7933, pp 236–247 (2013)
Christoph Buchheim, Emiliano Traversi
(See online at https://doi.org/10.1007/978-3-642-38527-8_22) - Quadratic Combinatorial Optimization Using Separable Underestimators. INFORMS Journal on Computing
Christoph Buchheim, Emiliano Traversi
(See online at https://doi.org/10.1287/ijoc.2017.0789) - Conic optimization under combinatorial sparsity constraints. Technical Report, Optimization Online (2018)
Christoph Buchheim, Emiliano Travers
