Titre :

Models for the piecewise linear unsplittable multicommodity flow problems

Auteur(s) :

Fortz, Bernard [Auteur]
Graphes et Optimisation Mathématique [Bruxelles] [GOM]
Integrated Optimization with Complex Structure [INOCS]
Gouveia, Luís [Auteur]
Centro de Investigação Operacional [CIO]
Joyce-Moniz, Martim [Auteur]
Graphes et Optimisation Mathématique [Bruxelles] [GOM]

Titre de la revue :

European Journal of Operational Research

Pagination :

30 - 42

Éditeur :

Elsevier

Date de publication :

2017-08

ISSN :

0377-2217

Mot(s)-clé(s) en anglais :

OR in telecommunications
Networks
Unsplittable Flows
Integer programming
Combinatorial optimization

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL