Application réussie des méthodes de branchement et de limitation pour les problèmes NP-difficiles

13

Branch and bound est une heuristique efficace pour les problèmes de recherche, et Wikipedia répertorie un certain nombre de problèmes difficiles où branch-and-bound a été utilisé. Cependant, je n'ai pas été en mesure de trouver des références pour suggérer que c'est plus qu'une "seule méthode" pour résoudre ces problèmes.

Pour l'anecdote, j'ai entendu dire que certaines des meilleures heuristiques pour la programmation SAT et entière viennent de la branche et de la borne, donc ma question est:

Quelqu'un peut-il m'indiquer des références détaillant les utilisations efficaces de la branche et liées aux problèmes NP-difficiles?

ds.algorithms reference-request optimization heuristics Suresh Venkat
la source
1
Je suis en train de lire cet article pour une raison différente, mais il semble toucher à votre question, et elle est fascinante: les portefeuilles d'algorithmes de Gomes et Selman.
Aaron Sterling
2
Un bon livre à lire sur la programmation entière est Integer and Combinatorial Optimization par Nemhauser & Wolsey. Couvre un large éventail de sujets, y compris différents paradigmes comme la branche et lié, la branche et la coupe, etc. et d'autres techniques IP comme les plans de coupe, etc.
Opt

Réponses:

9

Pour TSP, consultez ce livre ... http://www.tsp.gatech.edu/book/index.html

Je crois comprendre qu'il n'y a pas un seul outil pour tous les tuer. On peut dire que toute solution récursive déployant le backtracking et une fonction de scoring utilise branch et bound. En tant que tel, une grande partie des résolveurs de problèmes difficiles NP utilisent une certaine forme de branche et liée.

Sariel Har-Peled
la source
9

Le problème de partitionnement de clique n'est peut-être pas le problème NP le plus populaire, mais il a été efficacement résolu en utilisant une branche et une liaison, voir cet article: http://joc.journal.informs.org/content/6/2/141 .abstrait

Florian Jaehn
la source