Erlernen gültiger dualer Grenzen in der Constraints-Programmierung: Boosted Lagrangian Zerlegung mit selbstüberwachtem Lernen

Die Lagrange-Zerlegung (LD) ist ein Relaxationsverfahren, das eine duale Schranke für konstruierte Optimierungsprobleme bereitstellt, indem es diese in handhabbarere Teilprobleme zerlegt. Diese Schranke kann in Branch-and-Bound-Algorithmen verwendet werden, um den Suchraum effektiv zu beschneiden. Kurz gesagt, ein Vektor von Lagrange-Multiplikatoren wird mit jedem Teilproblem assoziiert, und ein iteratives Verfahren (z. B. eine Subgradientenoptimierung) passt diese Multiplikatoren an, um die engste Schranke zu finden. Ursprünglich auf die ganzzahlige Programmierung angewendet, hatte die Lagrange-Zerlegung auch in der Constraints-Programmierung aufgrund ihrer Vielseitigkeit und der Tatsache, dass globale Einschränkungen natürliche Teilprobleme bieten, Erfolg. Allerdings macht die nichtlineare und kombinatorische Natur der Teilprobleme in der Constraints-Programmierung die Optimierung der Lagrange-Multiplikatoren mit Subgradientenmethoden an jedem Knoten der Baumsuche rechenintensiv. Dies begrenzt derzeit die Praktikabilität von LD als allgemeinem Schrankenmechanismus für die Constraints-Programmierung. Um diese Herausforderung anzugehen, schlagen wir einen selbstüberwachten Lernansatz vor, der neuronale Netzwerke nutzt, um Multiplikatoren direkt zu generieren, was zu engen Schranken führt. Dieser Ansatz reduziert signifikant die Anzahl der benötigten Schritte zur Subgradientenoptimierung, verbessert die Beschneidungseffizienz und verkürzt die Ausführungszeit der Solver für die Constraints-Programmierung. Dieser Beitrag ist einer der wenigen, die Lernen nutzen, um Schrankenmechanismen auf der dualen Seite zu verbessern, ein kritisches Element im Design kombinatorischer Solver. Soweit uns bekannt ist, präsentiert diese Arbeit die erste generische Methode zum Lernen gültiger dualer Schranken in der Constraints-Programmierung.