V..Gabrel, M..Minoux Large scale LP relaxations for minimum cost multicommodity flow problems with step increasing cost functions and computational results On s'intéresse ici à une classe particulièrement difficile de problèmes de multiflots à coût minimum : celle où les fonctions de coût sur les liens du réseau sont discontinues et croissantes en escalier. Plusieurs relaxations sous forme de programmes linéaires sont proposées, qui conduisent à des problèmes de (très) grande taille. On montre que les solutions optimales con­ tinues de ces programmes linéaires peuvent néanmoins être obtenues par des techniques de programmation linéaire généralisée, combinant génération de colonnes et génération de contraintes. On présente des résultats de calcul préliminaires qui montrent que les relaxations proposées permettent d'obtenir des bornes inférieures s'écartant typiquement de 10% a 20% des solutions optimales (inconnues). A notre connaissance, il s'agit là de la première approche systématique pour générer des bornes inférieures non triviales pour des problèmes de multiflots à fonctions de coût croissantes en escalier. We address here a class of particularly hard-to-solve minimum cost multicommodity network flow problems when the link cost functions are discontinuous step increasing. Several LP relax­ ations for such problems are proposed, giving rise to (very) large scale linear programs. It is shown that the continuous op­ timal solutions to these linear programs can nevertheless be ob­ tained via combined column generation and constraint generation procedures. Preliminary computational results are presented show­ ing that our relaxations lead to lower bounds typically within 10% to 20% off the (unknown) optimal values. As far as we know, this is the first time a systematic way of generating nontrivial lower bounds to minimum cost multicommodity network flow problems with step increasing (discontinuous) cost functions is proposed.