On a particular quadratic network problem

Let c(x), d(x) and h(x) be linear functions defined over a convex polyhedron X = {x | Ax = r and 0 ⩽ x ⩽ u }, where A is the node-edge incidence matrix of a given network. Let f(x) = c(x)d(x) + h(x) be a (particular) quadratic function which we intend to minimize over X. In this paper we use the theory of multiobjective programming do develop algorithms for the semidefinite positive case (f(x) = ϱd(x)]² + h(x) and ϱ is a strictly postive real constant) and the semidefinite negative case (f(x) = ϱd(x)]² + h (x) and ϱ is a strictly negative real constant). A special indefinite case (h(x) is constant over X) is also studied.In the proposed algorithms, basic solutions are used in all the interactions with possible exception for the last one. Moreover only the concepts of the simplex method are used; consequently these algorithms can be used even when A is not the node-edge incidence matrix of a network. However they are particularly attractive for the network case. In fact, network basic solutions are efficiently manipulated when appropriated data structures are used in the computational implementation of an algorithm.