Introduction
La procédure de séparation et d'évaluation ou la méthode "Branch and Bound" est une méthode qui consiste à construire un arbre de recherche implicite. Cet arbre est exploré de façon à éviter les branches inutiles/dominées. Une branche dominée est une partie de l'espace de recherche qui est vide des solutions réalisables ou bien ne contenant aucune solution plus intéressante qu'une solution courante. Cette exploration intelligente est réalisée grâce à des évaluations des branches et à des comparaisons avec un seuil de la valeur du critère (également appelé borne). Pour les problèmes combinatoires de grande taille, cette technique risque de générer une arborescente conséquente à explorer (phénomène d'explosion combinatoire). Pour remédier à un tel problème, la borne utilisée doit être la plus fine/serrée possible [Carlier et Chrétienne, 1988 ; Wolsey 1998].
