Premium
Computational development of a lagrangian dual approach for quadratic networks
Author(s) -
Ventura Jose A.
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210407
Subject(s) - line search , mathematical optimization , quadratic equation , conjugate gradient method , mathematics , quadratic programming , flow network , dual (grammatical number) , knapsack problem , computer science , algorithm , art , geometry , computer security , literature , radius
A Lagrangian dual approach for large‐scale quadratic programs due to Lin and Pang is adapted to the quadratic cost network flow problem. The unconstrained dual problem is solved iteratively by combining conjugate gradient directions with finite line‐search methods. By exploiting the graph structure, matrix and vector operations are streamlined so that the technique can be used for large problems. A computational study of randomly generated networks with up to 500 nodes and 20,000 arcs gives a comparison between combinations of different conjugate direction formulas with three line‐search techniques. The results demonstrate the clear superiority of the Polak‐Ribiere direction formula combined with a variant of a line‐search technique originally developed by Bitran and Hax for convex knapsack problems.