Skip to main content
SpringerLink
Log in

Solving Difficult Multicommodity Problems with a Specialized Interior-Point Algorithm

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

Due to recent advances in the development of linear programming solvers, some of the formerly considered difficult multicommodity problems can today be solved in few minutes, even faster than with specialized methods. However, for other kind of multicommodity instances, general linear solvers can still be quite inefficient. In this paper we will give an overview of the current state-of-the-art in solving large-scale multicommodity problems, comparing an specialized interior-point algorithm with CPLEX 6.5 in the solution of difficult multicommodity problems of up to 1 million of variables and 300,000 constraints.

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

  • Ahuja, R.K., T.L. Magnanti, and J.B. Orlin. (1993). Network Flows. New York: Prentice Hall.

    Google Scholar 

  • Ali, A. and J.L. Kennington. (1977). “Mnetgen Program Documentation.” Technical Report 77003, Department of Ind. Eng. and Operations Research, Southern Methodist University, Dallas.

    Google Scholar 

  • Bienstock, D. (1999). “Approximately Solving Large-Scale Linear Programs. I: Strengthening Lower Bounds and Accelerating Convergence.” CORC Report 1999-1, Columbia University, New York.

    Google Scholar 

  • Bixby, R.E., M. Fenelon, Z. Gu, E. Rothberg, and R. Wunderling. (2000). “MIP: Theory and Practice -Closing the Gap.” In M.J.D. Powell and S. Scholtes (eds.), System Modelling and Optimization. Methods, Theory and Applications. Dordrecht: Kluwer, pp. 19–49.

    Google Scholar 

  • Castro, J. (2000a). “A Specialized Interior-Point Algorithm for Multicommodity Network Flows.” SIAM Journal on Optimization 10(3), 852–877.

    Google Scholar 

  • Castro, J. (2000b). “Computational Experience with a Parallel Implementation of an Interior-Point Algorithm for Multicommodity Flows.” In M.J.D. Powell and S. Scholtes (eds.), System Modelling and Optimization. Methods, Theory and Applications. Dordrecht: Kluwer, pp. 79–95.

    Google Scholar 

  • Castro, J. and A. Frangioni. (2001). “A Parallel Implementation of an Interior-Point Algorithm for Multicommodity Network Flows.” In J.M. Palma, J. Dongarra, and V. Hernández (eds.), Vector and Parallel Processing, Lecture Notes in Computer Sciences, Vol. 1981. Berlin: Springer, pp. 301–315.

    Google Scholar 

  • Castro, J. and N. Nabona. (1996). “An Implementation of Linear and Nonlinear Multicommodity Network Flows.” European Journal of Operations Research 92, 37–53.

    Google Scholar 

  • Carolan, W.J., J.E. Hill, J.L. Kennington, S. Niemi, and S.J. Wichmann. (1990). “An Empirical Evaluation of the KORBX Algorithms for Military Airlift Applications.” Operations Research 38, 240–248.

    Google Scholar 

  • Chardaire, P. and A. Lisser. (1999). “Simplex and Interior Point Specialized Algorithms for Solving Non-Oriented Multicommodity Flow Problems.” To appear in Operations Research.

  • Chardaire, P. and A. Lisser. (2002). “Minimum Cost Multicommodity Flow.” In M. Pardalos and M. Resende (eds.), Handbook of Applied Optimization. Oxford: Oxford University Press, pp. 404–422.

    Google Scholar 

  • Frangioni, A. (1997). “tDual Ascent Methods and Multicommodity Flows.” Ph.D. Thesis TD 5/97, Dip. di Informatica, Univ. di Pisa.

  • Frangioni, A. and G. Gallo. (1999). “A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min Cost Flow Problems.” INFORMS Journal on Computing 11(4), 370–393.

    Google Scholar 

  • Goffin, J.-L., J. Gondzio, R. Sarkissian, and J.-P. Vial. (1996). “Solving Nonlinear Multicommodity Flow Problems by the Analytic Center Cutting Plane Method.” Mathematical Programming 76, 131–154.

    Google Scholar 

  • Goldberg, A.V., J.D. Oldham, S. Plotkin, and C. Stein. (1998). “An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow.” In R.E. Bixby, E.A. Boyd, and R.Z. Ríos-Mercado (eds.), Proceedings of the 6th International Integer Programming and Combinatorial Optimization Conference. Lecture Notes in Computer Sciences, Vol. 1412. Berlin: Springer.

    Google Scholar 

  • Golub, G.H. and C.F. Van Loan. (1996). Matrix Computations, 3rd. ed. Baltimore, MD: Johns Hopkins University Press.

    Google Scholar 

  • Gondzio, J. (1996). “Multiple Centrality Corrections in a Primal-Dual Method for Linear Programming.” Computational Optimization and Applications 6, 137–156.

    Google Scholar 

  • Gondzio, J. and M. Makowski. (1995). “Solving a Class of LP Problems with a Primal-Dual Logarithmic Barrier Method.” European Journal of Operations Research 80, 184–192.

    Google Scholar 

  • Grigoriadis, M.D. and L.G. Khachiyan. (1995). “An Exponential-Function Reduction Method for Block-Angular Convex Programs.” Networks 26, 59–68.

    Google Scholar 

  • ILOG CPLEX. (1999). ILOG CPLEX 6.5 Reference Manual Library. ILOG.

  • Kamath, A.P., N.K. Karmarkar, and K.G. Ramakrishnan. (1993). “Computational and Complexity Results for an Interior Point Algorithm on Multicommodity Flow Problems.” Technical Report TR-21/93, Dip. di Informatica, Univ. di Pisa, Italy, pp. 116–122.

    Google Scholar 

  • Mamer, J. and R. McBride. (2000). “A Decomposition Bases Pricing Procedure for Large Scale Linear Programs: An Application to the Linear Multicommodity Flow Problem.” Management Science 46, 693–709.

    Google Scholar 

  • McBride, R.D. (1998). “Progress Made in Solving the Multicommodity Flow Problem.” SIAM Journal on Optimization 8, 947–955.

    Google Scholar 

  • Mehrotra, S. (1992). “On the Implementation of a Primal-Dual Interior Point Method.” SIAM Journal on Optimization 2, 575–601.

    Google Scholar 

  • Ng, E. and B.W. Peyton. (1993). “Block Sparse Cholesky Algorithms on Advanced Uniprocessor Computers.” SIAM Journal on Scientific Computing 14, 1034–1056.

    Google Scholar 

  • Portugal, L., M.G.C. Resende, G. Veiga, G., and J. Júdice. (1997). “A Truncated Interior-Point Method for the Solution of Minimum Cost Flow Problems on an Undirected Multicommodity Flow Network.” In Proceedings of First Portuguese National Telecommunications Conference, pp. 381–384 (in Portuguese).

  • Resende, M.G.C. and G. Veiga. (1993). “An Implementation of the Dual Affine Scaling Algorithm for Minimum Cost Flow on Bipartite Uncapacitated Networks.” SIAM Journal on Optimization 3, 516–537.

    Google Scholar 

  • Schultz, G.L. and R.R. Meyer. (1991). “An Interior Point Method for Block Angular Optimization.” SIAM Journal on Optimization 1, 583–602.

    Google Scholar 

  • Wright, S.J. (1996). Primal-Dual Interior-Point Methods. Philadelphia, PA: SIAM.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Statistics and Operations Research, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028, Barcelona, Spain

    Jordi Castro

Authors
  1. Jordi Castro
    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

Castro, J. Solving Difficult Multicommodity Problems with a Specialized Interior-Point Algorithm. Annals of Operations Research 124, 35–48 (2003). https://doi.org/10.1023/B:ANOR.0000004761.99649.a5

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/B:ANOR.0000004761.99649.a5

Search

Navigation