Version imprimable
Bonjour a tous,
C’est ce que je n’arrive pas à saisir est : quand en dois avoir besoin d'utilisé la méthode du branch-and-bound (résolution par séparation et évaluation) ? Dans quel type de problème ? (un exemple sera idéal)
Merci
NB : en nous demande de l'utilisé mais pour quoi, quel est le besoin possible pour cette façon de faire.
:salut:
Son intérêt principal est de résoudre les problèmes d'optimisation discrète (et Wikipedia est du même avis : https://en.wikipedia.org/wiki/Branch_and_bound). Les algorithmes traditionnels, type simplexe pour des problèmes linéaires https://en.wikipedia.org/wiki/Simplex_algorithm, proposent une solution, mais ne peuvent pas s'assurer que les variables qui doivent rester entières le sont, c'est là que la séparation et séparation est utile. De plus, elle ne se focalise pas sur la génération d'une solution faisable, l'algorithme peut aller jusqu'à l'optimalité, tout en gardant une mesure de la distance entre la solution actuelle et l'optimalité.
Avec un peu plus de pratique, le problème du voyageur de commerce peut être résolu par des techniques de programmation en nombres entiers (voir https://en.wikipedia.org/wiki/Travel...ng_formulation). Cet algorithme permet de le résoudre, en plus d'une méthode pour optimiser des programmes linéaires. Par contre, ce n'est pas forcément la méthode la plus efficace pour obtenir une bonne solution.
Si tu veux plus d'informations, teste ces quelques mots clés : recherche opérationnelle, programmation en nombre entiers, optimisation discrète/combinatoire.