An algorithm for solving quadratic network flow problems (Q1175149)

The authors describe an algorithm of the active-set-on-graph type for solving the network quadratic problem (1) \(\min(1/2)x^ TQx+p^ Tx\), subject to (2) \(Ex=b\), and (3) \(\ell\leq x\leq u\), where \(Q\) is a diagonal \(| A|\times| A|\) matrix with non-negative diagonal elements, \(p\in R^{| A|}\), \(E\) is the arc-node incidence matrix of a network \(G=(N,A)\), and \(\ell_ a\) and \(u_ a\) are the lower and upper capacity bounds on each arc \(a\in A\). The algorithm maintains (2) and uses an active set strategy to find a minimum cost flow which obeys (3). The algorithm terminates in a finite number of iterations. The performance of the proposed algorithm is compared to that of the convex simplex algorithm for networks.