CONJUGATE GRADIENT TECHNIQUE FOR CERTAIN QUADRATIC NETWORK PROBLEMS

The paper considers a class of network flow problems with pure quadratic costs and demonstrates that the conjugate gradient technique is highly effective for large-scale versions. It is shown that finding a saddle point for the Lagrangian of an m constraint, n variable network problem requires only the solution of an unconstrained quadratic programming problem with only m variables. It is demonstrated that the number of iterations for the conjugate gradient algorithm is substantially smaller than the number of variables or constraints in the (primal) network problem. Forty quadratic minimum-cost flow problems of various sizes up to 100 nodes are solved.

  • Corporate Authors:

    Office of Naval Research

    Department of the Navy, 800 North Quincy Street
    Arlington, VA  USA  22217
  • Authors:
    • LeBlanc, L J
  • Publication Date: 1976-12

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 00159697
  • Record Type: Publication
  • Source Agency: Engineering Index
  • Files: TRIS
  • Created Date: Apr 12 1978 12:00AM