Solving the Uncapacitated Network Design Problem by a Lagrangean Heuristic and Branch-and-Bound

References

• Ahuja R. K. , Magnanti T. L. , Orlin J. B. Network Flows. Theory, Algorithms and Applications (1993) (Prentice Hall) Google Scholar
• Allen E. , Helgason R. , Kennington J. , Shetty B. A generalization of polyak's convergence result for subgradient optimization. Math. Programming (1987) 37 309 317 Crossref, Google Scholar
• Balakrishnan A. , Magnanti T. L. , Wong R. T. A dual-ascent procedure for large-scale uncapacitated network design. Opns. Res. (1989) 37 716 740 Link, Google Scholar
• Bastay G. , Turesson B.-O. , Hellstrand J. A comparison between decomposition methods for the discrete network design problem. (1987) . Bachelor Thesis LiU-MAT-EX-87-62, Linköping University, Sweden. Supervisors K. Holmberg and A. Migdalas. (In Swedish.) Google Scholar
• Benders J. F. Partitioning procedures for solving mixed-variables programming problems. Numerische Matematik (1962) 4 238 252 Crossref, Google Scholar
• Camerini P. M. , Fratta L. , Maffioli F. On improving relaxation methods by modified gradient techniques. Math. Programming Stud. (1975) 3 26 34 Crossref, Google Scholar
• Crowder H. Computational improvements for subgradient optimization. Symposia Mathematica (1976) XIX (Academic Press, London) Google Scholar
• Erlenkotter D. A dual-based procedure for uncapacitated facility location. Opns. Res. (1978) 26 992 1009 Link, Google Scholar
• Gallo G. , Pallottino S. Fortran codes for network optimization: Shortest path algorithms. Ann. O. R. (1988) 13 3 79 Crossref, Google Scholar
• Geoffrion A. , Mcbride R. Lagrangean relaxation applied to capacitated facility location problems. AIIE Trans. (1978) 10 40 47 Crossref, Google Scholar
• Geoffrion A. M. Lagrangean relaxation for integer programming. Math. Programming Stud. (1974) 2 82 114 Crossref, Google Scholar
• Held M. , Wolfe P. , Crowder H. P. Validation of subgradient optimization. Math. Programming (1974) 6 62 88 Crossref, Google Scholar
• Hellstrand J. , Holmberg K. A Lagrangean heuristic applied to the uncapacitated network design problem. (1994) . Working paper LiTH-MAT/OPT-WP-1994-01, Department of Mathematics, Linköping Institute of Technology, Sweden Google Scholar
• Hellstrand J. , Larsson T. , Migdalas A. A characterization of the uncapacitated network design polytope. O. R. Lett. (1992) 12 159 163 Crossref, Google Scholar
• Holmberg K. On the use of valid inequalities in benders and cross decomposition. (1989) . Research report LiTH-MAT-R-1989-21, Department of Mathematics, Linköping Institute of Technology, Sweden Google Scholar
• Holmberg K. On the convergence of cross decomposition. Math. Programming (1990) 47 269 296 Crossref, Google Scholar
• Holmberg K. Mean value cross decomposition applied to integer programming problems. Eur. J. Opnl. Res. (1991) 97 124 138 . Research report LiTH-MAT-R-1991-18, Department of Mathematics, Linköping Institute of Technology, Sweden. Published in 1997 Crossref, Google Scholar
• Holmberg K. Linear mean value cross decomposition: A generalization of the Kornai-Liptak method. Eur. J. Opnl. Res. (1992) 62 55 73 Crossref, Google Scholar
• Holmberg K. , Hellstrand J. Solving the uncapacitated network design problem by a Lagrangean heuristic and branch-and-bound. (1994) . Research report LiTH-MAT-R-1994-11, Department of Mathematics, Linköping Institute of Technology, Sweden Google Scholar
• Holmberg K. , Jörnsten K. , Migdalas A. Decomposition methods applied to discrete network design. (1986) . Working paper LiTH-MAT/OPT-WP-1986-07, Optimization, Department of Mathematics, Linköping Institute of Technology, Sweden Google Scholar
• Holmberg K. , Migdalas A. Solution methods for the discrete choice network design problem combining Lagrangean relaxation and decomposition with generation of valid inequalitites. (1991) . Working paper LiTH-MAT/OPT-WP-1991-07, Optimization, Department of Mathematics, Linköping Institute of Technology, Sweden Google Scholar
• Johnson D. S. , Lenstra J. K. , Rinnooy Kan A. H. G. The complexity of the network design problem. Networks (1978) 8 279 285 Crossref, Google Scholar
• Kornai J. , Liptak T. Two-level planning. Econometrica (1965) 33 141 169 Crossref, Google Scholar
• Magnanti T. L. , Mireault P. , Wong R. T. Tailoring benders decomposition for uncapaciteted network design. Math. Programming Stud. (1986) 26 112 154 Crossref, Google Scholar
• Magnanti T. L. , Wong R. T. Accelerating benders decomposition: Algorithmic enhancement and model selection criteria. Opns. Res. (1981) 29 464 484 Link, Google Scholar
• Magnanti T. L. , Wong R. T. Network design and transportation planning: Model and algorithms. Transportation Sci. (1984) 18 1 55 Link, Google Scholar
• McDaniel D. , Devine M. A modified benders partitioning algorithm for mixed integer programming. Management Sci. (1977) 24 312 319 Link, Google Scholar
• Migdalas A. Mathematical programming techniques for analysis and design of communication and transportation networks. (1988) . Ph.D. thesis, Department of Mathematics, Linköping University, Sweden Google Scholar
• Poljak B. T. A general method of solving extremum problems. Soviet Math. Doklady (1967) 8 593 397 Google Scholar
• Poljak B. T. Minimization of unsmooth functionals. USSR Computational Mathematics and Mathematical Phys. (1969) 9 14 29 Crossref, Google Scholar
• Shor N. Z. Minimization Methods for Non-Differentiable Functions (1985) (Springer-Verlag, Berlin) Crossref, Google Scholar
• Van Roy T. J. Cross decomposition for mixed integer programming. Math. Programming (1983) 25 46 63 Crossref, Google Scholar
• Van Roy T. J. A cross decomposition algorithm for capacitated facility location. Opns. Res. (1986) 34 145 163 Link, Google Scholar