IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v186y2011i1p119-14010.1007-s10479-011-0858-7.html
   My bibliography  Save this article

A least-squares minimum-cost network flow algorithm

Author

Listed:
  • Balaji Gopalakrishnan
  • Seunghyun Kong
  • Earl Barnes
  • Ellis Johnson
  • Joel Sokol

Abstract

Node-arc incidence matrices in network flow problems exhibit several special least-squares properties. We show how these properties can be leveraged in a least-squares primal-dual algorithm for solving minimum-cost network flow problems quickly. Computational results show that the performance of an upper-bounded version of the least-squares minimum-cost network flow algorithm with a special dual update operation is comparable to CPLEX Network and Dual Optimizers for solving a wide range of minimum-cost network flow problems. Copyright Springer Science+Business Media, LLC 2011

Suggested Citation

  • Balaji Gopalakrishnan & Seunghyun Kong & Earl Barnes & Ellis Johnson & Joel Sokol, 2011. "A least-squares minimum-cost network flow algorithm," Annals of Operations Research, Springer, vol. 186(1), pages 119-140, June.
    • Handle: RePEc:spr:annopr:v:186:y:2011:i:1:p:119-140:10.1007/s10479-011-0858-7
    DOI: 10.1007/s10479-011-0858-7
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-011-0858-7
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-011-0858-7?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. W. H. Cunningham, 1979. "Theoretical Properties of the Network Simplex Method," Mathematics of Operations Research, INFORMS, vol. 4(2), pages 196-208, May.
    2. Dimitri P. Bertsekas & Paul Tseng, 1988. "Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems," Operations Research, INFORMS, vol. 36(1), pages 93-114, February.
    3. Éva Tardos, 1986. "A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs," Operations Research, INFORMS, vol. 34(2), pages 250-256, April.
    4. Antonio Frangioni & Antonio Manca, 2006. "A Computational Study of Cost Reoptimization for Min-Cost Flow Problems," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 61-70, February.
    5. D. Klingman & A. Napier & J. Stutz, 1974. "NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems," Management Science, INFORMS, vol. 20(5), pages 814-821, January.
    6. Warren B. Powell, 1989. "A Review of Sensitivity Results for Linear Networks and a New Approximation to Reduce the Effects of Degeneracy," Transportation Science, INFORMS, vol. 23(4), pages 231-243, November.
    7. James B. Orlin, 1993. "A Faster Strongly Polynomial Minimum Cost Flow Algorithm," Operations Research, INFORMS, vol. 41(2), pages 338-350, April.
    8. C. O. Fong & V. Srinivasan, 1977. "Determining All Nondegenerate Shadow Prices for the Transportation Problem," Transportation Science, INFORMS, vol. 11(3), pages 199-222, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Holzhauser, Michael & Krumke, Sven O. & Thielen, Clemens, 2017. "A network simplex method for the budget-constrained minimum cost flow problem," European Journal of Operational Research, Elsevier, vol. 259(3), pages 864-872.
    2. László A. Végh, 2017. "A Strongly Polynomial Algorithm for Generalized Flow Maximization," Mathematics of Operations Research, INFORMS, vol. 42(1), pages 179-211, January.
    3. P. Beraldi & F. Guerriero & R. Musmanno, 1997. "Efficient Parallel Algorithms for the Minimum Cost Flow Problem," Journal of Optimization Theory and Applications, Springer, vol. 95(3), pages 501-530, December.
    4. Hochbaum, Dorit S., 2002. "Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations," European Journal of Operational Research, Elsevier, vol. 140(2), pages 291-321, July.
    5. ÇalIskan, Cenk, 2011. "A specialized network simplex algorithm for the constrained maximum flow problem," European Journal of Operational Research, Elsevier, vol. 210(2), pages 137-147, April.
    6. Prabhjot Kaur & Anuj Sharma & Vanita Verma & Kalpana Dahiya, 2022. "An alternate approach to solve two-level hierarchical time minimization transportation problem," 4OR, Springer, vol. 20(1), pages 23-61, March.
    7. Sedeno-Noda, A. & Gonzalez-Martin, C. & Gutierrez, J., 2005. "The biobjective undirected two-commodity minimum cost flow problem," European Journal of Operational Research, Elsevier, vol. 164(1), pages 89-103, July.
    8. Orlin, James B., 1953-, 1995. "A polynomial time primal network simplex algorithm for minimum cost flows," Working papers 3834-95., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    9. Sedeno-Noda, A. & Gonzalez-Martin, C., 2000. "The biobjective minimum cost flow problem," European Journal of Operational Research, Elsevier, vol. 124(3), pages 591-600, August.
    10. Kraft, Edwin R., 2002. "Scheduling railway freight delivery appointments using a bid price approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 36(2), pages 145-165, February.
    11. Lin, Chi-Jen & Wen, Ue-Pyng, 2003. "Sensitivity analysis of the optimal assignment," European Journal of Operational Research, Elsevier, vol. 149(1), pages 35-46, August.
    12. Raymond K. Cheung & Chuen-Yih Chen, 1998. "A Two-Stage Stochastic Network Model and Solution Methods for the Dynamic Empty Container Allocation Problem," Transportation Science, INFORMS, vol. 32(2), pages 142-162, May.
    13. Minghe Sun, 2005. "Warm-Start Routines for Solving Augmented Weighted Tchebycheff Network Programs in Multiple-Objective Network Programming," INFORMS Journal on Computing, INFORMS, vol. 17(4), pages 422-437, November.
    14. Ting Pong & Hao Sun & Ningchuan Wang & Henry Wolkowicz, 2016. "Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem," Computational Optimization and Applications, Springer, vol. 63(2), pages 333-364, March.
    15. Gregory A. Godfrey & Warren B. Powell, 2002. "An Adaptive Dynamic Programming Algorithm for Dynamic Fleet Management, II: Multiperiod Travel Times," Transportation Science, INFORMS, vol. 36(1), pages 40-54, February.
    16. Amitai Armon & Iftah Gamzu & Danny Segev, 2014. "Mobile facility location: combinatorial filtering via weighted occupancy," Journal of Combinatorial Optimization, Springer, vol. 28(2), pages 358-375, August.
    17. Festa, P. & Guerriero, F. & Laganà, D. & Musmanno, R., 2013. "Solving the shortest path tour problem," European Journal of Operational Research, Elsevier, vol. 230(3), pages 464-474.
    18. R. Fourer & H. Gassmann & J. Ma & R. Martin, 2009. "An XML-based schema for stochastic programs," Annals of Operations Research, Springer, vol. 166(1), pages 313-337, February.
    19. Mongeau, Marcel & Sartenaer, Annick, 1995. "Automatic decrease of the penalty parameter in exact penalty function methods," European Journal of Operational Research, Elsevier, vol. 83(3), pages 686-699, June.
    20. Shoshana Anily, 1996. "The vehicle‐routing problem with delivery and back‐haul options," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(3), pages 415-434, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:186:y:2011:i:1:p:119-140:10.1007/s10479-011-0858-7. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.