Skuteczne zastosowanie metod rozgałęzionych i związanych z problemami trudnymi dla NP

13

Rozgałęzienie i powiązanie to skuteczna heurystyka dla problemów wyszukiwania, a Wikipedia wymienia wiele trudnych problemów, w których zastosowano rozgałęzienie i powiązanie. Jednak nie udało mi się znaleźć referencji sugerujących, że jest to więcej niż „jedna metoda” rozwiązania tych problemów.

Anegdotycznie słyszałem, że jedne z najlepszych heurystyki dla programowania SAT i liczb całkowitych pochodzą z gałęzi i są powiązane, więc moje pytanie brzmi:

Czy ktoś może wskazać mi jakieś odniesienia opisujące efektywne wykorzystanie gałęzi i związane z trudnymi NP?

ds.algorithms reference-request optimization heuristics Suresh Venkat
źródło
1
Właśnie czytam ten artykuł z innego powodu, ale wydaje się, że porusza twoje pytanie i jest fascynujący: portfolio algorytmów Gomesa i Selmana.
Aaron Sterling
2
Dobra książka do czytania o programowaniu liczb całkowitych to Integer and Combinatorial Optimization autorstwa Nemhauser & Wolsey. Obejmuje szeroki zakres tematów, w tym różne paradygmaty, takie jak odgałęzienie i powiązanie, rozgałęzienie i wycięcie itp. Oraz inne techniki własności intelektualnej, takie jak wycinanie samolotów itp.
Opt

Odpowiedzi:

9

W przypadku TSP sprawdź tę książkę ... http://www.tsp.gatech.edu/book/index.html

Rozumiem, że nie ma jednego narzędzia do zabicia ich wszystkich. Prawdopodobnie każde rozwiązanie rekurencyjne wykorzystujące backtracking i niektóre funkcje oceniania używają rozgałęzienia i powiązania. Jako taka, duża część solverów do trudnych problemów NP wykorzystuje jakąś formę rozgałęzienia i związania.

Sariel Har-Peled
źródło