A Lagrangian Heuristic Based Branch-and-Bound Approach for the Capacitated Network Design Problem

References

• Allen E., Helgason R., Kennington J., Shetty B. A generalization of Polyak's convergence result for subgradient optimization. Math. Programming (1987) 37:309–317Crossref, Google Scholar
• Balakrishnan A., Magnanti T. L., Wong R. T. A dual-ascent procedure for large-scale uncapacitated network design. Oper. Res. (1989) 37:716–740Link, Google Scholar
• Barnhart C. Dual-ascent methods for large-scale multicommodity flow problems. Naval Res. Logist. (1993) 40:305–324Crossref, Google Scholar
• Bazaraa M. S., Sherali H. D. On the choice of step size in subgradient optimization. European J. Oper. Res. (1981) 7:380–388Crossref, Google Scholar
• Busacker R., Gowen P. A procedure for determining a family of minimum-cost network flow patterns. (1961) . ORO Technical Report 15, Johns Hopkins University, Baltimore, MDGoogle Scholar
• Crowder H. Computational improvements for subgradient optimization. Symposia Mathematica (1976) XIX(Academic Press, London) 357–372Google Scholar
• Gaivoronsky A., Ermoliev Y., et al. Stochastic quasigradient methods and their implementation. Numerical Techniques for Stochastic Optimization (1988) 10(Springer-Verlag, Berlin, Germany) 313–351Springer Series in Computational MathematicsChapter 16Crossref, Google Scholar
• Gallo G., Pallottino S. Fortran codes for network optimization: Shortest path algorithms. Ann. Oper. Res. (1988) 13:3–79Crossref, Google Scholar
• Gendron B., Crainic T. G. Relaxations for multicommodity capacitated network design problems. (1994) . Research Report CRT-965, Centre de Recherche sur les Transports, Université de Montréal, CanadaGoogle Scholar
• Goffin J. L. On convergence rates of subgradient optimization methods. Math. Programming (1977) 13:329–347Crossref, Google Scholar
• Held M., Karp R. M. The traveling salesman problem and minimum spanning trees: Part ii. Math. Programming (1971) 1:6–25Crossref, Google Scholar
• Held M., Wolfe P., Crowder H. P. Validation of subgradient optimization. Math. Programming (1974) 6:62–88Crossref, Google Scholar
• Hellstrand J., Larsson T., Migdalas A. A characterization of the uncapacitated network design polytope. Oper. Res. Letters (1992) 12:159–163Crossref, Google Scholar
• Holmberg K. Lagrangian heuristics for linear cost multicommodity network flow problems. (1995) . Working Paper LiTH-MAT/OPT-WP-1995-01,Division of Optimization, Department of Mathematics, Linköping Institute of Technology, SwedenGoogle Scholar
• Holmberg K., Hellstrand J. Solving the uncapacitated network design problem by a Lagrangian heuristic and branch-and-bound. Oper. Res. (1998) 46:247–259Link, Google Scholar
• Holmberg K., Yuan D. A multicommodity network flow problem with side constraints on paths solved by column generation. (1998) . Research Report LiTH-MAT-R-1998-05, Department of Mathematics, Linköping Institute of Technology, SwedenGoogle Scholar
• Iri M. A new method for solving transportation-network problems. J. OR Soc. Japan (1960) 3:27–87Google Scholar
• Jewell W. Optimal flow through networks. (1958) . Technical Report 8, OR Center, MIT, Cambridge, MAGoogle Scholar
• Jones K. L., Lustig I. J., Farvolden J. M., Powell W. B. Multicommodity network flows: The impact of formulation on decomposition. Math. Programming (1993) 62:95–117Crossref, Google Scholar
• Lamar B. W., Sheffi Y., Powell W. B. A capacity improvement lower bound for fixed charge network design problems. Oper. Res. (1990) 38:704–710Link, Google Scholar
• Magnanti T. L., Mireault P., Wong R. T. Tailoring Benders decomposition for uncapacitated network design. Math. Programming Study (1986) 26:112–154Crossref, Google Scholar
• Magnanti T. L., Wong R. T. Network design and transportation planning: Models and algorithms. Transp. Sci. (1984) 18:1–55Link, Google Scholar
• Poljak B. T. A general method of solving extremum problems. Soviet Math. Doklady (1967) 8:593–597Google Scholar
• Poljak B. T. Minimization of unsmooth functionals. USSR Computational Math. and Math. Physics (1969) 9:14–29Crossref, Google Scholar
• Sen S., Sherali H. D. A class of convergent primal-dual subgradient algorithms for decomposable convex problems. Math. Programming (1986) 35:279–297Crossref, Google Scholar
• Shor N. Z. On the rate of convergence of the generalized gradient method. Kibernetika (1968) 4:98–99Google Scholar
• Shor N. Z.Minimization Methods for Non-Differentiable Functions (1985) (Springer-Verlag, Berlin) Crossref, Google Scholar