Le 17/09/2015 par etudiantero :
Bon apres midi, pour la methode de branch and bound , j'ai calculé une borne sup pour mon probleme de minimisation j'ai calculé aussi les bornes inferieures mais je ne sais pas comment comparer et mettre à jour comment faire?
Le 17/09/2015 par snoop :
Bonsoir,
.
La question n'est pas très claire.
.
Le branch-and-bound est une méthode arborescente pour résoudre des problèmes combinatoires discrets. Dans la version classique, le parcours de l'espace des solutions s'effectue en explorant un graphe orienté acyclique binaire (= arbre binaire).
On calcule une borne inférieure au problème de minimisation à chaque noeud de l'arbre. La recherche commence à la racine et se poursuit par récurrence dans chaque branche de l'arbre jusqu'à l'obtention de noeuds fournissant soit :
(1) une solution réalisable.
(2) un problème irréalisable.
(3) une borne inf supérieure dont la valeur est égale ou supérieure à celle de la borne sup.
Pour ces 3 trois conditions d'arrêt, on dit que la recherche est partielle car l'exploration de certaines branches s'arrête prématurément.
Lorsqu'un noeud fournit une borne inférieure correspondant à une solution réalisable, celle-ci devient la nouvelle borne supérieure du problème initiale si elle est plus intéressante que la borne sup actuelle.
En espérant que cette brève présentation puisse t'aider
Le 17/09/2015 par snoop :
Bonsoir,
.
La question n'est pas très claire.
.
Le branch-and-bound est une méthode arborescente pour résoudre des problèmes combinatoires discrets. Dans la version classique, le parcours de l'espace des solutions s'effectue en explorant un graphe orienté acyclique binaire (= arbre binaire).
On calcule une borne inférieure au problème de minimisation à chaque noeud de l'arbre. La recherche commence à la racine et se poursuit par récurrence dans chaque branche de l'arbre jusqu'à l'obtention de noeuds fournissant soit :
(1) une solution réalisable.
(2) un problème irréalisable.
(3) une borne inf dont la valeur est égale ou supérieure à celle de la borne sup.
Pour ces 3 trois conditions d'arrêt, on dit que la recherche est partielle car l'exploration de certaines branches s'arrête prématurément.
Lorsqu'un noeud fournit une borne inférieure correspondant à une solution réalisable, celle-ci devient la nouvelle borne supérieure du problème initiale si elle est plus intéressante que la borne sup actuelle.
En espérant que cette brève présentation puisse t'aider
