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

Notes et références

↑ (en) Martin Savelsbergh, « A Branch-and-Price Algorithm for the Generalized Assignment Problem », Operations Research, vol. 45, n^o 6,‎ décembre 1997, p. 831–841 (ISSN 0030-364X et 1526-5463, DOI 10.1287/opre.45.6.831, lire en ligne, consulté le 9 décembre 2023)
↑ (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, n^o 3,‎ juin 1998, p. 316–329 (ISSN 0030-364X et 1526-5463, DOI 10.1287/opre.46.3.316, lire en ligne, consulté le 9 décembre 2023)
↑ (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, n^o 1,‎ février 1989, p. 1–13 (ISSN 0041-1655 et 1526-5447, DOI 10.1287/trsc.23.1.1, lire en ligne, consulté le 9 décembre 2023)

Portail de l'informatique théorique

[1] (en) Martin Savelsbergh, « A Branch-and-Price Algorithm for the Generalized Assignment Problem », Operations Research, vol. 45, n^o 6,‎ décembre 1997, p. 831–841 (ISSN 0030-364X et 1526-5463, DOI 10.1287/opre.45.6.831, lire en ligne, consulté le 9 décembre 2023)

[2] (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, n^o 3,‎ juin 1998, p. 316–329 (ISSN 0030-364X et 1526-5463, DOI 10.1287/opre.46.3.316, lire en ligne, consulté le 9 décembre 2023)

[3] (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.

[4] (en) Martin Desrochers et François Soumis, « A Column Generation Approach to the Urban Transit Crew Scheduling Problem », Transportation Science, vol. 23, n^o 1,‎ février 1989, p. 1–13 (ISSN 0041-1655 et 1526-5447, DOI 10.1287/trsc.23.1.1, lire en ligne, consulté le 9 décembre 2023)

[1]

[2]

[3]

[4]