A polyhedral approach to an integer multicommodity flow problem

in-this paper we propose a branch-and-cut algorithm for the exact solution of an integer multicommodity flow problem. This NP-hard problem finds impor tant applications in transportation, VLSI design, and telecommunications. W e consider alternative formulations of the problem and describe several cla sses of valid inequalities. We describe lifting procedures to extend a give n valid inequality for the problem with k commodities, to that having a lar ger number of commodities. We introduce a new large class of valid constrai nts,:the multi-handle comb inequalities. The polyhedral structure of the in teger multicommodity polytope:is studied in the case of unit edge capacitie s. We prove that this polytope is full dimensional and show that some multi -handle comb inequalities are facet defining. Also, the lifting procedures re facet preserving under certain conditions. A branch-and-cut algorithm fo r the exact solution of the problem is then outlined, and separation algori thms for the main classes of inequalities studied in the paper are proposed . Computational results on several classes of test problems an finally repo rted, with a comparison between two different formulations. (C) 2000 Elsevi er Science B.V. All rights reserved.