{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T02:32:26Z","timestamp":1770431546550,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1994,1]]},"DOI":"10.1007\/bf01582057","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T04:37:34Z","timestamp":1114663054000},"page":"23-45","source":"Crossref","is-referenced-by-count":7,"title":["A technique for speeding up the solution of the Lagrangean dual"],"prefix":"10.1007","volume":"63","author":[{"given":"Dimitris","family":"Bertsimas","sequence":"first","affiliation":[]},{"given":"James B.","family":"Orlin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","unstructured":"R. Ahuja, A. Goldberg, J. Orlin and R. Tarjan, \u201cFinding minimum-cost flows by double scaling,\u201d to appear in:SIAM Journal of Computing (1991)."},{"key":"CR2","series-title":"Sloan working paper","volume-title":"\u201cImproved algorithms for bipartite network flow\u201d, \u201cImproved algorithms for bipartite network flows,\u201d","author":"R. Ahuja","year":"1990","unstructured":"R. Ahuja, J. Orlin, C. Stein and R. Tarjan, \u201cImproved algorithms for bipartite network flow\u201d, \u201cImproved algorithms for bipartite network flows,\u201d Sloan working paper 3218-90-MS, MIT (Cambridge, MA, 1990)."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"716","DOI":"10.1287\/opre.37.5.716","volume":"5","author":"A. Balakrishnan","year":"1989","unstructured":"A. Balakrishnan, T.L. Magnanti and R.T. Wong, \u201cA dual-ascent procedure for large-scale uncapacitated network design,\u201dOperations Research 5 (1989) 716\u2013740.","journal-title":"Operations Research"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F. Barahona","year":"1988","unstructured":"F. Barahona, M. Gr\u00f6tschel, M. J\u00fcnger and G. Reinelt, \u201cAn application of combinatorial optimization to statistical physics and circuit layout design,\u201dOperations Research 36 (1988) 493\u2013513.","journal-title":"Operations Research"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/BFb0121006","volume":"22","author":"I. Barany","year":"1984","unstructured":"I. Barany, T.J. Van Roy and L.A. Wolsey, \u201cUncapacitated lot sizing: the convex hull of solutions,\u201dMathematical Programming Study 22 (1984) 32\u201343.","journal-title":"Mathematical Programming Study"},{"key":"CR6","unstructured":"V. Chandru and M. Trick, \u201cOn the complexity of Lagrange multiplier search,\u201d unpublished manuscript."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"D. Coppersmith and S. Winograd, \u201cMatrix multiplication via arithmetic progressions,\u201dProceedings of the 19th Annual ACM Symposium on Theory of Computing (1987) 1\u20136.","DOI":"10.1145\/28395.28396"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1287\/opre.31.5.803","volume":"31","author":"H. Crowder","year":"1983","unstructured":"H. Crowder, E.L. Johnson and M.W. Padberg, \u201cSolving large scale zero\u2013one linear programming problems,\u201dOperations Research 31 (1983) 803\u2013834.","journal-title":"Operations Research"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1287\/mnsc.26.5.495","volume":"26","author":"H. Crowder","year":"1980","unstructured":"H. Crowder and M.W. Padberg, \u201cSolving large scale symmetric traveling salesman problems to optimality,\u201dManagement Science 26 (1980) 495\u2013509.","journal-title":"Management Science"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0095-8956(84)90023-6","volume":"36","author":"W. Cunningham","year":"1984","unstructured":"W. Cunningham, \u201cTesting membership in matroid polyhedra,\u201dJournal of Combinatorial Theory Series B 36 (1984) 161\u2013188.","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1287\/opre.35.6.832","volume":"35","author":"G.D. Eppen","year":"1987","unstructured":"G.D. Eppen and R.K. Martin, \u201cSolving multi-item capacitated lot sizing problems using variable redefinition,\u201dOperations Research 35 (1987) 832\u2013848.","journal-title":"Operations Research"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.27.1.1","volume":"27","author":"M. Fisher","year":"1981","unstructured":"M. Fisher, \u201cThe Lagrangean relaxation method for solving integer programming problems,\u201dManagement Science 27 (1981) 1\u201318.","journal-title":"Management Science"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/BFb0120690","volume":"2","author":"A. Geoffrion","year":"1974","unstructured":"A. Geoffrion, \u201cLagrangean relaxation and its uses in integer programming,\u201dMathematical Programming Study 2 (1974) 82\u2013114.","journal-title":"Mathematical Programming Study"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF01580607","volume":"60","author":"M. Goemans","year":"1993","unstructured":"M. Goemans and D. Bertsimas, \u201cSurvivable networks, linear programming relaxations and the parsimonious property,\u201dMathematical Programming 60 (1993) 145\u2013166.","journal-title":"Mathematical Programming"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"1195","DOI":"10.1287\/opre.32.6.1195","volume":"32","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"M. Gr\u00f6tschel, M. J\u00fcnger and G. Reinelt, \u201cA cutting plane algorithm for the linear ordering problem,\u201dOperations Research 32 (1984) 1195\u20131220.","journal-title":"Operations Research"},{"key":"CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e4sz and A. Schrijver,Geometric Algorithms and Combinatorial Optimization (Springer, Berlin, 1988)."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"M. Held and R.M. Karp, \u201cThe traveling-salesman problem and minimum spanning trees,\u201dOperations Research 18 (1970) 1138\u20131162.","journal-title":"Operations Research"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M. Held","year":"1971","unstructured":"M. Held and R.M. Karp, \u201cThe traveling-salesman problem and minimum spanning trees: Part II,\u201dMathematical Programming 1 (1971) 6\u201325.","journal-title":"Mathematical Programming"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/BF01580223","volume":"6","author":"M. Held","year":"1974","unstructured":"M. Held, P. Wolfe and H. Crowder, \u201cValidation of subgradient optimization,\u201dMathematical Programming 6 (1974) 62\u201388.","journal-title":"Mathematical Programming"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1287\/opre.33.4.803","volume":"33","author":"E.L. Johnson","year":"1985","unstructured":"E.L. Johnson, M.M. Kostreva and H.H. Suhl, \u201cSolving 0\u20131 integer programming problems arising from large scale planning models,\u201dOperations Research 33 (1985) 802\u2013820.","journal-title":"Operations Research"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0377-2217(86)90328-0","volume":"27","author":"K. Jornsten","year":"1986","unstructured":"K. Jornsten and M. Nasberg, \u201cA new Lagrangean relaxation approach to the generalized assignment problem,\u201dEuropean Journal of Operations Research 27 (1986) 313\u2013323.","journal-title":"European Journal of Operations Research"},{"key":"CR22","first-page":"191","volume":"20","author":"L.G. Khachian","year":"1979","unstructured":"L.G. Khachian, \u201cA polynomial algorithm for linear programming,\u201dSoviet Mathematics Doklady 20 (1979) 191\u2013194.","journal-title":"Soviet Mathematics Doklady"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/BF01589110","volume":"45","author":"J. Leung","year":"1989","unstructured":"J. Leung, T.L Magnanti and R. Vachani, \u201cFacets and algorithms for capacitated lot sizing,\u201dMathematical Programming 45 (1989) 331\u2013359.","journal-title":"Mathematical Programming"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/BFb0121090","volume":"26","author":"T.L. Magnanti","year":"1986","unstructured":"T.L. Magnanti, P. Mireault and R.T. Wong, \u201cTailoring Benders decomposition for uncapacitated network design,\u201dMathematical Programming Study 26 (1986) 112\u2013154.","journal-title":"Mathematical Programming Study"},{"key":"CR25","unstructured":"T.L. Magnanti and R. Vachani, \u201cA strong cutting plane algorithm for production scheduling with changeover costs,\u201d working paper OR173-87, Operations Research Center (1989)."},{"key":"CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/trsc.18.1.1","volume":"18","author":"T.L. Magnanti","year":"1984","unstructured":"T.L. Magnanti and R.T. Wong, \u201cNetwork design and transportation planning: Models and algorithms,\u201dTransportation Science 18 (1984) 1\u201356.","journal-title":"Transportation Science"},{"key":"CR27","volume-title":"Integer and Combinatorial Optimization","author":"G.L. Nemhauser","year":"1985","unstructured":"G.L. Nemhauser and L.A. Wolsey,Integer and Combinatorial Optimization (Wiley, New York, 1985)."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BFb0120888","volume":"12","author":"M.W. Padberg","year":"1980","unstructured":"M.W. Padberg and S. Hong, \u201cOn the symmetric traveling salesman problem: a computational study,\u201dMathematical Programming Study 12 (1980) 78\u2013107.","journal-title":"Mathematical Programming Study"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0167-6377(87)90002-2","volume":"6","author":"M.W. Padberg","year":"1987","unstructured":"M.W. Padberg and G. Rinaldi, \u201cOptimization of a 532-city symmetric traveling salesman problem by branch and cut,\u201dOperations Research Letters 6 (1987) 1\u20137.","journal-title":"Operations Research Letters"},{"key":"CR30","unstructured":"S. Plotkin, D. Shmoys and E. Tardos, \u201cFast approximation algorithms for fractional packing and covering problems,\u201d extended abstract."},{"key":"CR31","volume-title":"Mathematical Programming, Structures and Algorithms","author":"J. Shapiro","year":"1979","unstructured":"J. Shapiro,Mathematical Programming, Structures and Algorithms (Wiley, New York, 1979)."},{"key":"CR32","doi-asserted-by":"crossref","unstructured":"P. Vaidya, \u201cSpeeding-up linear programming using fast matrix multiplication,\u201dProceedings of the 30th Symposium on the Foundations of Computer Science (1989) 332\u2013337.","DOI":"10.1109\/SFCS.1989.63499"},{"key":"CR33","volume-title":"A new algorithm for minimizing convex functions over convex sets","author":"P. Vaidya","year":"1990","unstructured":"P. Vaidya, \u201cA new algorithm for minimizing convex functions over convex sets,\u201d AT&T Bell Laboratories (Murray Hill, NJ, 1990)."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01582057.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01582057\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01582057","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T11:15:44Z","timestamp":1556882144000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01582057"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,1]]},"references-count":33,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1994,1]]}},"alternative-id":["BF01582057"],"URL":"https:\/\/doi.org\/10.1007\/bf01582057","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,1]]}}}