Branch and price
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.
Notes et références
- (en) M.W.P. Savelsbergh (1997). A branch-and-price algorithm for the generalized assignment problem. Oper. Res. 45, 831–841 .
- (en) C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.F. Savelsbergh et P.H. Vance. Branch-and-Price. Column Generation for Solving Huge Integer Programs. Operations Research, Vol. 46, No. 3, pp. 316-329, May-June 1998
- (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) M. Desrochers, F.M. Solomon. (1989). A column generation approach to the urban transit crew scheduling problem. Transp. Sci. 23, 1–13