Message > comparaison de bornes

  • Forum 'Discussions' - Sujet créé le 17/09/2015 par etudiantero (5323 vues)


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







Moteur de recherche