A technique for speeding up the solution of the Lagrangean dual

The authors propose techniques for the solution of the LP relaxation and the Lagrangean dual in combinatorial optimization and nonlinear programming problems. The present techniques find the optimal solution value and the optimal dual multipliers of the LP relaxation and the Lagrangean dual in polynomial time using as a subroutine either the Ellipsoid algorithm or the recent algorithm of Vaidya. Moreover, in problems of a certain structure the techniques find not only the optimal solution value, but the solution as well. The present techniques lead to significant improvements in the theoretical running time compared with previously known methods (interior point methods, Ellipsoid algorithm, Vaidya’s algorithm). The authors use their method to the solution of the LP relaxation and the Lagrangean dual of several classical combinatorial problems, like the traveling salesman problem, the vehicle routing problem, the Steiner tree problem, the k-connected problem, multicommodity flows, network design problems, network flow problems with side constraints, facility location problems, K-polymatroid intersection, multiple item capacitated lot sizing problem, and stochastic programming. In all these problems the present techniques significantly improve the theoretical running times and yield the fastest way to solve them.