Models for the piecewise linear unsplittable multicommodity flow problems

Bernard Fortz 1, 2 Luis Gouveia 3 Martim Joyce-Moniz 1
2 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : In this paper, we consider multicommodity flow problems, with unsplit-table flows and piecewise linear routing costs. We first focus on the case where the piecewise linear routing costs are convex. We show that this problem is N P-hard for the general case, but polynomially solvable when there is only one commodity. We then propose a strengthened mixed-integer programming formulation for the problem. We show that the linear relaxation of this formulation always gives the optimal solution of the problem for the single commodity case. We present a wide array of computational experiments, showing this formulation also produces very tight linear programming bounds for the multi-commodity case. Finally, we also adapt our formulation for the non-convex case. Our experimental results imply that the linear programming bounds for this case, are only slightly than the ones of state-of-the-art models for the splittable flow version of the problem.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2017, 261 (1), pp.30 - 42. 〈10.1016/j.ejor.2017.01.051〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01665610
Contributeur : Bernard Fortz <>
Soumis le : jeudi 21 décembre 2017 - 14:30:38
Dernière modification le : mardi 3 juillet 2018 - 11:23:21

Fichier

PUMF.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Bernard Fortz, Luis Gouveia, Martim Joyce-Moniz. Models for the piecewise linear unsplittable multicommodity flow problems. European Journal of Operational Research, Elsevier, 2017, 261 (1), pp.30 - 42. 〈10.1016/j.ejor.2017.01.051〉. 〈hal-01665610〉

Partager

Métriques

Consultations de la notice

193

Téléchargements de fichiers

43