Abstract
We propose techniques for the solution of the LP relaxation and the Lagrangean dual in combinatorial optimization and nonlinear programming problems. Our 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 our techniques find not only the optimal solution value, but the 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 use 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 problem, thek-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 our techniques significantly improve the theoretical running time and yield the fastest way to solve them.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Ahuja, A. Goldberg, J. Orlin and R. Tarjan, “Finding minimum-cost flows by double scaling,” to appear in:SIAM Journal of Computing (1991).
R. Ahuja, J. Orlin, C. Stein and R. Tarjan, “Improved algorithms for bipartite network flow”, “Improved algorithms for bipartite network flows,” Sloan working paper 3218-90-MS, MIT (Cambridge, MA, 1990).
A. Balakrishnan, T.L. Magnanti and R.T. Wong, “A dual-ascent procedure for large-scale uncapacitated network design,”Operations Research 5 (1989) 716–740.
F. Barahona, M. Grötschel, M. Jünger and G. Reinelt, “An application of combinatorial optimization to statistical physics and circuit layout design,”Operations Research 36 (1988) 493–513.
I. Barany, T.J. Van Roy and L.A. Wolsey, “Uncapacitated lot sizing: the convex hull of solutions,”Mathematical Programming Study 22 (1984) 32–43.
V. Chandru and M. Trick, “On the complexity of Lagrange multiplier search,” unpublished manuscript.
D. Coppersmith and S. Winograd, “Matrix multiplication via arithmetic progressions,”Proceedings of the 19th Annual ACM Symposium on Theory of Computing (1987) 1–6.
H. Crowder, E.L. Johnson and M.W. Padberg, “Solving large scale zero–one linear programming problems,”Operations Research 31 (1983) 803–834.
H. Crowder and M.W. Padberg, “Solving large scale symmetric traveling salesman problems to optimality,”Management Science 26 (1980) 495–509.
W. Cunningham, “Testing membership in matroid polyhedra,”Journal of Combinatorial Theory Series B 36 (1984) 161–188.
G.D. Eppen and R.K. Martin, “Solving multi-item capacitated lot sizing problems using variable redefinition,”Operations Research 35 (1987) 832–848.
M. Fisher, “The Lagrangean relaxation method for solving integer programming problems,”Management Science 27 (1981) 1–18.
A. Geoffrion, “Lagrangean relaxation and its uses in integer programming,”Mathematical Programming Study 2 (1974) 82–114.
M. Goemans and D. Bertsimas, “Survivable networks, linear programming relaxations and the parsimonious property,”Mathematical Programming 60 (1993) 145–166.
M. Grötschel, M. Jünger and G. Reinelt, “A cutting plane algorithm for the linear ordering problem,”Operations Research 32 (1984) 1195–1220.
M. Grötschel, L. Loväsz and A. Schrijver,Geometric Algorithms and Combinatorial Optimization (Springer, Berlin, 1988).
M. Held and R.M. Karp, “The traveling-salesman problem and minimum spanning trees,”Operations Research 18 (1970) 1138–1162.
M. Held and R.M. Karp, “The traveling-salesman problem and minimum spanning trees: Part II,”Mathematical Programming 1 (1971) 6–25.
M. Held, P. Wolfe and H. Crowder, “Validation of subgradient optimization,”Mathematical Programming 6 (1974) 62–88.
E.L. Johnson, M.M. Kostreva and H.H. Suhl, “Solving 0–1 integer programming problems arising from large scale planning models,”Operations Research 33 (1985) 802–820.
K. Jornsten and M. Nasberg, “A new Lagrangean relaxation approach to the generalized assignment problem,”European Journal of Operations Research 27 (1986) 313–323.
L.G. Khachian, “A polynomial algorithm for linear programming,”Soviet Mathematics Doklady 20 (1979) 191–194.
J. Leung, T.L Magnanti and R. Vachani, “Facets and algorithms for capacitated lot sizing,”Mathematical Programming 45 (1989) 331–359.
T.L. Magnanti, P. Mireault and R.T. Wong, “Tailoring Benders decomposition for uncapacitated network design,”Mathematical Programming Study 26 (1986) 112–154.
T.L. Magnanti and R. Vachani, “A strong cutting plane algorithm for production scheduling with changeover costs,” working paper OR173-87, Operations Research Center (1989).
T.L. Magnanti and R.T. Wong, “Network design and transportation planning: Models and algorithms,”Transportation Science 18 (1984) 1–56.
G.L. Nemhauser and L.A. Wolsey,Integer and Combinatorial Optimization (Wiley, New York, 1985).
M.W. Padberg and S. Hong, “On the symmetric traveling salesman problem: a computational study,”Mathematical Programming Study 12 (1980) 78–107.
M.W. Padberg and G. Rinaldi, “Optimization of a 532-city symmetric traveling salesman problem by branch and cut,”Operations Research Letters 6 (1987) 1–7.
S. Plotkin, D. Shmoys and E. Tardos, “Fast approximation algorithms for fractional packing and covering problems,” extended abstract.
J. Shapiro,Mathematical Programming, Structures and Algorithms (Wiley, New York, 1979).
P. Vaidya, “Speeding-up linear programming using fast matrix multiplication,”Proceedings of the 30th Symposium on the Foundations of Computer Science (1989) 332–337.
P. Vaidya, “A new algorithm for minimizing convex functions over convex sets,” AT&T Bell Laboratories (Murray Hill, NJ, 1990).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bertsimas, D., Orlin, J.B. A technique for speeding up the solution of the Lagrangean dual. Mathematical Programming 63, 23–45 (1994). https://doi.org/10.1007/BF01582057
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582057