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  United States  22217
• Authors:
  • LeBlanc, L J
• Publication Date: 1976-12

Media Info

• Serial:
  • Naval Research Logistics Quarterly
  • Volume: 23
  • Issue Number: 4
  • Publisher: Department of the Navy

Subject/Index Terms

• TRT Terms: Algorithms; Constraints; Iterative methods; Lagrangian functions; Mathematical analysis; Network analysis (Planning); Networks; Nonlinear programming; Problem identification; Routes; Scheduling; Traffic flow; Transportation; Urban transportation; Variables
• Uncontrolled Terms: Network flows
• Old TRIS Terms: Conjugate functions; Conjugate gradient technique; Network problems; Quadratic forms; Quadratic networks; Route analysis
• Subject Areas: Operations and Traffic Management; Planning and Forecasting; Transportation (General);

Filing Info

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