A modified subgradient algorithm for Lagrangean relaxation

Despite nonmonotonic properties, weak convergence performance and possible erratic behavior, the standard subgradient optimization method is still one of the most widely adopted algorithms for solving the Lagrangean dual problem in practical applications. Several attempts have been made recently to improve the algorithm performance. In this paper we present a modified algorithm which employs a variable target value for the step length determination and considers a direction given by a conic combination of possibly all previously generated subgradients. Computational experience of the proposed algorithm on Traveling Salesman and Assignment problems of different sizes is reported.