Explication de la branche et de la limite

J'ai un test sur la branche et l' algorithme lié . Je comprends théoriquement le fonctionnement de cet algorithme mais je n'ai pas trouvé d'exemples qui illustrent comment cet algorithme peut être implémenté pratiquement.

J'ai trouvé quelques exemples comme celui-ci mais je suis toujours confus à ce sujet. J'ai aussi cherché un problème de vendeur ambulant et je ne pouvais pas le comprendre.

J'ai besoin de quelques problèmes et comment ces problèmes peuvent-ils être résolus en utilisant branch et bound.

algorithms optimization branch-and-bound MR.NASS
la source

Qu'est-ce qui était difficile à comprendre? avez-vous déjà essayé de revenir en arrière ?

Ouais, je l'ai essayé. Le problème avec le B&B est que si j'obtiens un problème qui peut être résolu avec le B&B, je ne sais pas comment obtenir la borne inférieure pour chaque nœud et comment obtenir la fonction objectif. De plus, quelle est la première valeur du bestsofar que je compare avec chaque borne inférieure?

MR.NASS

@ MR.NASS Je ne sais pas exactement ce que vous dites dans votre dernier commentaire. Laissez-moi essayer d'expliquer. B&B est une méthode d'élagage de l'arbre de recherche. Elle peut être appliquée à des problèmes qui doivent optimiser une fonction objective. Il est généralement appliqué à des problèmes d'optimisation discrets ou combinatoires. À chaque étape, vous essayez de trouver une limite inférieure de la fonction objectif pour toutes les solutions possibles restantes. Si la limite inférieure est supérieure à la meilleure solution actuelle, vous pouvez arrêter la recherche et revenir en arrière (élagage de l'arbre de recherche), car il ne peut y avoir de solution avec un score inférieur.

George

Habituellement, on résout une version détendue du problème pour obtenir une limite inférieure. Pour les programmes mixtes entiers, il s'agit généralement de la relaxation de programmation linéaire.

Opt

@ MR.NASS Cela dépend de la fonction objectif. Comme Sid l'a dit, vous résolvez généralement une version détendue du problème donné. Habituellement, on veut utiliser une version détendue qui donne une bonne approximation du problème initial et peut être résolue efficacement. Notez que la version détendue doit donner une borne inférieure qui est au plus aussi élevée que la vraie borne inférieure afin de fonctionner correctement. Autre exemple: supposons que vous vouliez résoudre MAXSAT avec une méthode B&B. Pour une affectation de vérité partielle donnée, vous pouvez facilement calculer le nombre de clauses satisfaites. Une limite supérieure (car c'est un problème de maximisation) ...

George

Réponses:

Appliquons Branch and Bound à Knapsack , j'espère que cela clarifiera le concept pour vous.

Nous avons éléments, étiquetés de à . est la valeur du ème élément, et son poids. Nous essayons de les insérer dans un sac à dos pouvant contenir jusqu'à poids au total, et nous essayons de maximiser la somme des valeurs de l'article que nous mettons dans le sac à dos. $n$ $1$ $n$ $v_i$ $i$ $w_i$ $T$

$v_1$ $n-1$ $v_1$ $n-1$

$i$ $i$ $n$ $O(2^n)$

$T$ $n/2$ $n/2+1$ $n$ $n/2+1$ $n$ $2^{n/2}$

$d$ $O(2^d)$

Notez que cela s'appelle ' Bounding ' car il implique généralement une sorte de limite inférieure ou supérieure: pour le critère ' même si je mets tous les éléments restants, la valeur des éléments que j'ai mis ne dépassera pas la meilleure configuration J'ai trouvé jusqu'à présent ', la valeur de votre meilleure configuration jusqu'à présent est une limite inférieure sur la meilleure configuration, donc tout ce qui ne dépassera jamais cette limite inférieure est voué à l'échec.

Vous pouvez rendre la partie «délimitation» aussi complexe que vous le souhaitez. Par exemple, les problèmes de programmation entiers sont souvent résolus à l'aide de relaxations: vous relaxez votre programme en un programme linéaire, que vous pouvez résoudre en temps polynomial, puis vous pouvez jeter beaucoup de cas pour vos variables binaires qui ne fonctionneront jamais de toute façon. Vous branchez ensuite sur les options restantes.

Notez que Branch and Bound ne vous donne généralement qu'une augmentation de la vitesse en pratique, mais pas en théorie: il est difficile de dire exactement quelle partie de l'arbre de recherche est découpée à l'aide de votre heuristique. Ceci est attesté par le nombre d'heuristiques différentes utilisées en pratique sur de tels problèmes. Si vous n'avez pas de chance, l'arborescence de recherche restante reste énorme même avec beaucoup de limites.

Alex ten Brink
la source

Considérez la planification , la tâche d'affecter des tâches avec certaines durées et délais aux machines. Nous supposons un temps discret. Beaucoup de ces problèmes sont de niveau NP (O).

$1 \mid r_i \mid L_\max$

sur une machine
problèmes avec les dates de sortie et nous
minimiser le retard maximum , c'est-à-dire la différence maximale entre le délai et le temps de réalisation sur tous les travaux. $L_\max$

La version de décision de ce problème est NP-hard; cela peut être vu par réduction de 3PARTITION .

Chose intéressante, si nous autorisons la préemption , c'est-à-dire la permutation des travaux actifs, le problème peut être résolu en temps quadratique par la première heuristique de la première échéance (aux dates d'échéance modifiées). Il est facile de voir que la solution optimale de cette variante ne peut pas être pire que la solution optimale du problème d'origine.

Maintenant, afin d'appliquer Branch & Bound à ce problème, nous devons corriger certains paramètres:

Nous calculons les limites inférieures en autorisant la préemption et en utilisant EDD.
Nous branchons en fixant tous les travaux imprévus comme le prochain.
Nous allons d'abord à l'enfant avec les petites bornes inférieures.

Vous devez le faire pour chaque application de B&B.

Pour un exemple concret, considérons cette instance de : $1 \mid r_i \mid L_\max$

$\qquad \displaystyle \begin{array}{c|cccc} i & 1 & 2 & 3 & 4 \\ \hline p_i & 4 & 2 & 6 & 5 \\ r_i & 0 & 1 & 3 & 5 \\ d_i & 8 & 12 & 11 & 10 \end{array}$

avec les délais de traitement des travaux, les dates de sortie et les dates d'échéance. $p_i$ $r_i$ $d_i$

En exécutant B&B comme spécifié ci-dessus, cela se produit:

algorithme
_{Ce GIF ne fait pas de boucle. Rechargez- le dans un nouvel onglet pour voir depuis le début.}
^{[ source ] [ version statique ]}

Notez que sur 41 nœuds, seuls quatre sont visités correctement et seulement pour dix les bornes inférieures sont calculées.

Raphael
la source