Branch and price
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Branch and price est une méthode d'optimisation combinatoire pour résoudre des problèmes d'optimisation linéaire en nombres entiers. Cette méthode combine l'algorithme du branch and bound classique avec une génération de colonnes à chaque nœud de l'arbre. Baptisée par Savelsbergh et al.[1],[2], cette technique a été initialement proposée par Johnson[3] et implémentée par Desrochers et al.[4].
On définit ici tout d'abord un problème maître dont on a relâché les contraintes d'intégrité qui sont imposées au fur et à mesure de la descente dans l'arbre du branch and bound et un problème esclave (appelé aussi problème de pricing) qui évalue chaque nouvelle colonne ou groupe de colonnes ajoutées au problème maître.
Très efficace sur des problèmes de très grande taille, la méthode reste cependant complexe à mettre en œuvre. Le problème dual est souvent non polynomial et sa formulation n'est pas toujours triviale.
Voir aussi[modifier | modifier le code]
Notes et références[modifier | modifier le code]
- (en) Martin Savelsbergh, « A Branch-and-Price Algorithm for the Generalized Assignment Problem », Operations Research, vol. 45, no 6, , p. 831–841 (ISSN 0030-364X et 1526-5463, DOI 10.1287/opre.45.6.831, lire en ligne, consulté le )
- (en) Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser et Martin W. P. Savelsbergh, « Branch-and-Price: Column Generation for Solving Huge Integer Programs », Operations Research, vol. 46, no 3, , p. 316–329 (ISSN 0030-364X et 1526-5463, DOI 10.1287/opre.46.3.316, lire en ligne, consulté le )
- (en) E.L. Johnson. Modeling and strong linear programs for mixed integer programming (1989). S.W.Wallace (ed). Algorithms and Model Formulations in Mathematical Programming, Springer-Verlag, 1–43.
- (en) Martin Desrochers et François Soumis, « A Column Generation Approach to the Urban Transit Crew Scheduling Problem », Transportation Science, vol. 23, no 1, , p. 1–13 (ISSN 0041-1655 et 1526-5447, DOI 10.1287/trsc.23.1.1, lire en ligne, consulté le )
