%0 Journal Article %1 cynthia1994column %A Barnhart, Cynthia %A Hane, Christopher A. %A Johnson, Ellis L. %A Sigismondi, Gabriele %D 1994 %J Telecommunication Systems %K flow multicommodity unread %N 3 %P 239--258 %T A column generation and partitioning approach for multi-commodity flow problems %U http://dx.doi.org/10.1007/BF02110307 %V 3 %X Multi-commodity network flow problems, prevalent in transportation, production and communication systems, can be characterized by a set of commodities and an underlying network. The objective is to flow the commodities through the network at minimum cost without exceeding arc capacities. In this paper, we present a partitioning solution procedure for large-scale multi-commodity flow problems with many commodities, such as those encountered in the telecommunications industry. Using a cycle-based multi-commodity formulation and column generation techniques, we solve a series of reduced-size linear programs in which a large number of constraints are relaxed. Each solution to a reduced-size problem is an improved basic dual feasible solution to the original problem 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 large-scale multi-commodity flow problems significantly faster than existing linear programming or column generation solution procedures. ER -

@article{cynthia1994column, abstract = {Multi-commodity network flow problems, prevalent in transportation, production and communication systems, can be characterized by a set of commodities and an underlying network. The objective is to flow the commodities through the network at minimum cost without exceeding arc capacities. In this paper, we present a partitioning solution procedure for large-scale multi-commodity flow problems with many commodities, such as those encountered in the telecommunications industry. Using a cycle-based multi-commodity formulation and column generation techniques, we solve a series of reduced-size linear programs in which a large number of constraints are relaxed. Each solution to a reduced-size problem is an improved basic dual feasible solution to the original problem 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 large-scale multi-commodity flow problems significantly faster than existing linear programming or column generation solution procedures. ER -}, added-at = {2010-04-03T23:34:42.000+0200}, author = {Barnhart, Cynthia and Hane, Christopher A. and Johnson, Ellis L. and Sigismondi, Gabriele}, biburl = {https://www.bibsonomy.org/bibtex/2c94b29536282fa60336aa4024941d31c/meridius}, description = {SpringerLink - Journal Article}, interhash = {fd12f927df9aaddf84f829fd0ec48777}, intrahash = {c94b29536282fa60336aa4024941d31c}, journal = {Telecommunication Systems}, keywords = {flow multicommodity unread}, month = {#oct#}, number = 3, pages = {239--258}, timestamp = {2010-04-03T23:40:06.000+0200}, title = {A column generation and partitioning approach for multi-commodity flow problems}, url = {http://dx.doi.org/10.1007/BF02110307}, volume = 3, year = 1994 }