Ramificar y vincular es una heurística eficaz para los problemas de búsqueda, y Wikipedia enumera una serie de problemas difíciles en los que se ha utilizado ramificar y vincular. Sin embargo, no he podido encontrar referencias que sugieran que es más que solo "un método" para resolver estos problemas.
Como anécdota, escuché que algunas de las mejores heurísticas para la programación de SAT y enteros provienen de la rama y el límite, por lo que mi pregunta es:
¿Alguien puede señalarme alguna referencia que detalle los usos efectivos de la rama y los problemas de NP-hard?
ds.algorithms
reference-request
optimization
heuristics
Suresh Venkat
fuente
fuente
Respuestas:
Para TSP, consulte este libro ... http://www.tsp.gatech.edu/book/index.html
Tengo entendido que no hay una herramienta única para matarlos a todos. Podría decirse que cualquier solución recursiva que despliegue el backtracking y alguna función de puntuación está utilizando branch and bound. Como tal, una gran fracción de los solucionadores de problemas difíciles de NP utilizan alguna forma de ramificación y unión.
fuente
El problema de partición de la camarilla podría no ser el problema NP-hard más popular, pero se resolvió de manera eficiente utilizando ramificaciones y enlaces, consulte este documento: http://joc.journal.informs.org/content/6/2/141 .resumen
fuente
Algoritmos exponenciales exactos es un buen libro reciente sobre tales algoritmos. Algoritmo X para el problema exacto de la cubierta también es bueno saber.
fuente