On the convex piecewise linear unsplittable multicommodity flow problem

Bernard Fortz 1, 2 Luis Gouveia 3 Martim Joyce-Moniz 4
1 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 : We consider the problem of finding the cheapest routing for a set of commodities over a directed graph, such that: i) each commodity flows through a single path, ii) the routing cost of each arc is given by a convex piecewise linear function of the load (i.e. the total flow) traversing it. We propose a new mixed-integer programming formulation for this problem. This formulation gives a complete description of the associated polyhedron for the single commodity case, and produces very tight linear programming bounds for the multi-commodity case.
Type de document :
Communication dans un congrès
2016 12th International Conference on the Design of Reliable Communication Networks (DRCN), Mar 2016, Paris, France. pp.9--13, 2016, 〈10.1109/DRCN.2016.7470829〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01410555
Contributeur : Bernard Fortz <>
Soumis le : mardi 6 décembre 2016 - 17:03:00
Dernière modification le : mardi 3 juillet 2018 - 11:42:02

Identifiants

Collections

Citation

Bernard Fortz, Luis Gouveia, Martim Joyce-Moniz. On the convex piecewise linear unsplittable multicommodity flow problem. 2016 12th International Conference on the Design of Reliable Communication Networks (DRCN), Mar 2016, Paris, France. pp.9--13, 2016, 〈10.1109/DRCN.2016.7470829〉. 〈hal-01410555〉

Partager

Métriques

Consultations de la notice

154