The problem of determining a minimal spanning tree, subject to side constraints, arises frequently in the design of computer communication networks and pipeline systems. In this paper, a specific case of the general problem, with only one side constraint of the knapsack type is considered. For its solution, a new Lagrangian relaxation, based on a reformulation of the problem through the utilization of duplication of variables, is developed. Theoretical and computational results, indicating the superiority of the new approach, over the straightforward Lagrangian relaxation, are presented. Finally, the possibility of adopting the approach for the solution of more general problems is demonstrated.

We describe a solution procedure for nonseparable nonlinear programming problems over Cartesian product sets. Problems of this type frequently arise in transportation planning and in the analysis and design of computer communication networks. The basic algorithmic concept is to induce separability by linearizing the nonseparable part of the objective function, This algorithm and the well-known Frank-Wolfe method have many similarities. It is illustrated by a small numerical example.

This paper presents a new solution technique for the traffic assignment problem. The approach is based on an iteratively improved nonlinear and separable approximation of the originally nonseparable objective function, and resembles the Frank-Wolfe algorithm in the sense that the subproblem separates with respect to commodities. Since the single-commodity subproblems are strictly convex, the new algorithm will not suffer from the poor convergence behaviour of the Frank-Wolfe algorithm, which is a consequence of the extreme solutions of its linear subproblems. The solution method is outlined along with convergence results, and a dual approach to the solution of the strictly convex subproblems is described. The performance of the algorithm is illustrated with two numerical examples

This paper presents a strongly polynomial algorithm for a special concave minimization problem which is a production-transportation problem involving concave production cost and linear transportation cost. The method used is characterized by a systematic exploitation of the specific structure of the problem: monotonicity property of the objective function, sparse nonconvexity (possibility of locating the nonconvexity in a low dimensional space) and combinatorial properties inherited from the network structure. Incidentally, a special parametric transportation problem is also studied

We consider two special cases of the Minimum Concave Cost Network Flow Problem (MCCNFP);the single source uncapacitated MCCNFP where all arc costs, except two, are linear and the uncapacitated MCCNFP with 2 sources and 1 nonlinear arc cost. Due to their specific structure these problems can he solved by efficient strongly polynomial time algorithms. More specifically, the algorithms developed have running times polynomial in the number of nodes and arcs and the number of sinks