Large scale LP relaxations for minimum cost multicommodity flow problems with step increasing cost functions and computational results

V. Gabrel, M. Minoux

Masi-IBP 1996/17: Rapport de Recherche Masi / Masi research reports
16 pages - Juin/June 1996 - Document en anglais.

PostScript : 84 Ko /Kb

Titre français : Relaxations pour les problèmes de multiflot à coût minimum avec des fonctions de coût croissantes en escalier et résultats expérimentaux
Titre anglais : Large scale LP relaxations for minimum cost multicommodity flow problems with step increasing cost functions and computational results

Résumé : 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 continues 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.

Abstract : 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 relaxations for such problems are proposed, giving rise to (very) large scale linear programs. It is shown that the continuous optimal solutions to these linear programs can nevertheless be obtained via combined column generation and constraint generation procedures. Preliminary computational results are presented showing 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.

Mots-clés : Optimisation de réseaux de télécommunications, multiflot à coût minimum, optimisation de problèmes de grande taille

Key-words : Telecommunication network optimization, minimum cost multicommodity network flow, large scale optimization

Publications internes Masi 1996 / Masi research reports 1996