A TECHNIQUE FOR SPEEDING-UP THE SOLUTION OF THE LAGRANGEAN DUAL

We propose techniques for the solution of the LP relaxation and the La grangean dual in combinatorial optimization and nonlinear programming problems. Our techniques find the optimal solution value and the optim al dual multipliers of the LP relaxation and the Lagrangean dual in po lynomial time using as a subroutine either the Ellipsoid algorithm or the recent algorithm of Vaidya. Moreover, in problems of a certain str ucture our techniques find not only the optimal solution value, but th e solution as well. Our techniques lead to significant improvements in the theoretical running time compared with previously known methods ( interior point methods, Ellipsoid algorithm, Vaidya's algorithm). We u se our method to the solution of the LP relaxation and the Langrangean dual of several classical combinatorial problems, like the traveling salesman problem, the vehicle routing problem, the Steiner tree proble m, the k-connected problem, multicommodity flows, network design probl ems, network flow problems with side constraints, facility location pr oblems, K-polymatroid intersection, multiple item capacitated lot sizi ng problem, and stochastic programming. In all these problems our tech niques significantly improve the theoretical running time and yield th e fastest way to solve them.