Skip to main content
SpringerLink
Log in

Exploiting special structure in a primal—dual path-following algorithm

  • Published:
Mathematical Programming Submit manuscript

Abstract

A primal-dual path-following algorithm that applies directly to a linear program of the form, min{c t x∣Ax = b, Hx ⩽u, x ⩾ 0,x ∈ ℝn}, is presented. This algorithm explicitly handles upper bounds, generalized upper bounds, variable upper bounds, and block diagonal structure. We also show how the structure of time-staged problems and network flow problems can be exploited, especially on a parallel computer. Finally, using our algorithm, we obtain a complexity bound of O(\(\sqrt n \) ds 2 log(nk)) fortransportation problems withs origins,d destinations (s <d), andn arcs, wherek is the maximum absolute value of the input data.

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. A.V. Aho, J.E. Hopcroft and J.D. Ullman,The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974).

    Google Scholar 

  2. E.R. Barnes, “A variation on Karmarkar's algorithms for linear programming,”Mathematical Programming 36 (1986) 174–182.

    Google Scholar 

  3. J.R. Birge and L. Qi, “Computing block-angular Karmarkar projections with applications to stochastic programming,”Management Science 34 (1988) 1472–1479.

    Google Scholar 

  4. I.C. Choi, C.L. Monma and D.F. Shanno, “Further development on primal-dual interior point method,”ORSA Journal on Computing 2(4) (1990) 304–311.

    Google Scholar 

  5. I.I. Dikin, “Iterative solution of problems of linear and quadratic programming,”Doklady Akademii Nauk USSR 174 (1967). [Translated in:Soviet Mathematics Doklady 8 (1967) 674–675.]

  6. C.M. Fiduccia and R.M. Mattheyses, “A linear-time heuristic for improving network partitions,”Proceedings 19th Design Automation Conference (1982) 175–181.

  7. R.M. Freund, “Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function,”Mathematical Programming 51 (1991) 203–222.

    Google Scholar 

  8. P.E. Gill, W. Murray and M.A. Saunders, “A single-phase dual barrier algorithm for linear programming,” Technical Report SOL 88-00, Systems Optimization Laboratory, Department of Operations Research, Stanford University (Stanford, CA, 1988).

    Google Scholar 

  9. P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin and M.H. Wright, “On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method,”Mathematical Programming 36 (1986) 183–209.

    Google Scholar 

  10. D. Goldfarb and M.J. Todd, “Linear Programming” in: G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd, eds.,Handbook in Operations Research and Management Science, Vol. 1, Optimization (North-Holland, Amsterdam, 1989).

    Google Scholar 

  11. G.H. Golub and C.F. Van Loan,Matrix Computations (The Johns Hopkins University Press, Baltimore, MD, 1983).

    Google Scholar 

  12. C. Gonzaga, “An algorithm for solving linear programming in O(n 3 L) operations,” in: N. Megiddo, ed.,Advances in Mathematical Programming—Interior Point and Related Methods (Springer, Berlin, 1989). Chapter 1.

    Google Scholar 

  13. S. Kapoor and P.M. Vaidya, “Speeding up Karmarker's algorithm for multicommodity flows,” manuscript, Department of Computer Sciences, University of Illinois at Urbana-Champaign (Urbana, IL, 1988).

    Google Scholar 

  14. N.K. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.

    Google Scholar 

  15. N.K. Karmarkar and K.G. Ramakrishnan, “Implementation and computational results of the Karmarkar algorithm for linear programming, using an iterative method for computing projections,” Technical Memorandum No. 11211-891011-10TM, AT&T Bell Laboratories (Murray Hill, NJ, 1989).

    Google Scholar 

  16. B.W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,”Bell System Technical Journal 49 (1970) 291–307.

    Google Scholar 

  17. 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 Applications 152 (1991) 191–222.

    Google Scholar 

  18. K. Masuzawa, S. Mizuno, and M. Mori, “A polynomial time interior point algorithm for minimum cost flow problems,”Journal of the Operations Research Society of Japan 33 (1990) 157–167.

    Google Scholar 

  19. S. Mehrotra, “On the implementation of a primal—dual interior point method,” Technical Report 90-03, Department of Industrial Engineering and Management Sciences, Northwestern University (Evanston, IL, 1990).

    Google Scholar 

  20. S. Mizuno and K. Masuzawa, “Polynomial time interior point algorithms for transportation problems,”Journal of the Operations Research Society of Japan 32 (1989) 371–382.

    Google Scholar 

  21. R.C. Monteiro and I. Adler, “Interior path-following primal-dual algorithms. Part 1: Linear programming,”Mathematical Programming 44 (1988) 27–41.

    Google Scholar 

  22. D. Moore, “A round-robin parallel partitioning algorithm,” TR 88-916, Department of Computer Science, Cornell University (Ithaca, NY, 1988).

    Google Scholar 

  23. J. Renegar, “A polynomial-time algorithm, based on Newton's method, for linear programming,”Mathematical Programming 40 (1988) 59–93.

    Google Scholar 

  24. R.E. Tarjan, “Depth first search and linear graph algorithms,”SIAM Journal of Computing 1(2) (1972) 146–160.

    Google Scholar 

  25. M.J. Todd, “Exploiting special structure in Karmarkar's linear programming algorithm,”Mathematical Programming 41 (1988) 97–113.

    Google Scholar 

  26. Y. Ye, “A O(n 3 L) potential reduction algorithm for linear programming,”Mathematical Programming 50 (1991) 239–258.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial Engineering, The Wichita State State University, Wichita, KS, USA

    In Chan Choi

  2. Department of Industrial Engineering and Operations Research, Columbia University, Seeley W. Mudd Building, 10027, New York, NY, USA

    Donald Goldfarb

Authors
  1. In Chan Choi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Donald Goldfarb
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was supported in part by NSF Grants DMS-85-12277 and CDR-84-21402 and by ONR Contract N00014-87-K-0214.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Choi, I.C., Goldfarb, D. Exploiting special structure in a primal—dual path-following algorithm. Mathematical Programming 58, 33–52 (1993). https://doi.org/10.1007/BF01581258

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Key words

Search

Navigation