Lagrangian Relaxations on Networks by e‐Subgradient Methods

The efficiency of the network flow techniques can be exploited in the solution of nonlinearly constrained network flow problems by means of approximate subgradient methods. The idea is to solve the dual problem by using ϵ‐subgradient methods, where the dual function is estimated by minimizing approximately a Lagrangian function, which relaxes the side constraints and is subject only to network constraints. In this paper, convergence results for some kind of ϵ‐subgradient methods are put forward. Moreover, in order to evaluate the quality of the solution and the efficiency of these methods some of them have been implemented and their performances computationally compared with codes that are able to solve the proposed test problems.