Aplicação bem-sucedida de métodos branch-and-bound para problemas difíceis de NP

13

Ramificação e encadernação é uma heurística eficaz para problemas de pesquisa, e a Wikipedia lista vários problemas difíceis nos quais ramificações e encadernações foram usadas. No entanto, não consegui encontrar referências para sugerir que é mais do que apenas "um método" para resolver esses problemas.

Curiosamente, ouvi dizer que algumas das melhores heurísticas para SAT e programação inteira vêm de branch and bound, então minha pergunta é:

Alguém pode me indicar referências que detalhem usos eficazes de ramificações e vinculado a problemas difíceis de NP?

Suresh Venkat
fonte
1
Agora, estou lendo este artigo por um motivo diferente, mas parece tocar na sua pergunta e é fascinante: Portfólios de algoritmos de Gomes e Selman.
Aaron Sterling
2
Um bom livro para ler sobre programação inteira é a Otimização de números inteiros e combinatórios da Nemhauser & Wolsey. Abrange uma vasta gama de tópicos, incluindo diferentes paradigmas como ramo e vinculada, ramo e corte, etc, e outras técnicas de IP como planos de corte, etc.
Opt

Respostas:

9

Para o TSP, confira este livro ... http://www.tsp.gatech.edu/book/index.html

Meu entendimento é que não existe uma ferramenta para matá-los todos. Indiscutivelmente, qualquer solução recursiva que implante backtracking e alguma função de pontuação está usando branch e bound. Como tal, uma grande fração de solucionadores de problemas difíceis de NP usa alguma forma de ramificação e vinculação.

Sariel Har-Peled
fonte