An algorithm for solving quadratic network flow problems

DOI10.1016/0893-9659(91)90056-2MaRDI QIDQ1175149zbMATH OpenOpenAlexWikidataFDO

Authors C. J. Goh, Natashia Boland, Alistair Mees

Publication date 25 June 1992

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0893-9659(91)90056-2

zbMATH Keywords

active set strategyconvex simplex algorithmminimum cost flownetwork quadratic problem

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Deterministic network models in operations research (90B10) Quadratic programming (90C20) Programming involving graphs or networks (90C35)

Review text

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.

Recommendations

• An Algorithm for Non-Linear Network Programming: Implementation, Results and Comparisons
• Analytic efficient solution set for bi-criteria quadratic network programs
• Application of the dual active set algorithm to quadratic network optimization
• A polynomial algorithm for minimum quadratic cost flow problems
• Computational development of a lagrangian dual approach for quadratic networks

Cites work

• A scaled reduced gradient algorithm for network flow problems with convex separable costs
• Dioïds and semirings: Links to fuzzy sets and other applications
• scientific article; zbMATH DE number 3961334 (Why is no real title available?)
• scientific article; zbMATH DE number 3718474 (Why is no real title available?)
• scientific article; zbMATH DE number 3791941 (Why is no real title available?)
• scientific article; zbMATH DE number 3559405 (Why is no real title available?)
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Network flow, transportation and scheduling. Theory and algorithms

Cited in

(7)

• A faster version of the ASG algorithm
• Application of the dual active set algorithm to quadratic network optimization
• scientific article; zbMATH DE number 4112385 (Why is no real title available?)
• Analytic efficient solution set for bi-criteria quadratic network programs
• scientific article; zbMATH DE number 2206640 (Why is no real title available?)
• Quadratic cost flow and the conjugate gradient method
• A polynomial algorithm for minimum quadratic cost flow problems

This page was built for publication: An algorithm for solving quadratic network flow problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1175149)