The projected pairwise multicommodity flow polyhedron

AbstractThe object of this paper is a simple characterization of the vertices and extreme rays of the undirected multicommodity flow polyhedron F, which has one variable for each channel. This polyhedron is seen as a linear projection of the high-dimensional directed multicommodity flow polyhedron F, which has variables corresponding to each possible tuple of the form (channel, direction, origin, destination). Along with the characterization of vertices and rays of F, a computationally verifiable necessary condition for the vertices is given. It is shown that no polynomially bounded analytical description of F exists, by exhibiting exponentially many facets of F