5.8.3 Méthode de séparation
Dans une méthode classique de Branch & Price, telle
que présentée précédemment, une fois que le
problème maître restreint est résolu à l'optimum,
dans le cas où il existe des variables fractionnaires, on applique une
méthode de séparation. On crée donc un certain nombre de
noeuds (généralement deux voire trois). Ces noeuds consistent
à rajouter une contrainte sur une variable ou un ensemble de variables
(contrainte d'intégralité, borne inférieure ou
supérieure,...). La génération de colonnes est ensuite
appelée à nouveau par le biais du problème esclave, qui
intègre les contraintes rajoutées par le noeud courant. Le
problème esclave va donc rajouter un certain nombre de colonnes dans
l'ensemble 1. Lorsqu'aucun chemin de coût négatif ne sera
trouvé, la méthode de séparation sera rappelée.
Un des moyens de rendre un Branch & Price heuristique est
de supprimer l'aspect « Pricing ». Pour cela, il suffit de ne pas
générer de nouvelles colonnes une fois qu'un noeud est
créé, en dehors du noeud racine. Les contraintes contenues dans
le noeud sont rajoutées dans le problème maître restreint.
La résolution de la relaxation linéaire du problème
correspondant permet d'avoir une borne inférieure sur le coût du
noeud. On se retrouve donc dans la configuration d'un Branch & Bound
classique pour lequel la borne inférieure est calculée par la
relaxation linéaire du problème maître restreint, la borne
supérieure étant la meilleure solution entière connue.
Cette méthode peut s'avérer efficace si un grand nombre de
colonnes est rajouté au noeud racine, étant donné
qu'aucune nouvelle colonne ne sera ajoutée lors des itérations
suivantes. Cette transformation d'un Branch & Price en un Branch &
Bound est possible pour l'arbre complet ou pour n'importe quel sous-arbre.
| 
