Integral polyhedra related to integer multicommodity flows on a cycle Original Research Article

The integer multicommodity flow problem on a cycle (IMFC) is to find a feasible integral routing of given demands between image pairs of nodes on a link-capacitated undirected cycle, which is known to be polynomially solvable. Along with integral polyhedra related to IMFC, this paper shows that there exists a linear program, with a polynomial number of variables and constraints, which solves IMFC. Using the results, we also present a compact polyhedral description of the convex hull of feasible solutions to a certain class of instances of IMFC whose number of variables and constraints is image, which in turn means that there exists a non-trivial special case for which a minimum cost integer multicommodity flow problem can be solved in polynomial time.