A COLUMN GENERATION AND PARTITIONING APPROACH FOR MULTICOMMODITY FLOWPROBLEMS

Multi-commodity network flow problems, prevalent in transportation, pr oduction and communication systems, can be characterized by a set of c ommodities and an underlying network. The objective is to flow the com modities through the network at minimum cost without exceeding are cap acities. In this paper, we present a partitioning solution procedure f or large-scale multi-commodity flow problems with many commodities, su ch as those encountered in the telecommunications industry. Using a cy cle-based multi-commodity formulation and column generation techniques , we solve a series of reduced-size linear programs in which a large n umber of constraints are relaxed. Each solution to a reduced-size prob lem is an improved basic dual feasible solution to the original proble m and, after a finite number of steps, an optimal multi-commodity flow solution is determined. Computational experience is gained in solving randomly generated test problems and message routing problems in the communications industry. The tests show that the procedure solves larg e-scale multi-commodity flow problems significantly faster than existi ng linear programming or column generation solution procedures.