Skip to main content
SpringerLink
Log in

A column generation and partitioning approach for multi-commodity flow problems

  • Published:
Telecommunication Systems Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R.K. Ahuja, T.L. Magnanti and J.B. Orlin,Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Englewood Cliffs, NJ, 1993).

    Google Scholar 

  2. 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.

    Google Scholar 

  3. A. Ali, R. Helgason, J. Kennington and H. Lall, Computational comparison among three multicommodity network flow algorithms, Oper. Res. 28(1980)995–1000.

    Google Scholar 

  4. A.A. Assad, Multicommodity network flows — computational experience, Working Paper OR-058-76, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA (1976).

    Google Scholar 

  5. A.A. Assad, Multicommodity network flows — a survey, Networks 8(1978)37–91.

    Google Scholar 

  6. A.A. Assad, Solving linear multicommodity flow problems,Proc. IEEE Int. Conf. on Circuits and Computers, Vol. 1 (1980) pp. 157–161.

    Google Scholar 

  7. 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.

    MathSciNet  Google Scholar 

  8. C. Barnhart, Dual-ascent methods for large-scale multi-commodity flow problems, Naval Res. Logist. Quart. 40(1993)305–324.

    Google Scholar 

  9. M.S. Bazaraa and J.J. Jarvis,Linear Programming and Network Flows (Wiley, New York, 1977).

    Google Scholar 

  10. G.B. Dantzig and P. Wolfe, Decomposition principle for linear programs, Oper. Res. 8(1960) 101–111.

    Google Scholar 

  11. G.B. Dantzig and R.M. Van Slyke, Generalized upper bounding techniques, J. Comput. Syst. Sci. 1(1967)213–226.

    Google Scholar 

  12. 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).

    Google Scholar 

  13. 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).

    Google Scholar 

  14. A.M. Geoffrion, Primal resource-directive approaches for optimizing non-linear decomposable systems, Oper. Res. 18(1970)375–403.

    Google Scholar 

  15. 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.

    Google Scholar 

  16. R.C. Grinold, Steepest ascent for a large-scale linear program, SIAM Rev. 14(1972)447–464.

    Article  Google Scholar 

  17. J.K. Hartman and L.S. Lasdon, A generalized upper bounding algorithm for multicommodity network flow problems, Networks 1(1972)333–354.

    Google Scholar 

  18. 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).

    Google Scholar 

  19. 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.

    Google Scholar 

  20. J.L. Kennington, Solving multicommodity transportation problems using a primal partitioning simplex technique, Naval Res. Logist. Quart. 24(1977)309–325.

    Google Scholar 

  21. J.L. Kennington, A survey of linear cost network flows, Oper. Res. 26(1978)209–236.

    Google Scholar 

  22. J.L. Kennington and R.V. Helgason,Algorithms for Network Programming (Wiley, New York, 1980).

    Google Scholar 

  23. J.L. Kennington and M. Shalaby, An effective subgradient procedure for minimal cost multicommodity flow problems, Manag. Sci. 23(1977)994–1004.

    Google Scholar 

  24. S. Lasdon,Optimization Theory for Large Systems (MacMillan, New York, 1970).

    Google Scholar 

  25. 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.

    Article  Google Scholar 

  26. 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.

  27. C.J. McCallum, A generalized upper bounding approach to a communications network planning problem, Networks 7(1977)1–23.

    Google Scholar 

  28. M. Minoux,Mathematical Programming: Theory and Algorithms (Wiley, New York, 1986).

    Google Scholar 

  29. K. Ritter, A decomposition method for linear programming problems with coupling constraints and variables, Report No. 739, Mathematics Research Center, University of Wisconsin (1967).

  30. J.T. Robacker, Notes on linear programming: Part XXXVII concerning multicommodity networks, RM-1799, The Rand Corporation, Santa Monica, CA (1956).

    Google Scholar 

  31. J.B. Rosen, Primal partition programming for block diagonal matrices, Numer. Mathematik 6(1964)250–260.

    Article  Google Scholar 

  32. R. Saigal, Multicommodity flows in directed networks, ORC 67-38, Operations Research Center, University of California, Berkeley, CA (1967).

    Google Scholar 

  33. M. Sakarovitch and R. Saigal, An extension of generalized upper bounding techniques for structured linear programs, SIAM J. Appl. Math. 15(1967)906–914.

    Article  Google Scholar 

  34. 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).

    Google Scholar 

  35. B. Shetty and R. Muthukrishnan, A parallel projection for the multicommodity network model, J. Oper. Res. Soc. 41(1990)837–842.

    Google Scholar 

  36. C. Swoveland, Decomposition algorithms for the multicommodity distribution problem, Working Paper No. 184, Western Management Science Institute, University of California, Los Angeles, CA (1971).

    Google Scholar 

  37. J.A. Tomlin, Minimum-cost multicommodity network flows, Oper. Res. 14(1966)45–51.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Civil and Environmental Engineering, Massachusetts Institute of Technology, 02139-4307, Cambridge, MA, USA

    Cynthia Barnhart

  2. Faculty of Commerce and Business Administration, University of British Columbia, Vancouver, British Columbia, Canada

    Christopher A. Hane

  3. School of Industrial and Systems Engineering, Georgia Institute of Technology, 30332-0205, Atlanta, GA, USA

    Ellis L. Johnson

  4. TNT Traco, Torino-Corso Romania, Italy

    Gabriele Sigismondi

Authors
  1. Cynthia Barnhart
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Christopher A. Hane
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ellis L. Johnson
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Gabriele Sigismondi
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02110307

Keywords

Search

Navigation