Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems

We present a column-generation model and branch-and-price-and-cut algorithm for origin-destination integer multicommodity flow problems. The origin-de stination integer multicommodity flow problem is a constrained version of t he linear multicommodity flow problem in which flow of a commodity (defined in this case by an origin-destination pair) may use only one path from ori gin to destination. Branch-and-price-and-cut is a variant of branch-and-bou nd, with bounds provided by solving linear programs using column-and-cut ge neration at nodes of the branch-and-bound tree. Because our model contains one variable for each origin destination path, for every commodity, the lin ear programming relaxations at nodes of the branch-and-bound tree are solve d using column generation, i.e., implicit pricing of nonbasic variables to generate new columns or to prove LP optimality. We devise a new branching r ule that allows columns to be generated efficiently at each node of the bra nch-and-bound tree. Then, we describe cuts (cover inequalities) that can be generated at each node of the branch-and-bound tree. These cuts help to st rengthen the linear programming relaxation and to mitigate the effects of p roblem symmetry. We detail the implementation of our combined column-and-cu t generation method and present computational results for a set of test pro blems arising from telecommunications applications. We illustrate the value of our branching rule when used to find a heuristic solution and compare b ranch-and-price and branch-and-price-and-cut methods to find optimal soluti ons for highly capacitated problems.