Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints

References

• Balakrishnan A. , Altinkemer K. Using a Hop-Constrained Model to Generate Alternative Communication Network Design. ORSA Journal on Computing (1992) 4 192 205 Link, Google Scholar
• Beasley J. , Christofides N. An Algorithm for the Resource Constrained Shortest Path Problem. Networks (1989) 19 379 394 Crossref, Google Scholar
• Coullard C. , Gamble B. , Liu J. , Ding-Zhu Du , Sen Jie . The K-walk Polyhedron. Advances in Optimization and Approximation (1994) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 9 29 Crossref, Google Scholar
• Chopra S. , Gorres E. , Rao M. Solving the Steiner Tree Problem on a Graph Using Branch and Cut. ORSA Journal on Computing (1992) 4 320 335 Link, Google Scholar
• Dahl G. , Realfsen B. Curve Approximation Constrained Shortest Path Problems. (1996) (Institute of Informatics, University of Oslo, Norway) . Report 6 Google Scholar
• Dahl G. The 2-hop Spanning Tree Problem. (1997) (Institute of Informatics, University of Oslo, Norway) . Report 250 Google Scholar
• Eppen G. , Martin R. Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition. Operations Research (1987) 35 832 848 Link, Google Scholar
• Geoffrion A. Lagrangean Relaxation for Integer Programming. Mathematical Programming Study (1974) 2 82 114 Crossref, Google Scholar
• Gouveia L. Using the Miller-Tucker-Zemlin constraints to formulate minimal spanning trees with hop constraints. Computers and Operations Research (1995) 22 959 970 Crossref, Google Scholar
• Gouveia L. Multicommodity Flow Models for Spanning Trees with Hop Constraints. European Journal Operational Research (1996) 95 178 190 Crossref, Google Scholar
• Hall L. Experience with a Cutting Plane Approach for the Capacitated Spanning Tree Problem. INFORMS Journal on Computing (1996) 8 219 234 Link, Google Scholar
• Held M. , Wolfe P. , Crowder H. Validation of Subgradient Optimization. Mathematical Programming (1974) 6 62 66 Crossref, Google Scholar
• Hwang F. , Richards D. , Winter P. The Steiner Tree Problem (1992) (North Holland, Amsterdam) Google Scholar
• Karp R. , Miller R. , Tatcher J. Reducibility among Combinatorial Problems. Complexity of Computer Computations (1972) (Plenum, New York) Crossref, Google Scholar
• Lawler E. Combinatorial Optimization: Networks and Matroids (1976) (Holt, Rinehart and Winston, New York) Google Scholar
• LeBlanc L. , Reddoch R. Reliable Link Topology/Capacity Design and Routing in Backbone Telecommunication Networks. (1990) . Paper presented at the First ORSA Telecommunications SIG Conference ‘Operations Research in Telecommunications’ Google Scholar
• LeBlanc L. , Reddoch R. , Chifflet J. , Mahey P. Routing in Telecommunications Networks with Flow Restrictions. (1996) . Working paper, Vanderbilt University, Nashville, TN Google Scholar
• Lim A. , Cheng S. , Wu C. Performance Oriented Rectilinear Steiner Trees. ELEKTRIK (1993) 1 137 151 Google Scholar
• Liu W. A Lower Bound for the Steiner Tree Problem in Directed Graphs. Networks (1990) 20 765 778 Crossref, Google Scholar
• Lucena A. , Beasley J. , Beasley J. Branch and Cut Algorithms. Advances in Linear and Integer Programming (1996) 187 222 . Oxford Lecture Series in Mathematics and its Applications Crossref, Google Scholar
• Maculan N. A new Linear Programming Formulation for the Shortest s-Directed Spanning Tree Problem. Journal of Combinatorics, Information and System Sciences (1986) 11 53 56 Google Scholar
• Magnanti T. , Wolsey L. Optimal Trees. ‘Network Models’, Handbooks in Operations Research and Management Science (1995) 7 503 615 Crossref, Google Scholar
• Manyem P. , Stallmann M. Some Approximation Results in Multicasting. (1996) . Working paper, North Carolina State University Google Scholar
• Martin R. Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition. Operations Research (1987) 35 820 831 Link, Google Scholar
• Miller C. , Tucker A. , Zemlin R. Integer Programming Formulations and Traveling Salesman Problems. Journal of ACM 7 (1960) 326 329 Crossref, Google Scholar
• Voss S. Steiner-Probleme in Graphen. Mathematical Systems in Economics (1990) 120 (Anton Hain Verlag, Karlsruhe, Germany) Google Scholar
• Voss S. The Steiner Tree Problem with Hop Constraints. March 1996 . Paper presented at Symposium on Combinatorial Optimization Imperial College, London Google Scholar
• Woolston K. , Albin S. The Design of Centralized Networks with Reliability and Availability Constraints. Computers and Operations Research (1988) 15 207 217 Crossref, Google Scholar