Branch and bound adalah heuristik yang efektif untuk masalah pencarian, dan Wikipedia mencantumkan sejumlah masalah sulit di mana branch-and-bound telah digunakan. Namun, saya belum dapat menemukan referensi untuk menyarankan bahwa itu lebih dari sekedar "satu metode" untuk menyelesaikan masalah ini.
Secara anekdot, saya pernah mendengar bahwa beberapa heuristik terbaik untuk SAT dan pemrograman integer berasal dari cabang dan terikat, jadi pertanyaan saya adalah:
Dapatkah seseorang mengarahkan saya ke referensi yang merinci penggunaan cabang yang efektif dan terikat untuk masalah NP-hard?
ds.algorithms
reference-request
optimization
heuristics
Suresh Venkat
sumber
sumber
Jawaban:
Untuk TSP, periksa buku ini ... http://www.tsp.gatech.edu/book/index.html
Pemahaman saya adalah bahwa tidak ada satu alat untuk membunuh mereka semua. Bisa dibilang setiap solusi rekursif menggunakan backtracking dan beberapa fungsi penilaian menggunakan cabang dan terikat. Dengan demikian, sebagian besar pemecah masalah sulit NP menggunakan beberapa bentuk cabang dan terikat.
sumber
Clique Partitioning Problem mungkin bukan masalah NP-hard paling populer, tetapi diselesaikan secara efisien menggunakan cabang-dan-terikat, lihat makalah ini: http://joc.journal.informs.org/content/6/2/141 .abstrak
sumber
Algoritma Eksponensial Eksak adalah buku terbaru yang bagus tentang algoritma tersebut. Algoritma X untuk masalah cover yang tepat juga baik untuk diketahui.
sumber