On the Convex Piecewise Linear Unsplittable Multicommodity Flow Problem

Session : SS1-3 / SS1 : Challenging Mixed-Integer Problems in Network Optimization
Vendredi 12 février 10:30 - 11:50 Salle : CI2-06
Bernard Fortz, Luis Gouveia et Martim Moniz

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.

Mots clés : Unsplittable multicommodity flows, Network optimization, Mixed-integer programming