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.
Similar content being viewed by others
References
R.K. Ahuja, T.L. Magnanti and J.B. Orlin,Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Englewood Cliffs, NJ, 1993).
A.I. Ali, D. Barnett, K. Farhangian, J.L. Kennington, B. Patty, B. Shetty, B. McCarl and P. Wong, Multicommodity network problems: Applications and computations, IIE Trans. 16(1984) 127–134.
A. Ali, R. Helgason, J. Kennington and H. Lall, Computational comparison among three multicommodity network flow algorithms, Oper. Res. 28(1980)995–1000.
A.A. Assad, Multicommodity network flows — computational experience, Working Paper OR-058-76, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA (1976).
A.A. Assad, Multicommodity network flows — a survey, Networks 8(1978)37–91.
A.A. Assad, Solving linear multicommodity flow problems,Proc. IEEE Int. Conf. on Circuits and Computers, Vol. 1 (1980) pp. 157–161.
C. Barnhart and Y. Sheffi, A network-based primal-dual heuristic for the solution of multicommodity network flow problems, Transportation Sci. 27(1993)102–117.
C. Barnhart, Dual-ascent methods for large-scale multi-commodity flow problems, Naval Res. Logist. Quart. 40(1993)305–324.
M.S. Bazaraa and J.J. Jarvis,Linear Programming and Network Flows (Wiley, New York, 1977).
G.B. Dantzig and P. Wolfe, Decomposition principle for linear programs, Oper. Res. 8(1960) 101–111.
G.B. Dantzig and R.M. Van Slyke, Generalized upper bounding techniques, J. Comput. Syst. Sci. 1(1967)213–226.
J. Druckerman, D. Silverman and K. Viaropulos, IBM optimization subroutine library guide and reference, Release 2, Document No. SC 23-0519-2, IBM, Kingston, NY (1991).
J.M. Farvolden and W.B. Powell, A primal partitioning solution for multicommodity network flow problems, Working Paper 90-04, Department of Industrial Engineering, University of Toronto, Canada (1990).
A.M. Geoffrion, Primal resource-directive approaches for optimizing non-linear decomposable systems, Oper. Res. 18(1970)375–403.
A. Gersht and A. Shulman, A new algorithm for the solution of the minimum cost multicommodity flow problem,Proc. 26th IEEE Conf. on Decision and Control (IEEE, New York, NY, 1987) pp. 748–758.
R.C. Grinold, Steepest ascent for a large-scale linear program, SIAM Rev. 14(1972)447–464.
J.K. Hartman and L.S. Lasdon, A generalized upper bounding algorithm for multicommodity network flow problems, Networks 1(1972)333–354.
K.L. Jones, I.J. Lustig, J.M. Farvolden and W.B. Powell, Multicommodity network flows: The impact of formulation on decomposition, Technical Report SOR 91-23, Department of Civil Engineering and Operations Research, Princeton University, Princeton, NJ (1992).
J. Karkazis and T.B. Boffey, A subgradient based optimal solution method for the multicommodity problem, in:Methods of Operations Research 40, eds. R.E. Burkard and T. Ellinger (Koenigstein, Anton Hain Meisenheim, 1981) pp. 339–344.
J.L. Kennington, Solving multicommodity transportation problems using a primal partitioning simplex technique, Naval Res. Logist. Quart. 24(1977)309–325.
J.L. Kennington, A survey of linear cost network flows, Oper. Res. 26(1978)209–236.
J.L. Kennington and R.V. Helgason,Algorithms for Network Programming (Wiley, New York, 1980).
J.L. Kennington and M. Shalaby, An effective subgradient procedure for minimal cost multicommodity flow problems, Manag. Sci. 23(1977)994–1004.
S. Lasdon,Optimization Theory for Large Systems (MacMillan, New York, 1970).
I.J. Lustig, R.E. Marsten and D.F. Shanno, Computational experience with a primal-dual interior point method for linear programming, Linear Algebra and Its Appl. 152(1991)191–222.
S.F. Maier, A compact inverse scheme applied to a multicommodity network with resource constraints, in:Optimization Methods for Resource Allocation, eds. R. Cottle and J. Krarup (English Universities Press, 1974) pp. 179–203.
C.J. McCallum, A generalized upper bounding approach to a communications network planning problem, Networks 7(1977)1–23.
M. Minoux,Mathematical Programming: Theory and Algorithms (Wiley, New York, 1986).
K. Ritter, A decomposition method for linear programming problems with coupling constraints and variables, Report No. 739, Mathematics Research Center, University of Wisconsin (1967).
J.T. Robacker, Notes on linear programming: Part XXXVII concerning multicommodity networks, RM-1799, The Rand Corporation, Santa Monica, CA (1956).
J.B. Rosen, Primal partition programming for block diagonal matrices, Numer. Mathematik 6(1964)250–260.
R. Saigal, Multicommodity flows in directed networks, ORC 67-38, Operations Research Center, University of California, Berkeley, CA (1967).
M. Sakarovitch and R. Saigal, An extension of generalized upper bounding techniques for structured linear programs, SIAM J. Appl. Math. 15(1967)906–914.
R. Schneur, Scaling algorithms for multi-commodity flow problems and network flow problems with side constraints, Ph.D. Dissertation, Department of Civil Engineering, MIT, Cambridge, MA (1991).
B. Shetty and R. Muthukrishnan, A parallel projection for the multicommodity network model, J. Oper. Res. Soc. 41(1990)837–842.
C. Swoveland, Decomposition algorithms for the multicommodity distribution problem, Working Paper No. 184, Western Management Science Institute, University of California, Los Angeles, CA (1971).
J.A. Tomlin, Minimum-cost multicommodity network flows, Oper. Res. 14(1966)45–51.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Barnhart, C., Hane, C.A., Johnson, E.L. et al. A column generation and partitioning approach for multi-commodity flow problems. Telecommunication Systems 3, 239–258 (1994). https://doi.org/10.1007/BF02110307
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02110307