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