Branch and price
- 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.
Voir aussi
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
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Branch and price de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Price Daniel — as a United States Senator. Associate Justice, Texas Supreme Court In office January 1971 – December 1978 Nationa … Wikipedia
Price Daniel, Jr. — Price Daniel Jr. Speaker of the Texas House of Representatives In office 1973–1975 Preceded by Rayford Price Succeeded by Bill W. Clayton Texas State Representa … Wikipedia
Price, Sir Uvedale, 1st Baronet — ▪ British landscape designer born , 1747 died Sept. 14, 1829, Foxley, Herefordshire, Eng. British landscape designer and, with the writer artist William Gilpin and Richard Payne Knight, one of the chief aestheticians of the Picturesque movement… … Universalium
Price Hill, Cincinnati — Price Hill is a neighborhood of Cincinnati, Ohio, located north of Sedamsville and Riverside, south of Westwood and South Fairmount, and west of Queensgate. It is one of the oldest outlying settlements of Cincinnati, [ [http://frontier.cincinnati … Wikipedia
Price war — is a term used in business to indicate a state of intense competitive rivalry accompanied by a multi lateral series of price reductions. One competitor will lower its price, then others will lower their prices to match. If one of the reactors… … Wikipedia
Branch Rickey — Infobox MLB retired name=Branch Rickey position=Catcher/Manager/Executive bgcolor1=#BC003A bgcolor2=#BC003A textcolor1=white textcolor2=white bats=Left throws=Right birthdate=December 20, 1881 deathdate=death date and age|1965|12|9|1881|12|20… … Wikipedia
The Price Is Right (U.S. game show) — The Price Is Right Format Game show Created by Mark Goodson Bill Todman Directed b … Wikipedia
Ulster and Delaware Railroad — Locale Kingston Point, NY to Oneonta, NY, Hunter, NY Kaaterskill, NY … Wikipedia
Philadelphia, Wilmington and Baltimore Railroad — Locale Pennsylvania, Delaware and Maryland Dates of operation 1836–1902 Successor Philadelphia, Baltimore and Washington Railroad Track gauge 4 ft 8 … Wikipedia
Doctrine and Covenants — The Doctrine and Covenants (sometimes abbreviated and cited as D C or D. and C.) is a part of the open scriptural canon of several denominations of the Latter Day Saint movement. Originally published in 1835 as Doctrine and Covenants of the… … Wikipedia
