Computational development of a lagrangian dual approach for quadratic networks

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.