The conjugate gradient technique for certain quadratic network problems

Larry J. Leblanc

Naval Research Logistics Quarterly, 1976, vol. 23, issue 4, 597-602

Abstract: We consider a class of network flow problems with pure quadratic costs and demonstrate 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. Solution time for the largest problems (4,950 variables and 99 linear constraints) averaged 4 seconds on the CBC Cyber 70 Model 72 computer.

Date: 1976
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800230403

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:23:y:1976:i:4:p:597-602

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().