Erfolgreiche Anwendung von Branch-and-Bound-Methoden für NP-harte Probleme

13

Branch-and-Bound ist eine effektive Heuristik für Suchprobleme, und Wikipedia listet eine Reihe schwerwiegender Probleme auf, bei denen Branch-and-Bound verwendet wurde. Es ist mir jedoch nicht gelungen, Referenzen zu finden, die darauf hindeuten, dass dies mehr als nur eine Methode zur Lösung dieser Probleme ist.

Anekdotisch habe ich gehört, dass einige der besten Heuristiken für SAT- und Integer-Programmierung von Branch and Bound stammen, daher lautet meine Frage:

Kann mich jemand auf Referenzen hinweisen, die die effektive Nutzung von Zweigen und die Bewältigung von NP-schwierigen Problemen beschreiben?

ds.algorithms reference-request optimization heuristics Suresh Venkat
quelle
1
Ich lese dieses Papier gerade aus einem anderen Grund, aber es scheint Ihre Frage zu berühren, und es ist faszinierend: Algorithmus-Portfolios von Gomes und Selman.
Aaron Sterling
2
Ein gutes Buch zum Thema Integer-Programmierung ist Integer and Combinatorial Optimization von Nemhauser & Wolsey. Behandelt eine breite Palette von Themen, einschließlich verschiedener Paradigmen wie Verzweigen und Binden, Verzweigen und Schneiden usw. und anderer IP-Techniken wie Schneiden von Ebenen usw.
Opt

Antworten:

9

Informationen zu TSP finden Sie in diesem Buch ... http://www.tsp.gatech.edu/book/index.html

Mein Verständnis ist, dass es kein einziges Werkzeug gibt, um sie alle zu töten. Es ist anzunehmen, dass jede rekursive Lösung, die Backtracking und einige Bewertungsfunktionen einsetzt, Branch-and-Bound verwendet. Als solches verwendet ein großer Teil der Löser für NP-schwierige Probleme irgendeine Form von Verzweigung und Bindung.

Sariel Har-Peled
quelle
9

Das Clique-Partitionierungsproblem ist möglicherweise nicht das beliebteste NP-schwierige Problem, wurde jedoch mithilfe von Branch-and-Bound effizient gelöst (siehe dieses Dokument: http://joc.journal.informs.org/content/6/2/141) .abstrakt

Florian Jaehn
quelle