TY - GEN A1 - Grötschel, Martin A1 - Monma, Clyde A1 - Stoer, Mechthild T1 - Design of Survivable Networks T3 - ZIB-Report - SC-93-09 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1054 ER - TY - GEN A1 - Grötschel, Martin A1 - Monma, Clyde A1 - Stoer, Mechthild T1 - A Polyhedral Approach to Network Connectivity Problems (Extended Abstract). N2 - We present a polyhedral approach for the general problem of designing a minimum-cost network with specified connectivity requir T3 - ZIB-Report - SC-92-22 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-924 ER - TY - GEN A1 - Grötschel, Martin A1 - Monma, Clyde A1 - Stoer, Mechthild T1 - Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements. N2 - We consider the important practical and theoretical problem of designing a low-cost communications network which can survive failures of certain network components. Our initial interest in this area was motivated by the need to design certain ``two-connected" survivable topologies for fiber optic communication networks of interest to the regional telephone companies. In this paper, we describe some polyhedral results for network design problems with higher connectivity requirements. We also report on some preliminary computational results for a cutting plane algorithm for various real-world and random problems with high connectivity requirements which shows promise for providing good solutions to these difficult problems. \def\NP{$\cal NP$} T3 - ZIB-Report - SC-92-24 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-944 ER - TY - GEN A1 - Stoer, Mechthild A1 - Dahl, Geir T1 - A Polyhedral Approach to Multicommodity Survivable Network Design. N2 - The design of cost-efficient networks satisfying certain survivability constraints is of major concern to the telecommunications industry. In this paper we study a problem of extending the capacity of a network by discrete steps as cheaply as possible, such that the given traffic demand can be accommodated even when a single edge or node in the network fails. We derive valid and non-redundant inequalities for the polyhedron of capacity design variables, by exploiting its relationship to connectivity network design and knapsack-like subproblems. Computational work using this model and the additional inequalities is in progress. T3 - ZIB-Report - SC-93-20 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1162 ER - TY - GEN A1 - Dahl, Geir A1 - Martin, Alexander A1 - Stoer, Mechthild T1 - Routing through virtual paths in layered telecommunication networks N2 - We study a network configuration problem in telecommunications where one wants to set up paths in a capacitated network to accommodate given point-to-point traffic demand. The problem is formulated as an integer linear programming model where 0-1 variables represent different paths. An associated integral polytope is studied and different classes of facets are described. These results are used in a cutting plane algorithm. Computational results for some realistic problems are reported. T3 - ZIB-Report - SC-95-41 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2070 ER - TY - CHAP A1 - Grötschel, Martin A1 - Monma, Clyde A1 - Stoer, Mechthild ED - Ball, Michael ED - Magnanti, Thomas ED - Monma, Clyde ED - Nemhauser, George T1 - Design of Survivable Networks T2 - Network Models Y1 - 1995 VL - 7 SP - 617 EP - 672 PB - North-Holland ER - TY - JOUR A1 - Grötschel, Martin A1 - Monma, Clyde A1 - Stoer, Mechthild T1 - Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements JF - Operations Research Y1 - 1995 VL - 43 IS - 6 SP - 1012 EP - 1024 ER - TY - CHAP A1 - Grötschel, Martin A1 - Monma, Clyde A1 - Stoer, Mechthild ED - Roberts, Fred ED - Hwang, Frank ED - Monma, Clyde T1 - Polyhedral Approaches to Network Survivability T2 - Reliability of Computer and Communication Networks, Proc. Workshop 1989, New Brunswick, NJ/USA Y1 - 1991 VL - 5 SP - 121 EP - 141 PB - American Mathematical Society ER - TY - JOUR A1 - Grötschel, Martin A1 - Monma, Clyde A1 - Stoer, Mechthild T1 - Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints JF - Operations Research Y1 - 1992 VL - 40 IS - 2 SP - 309 EP - 330 ER - TY - JOUR A1 - Grötschel, Martin A1 - Monma, Clyde A1 - Stoer, Mechthild T1 - Facets for polyhedra arising in the design of communication networks with low-connectivity constraints JF - SIAM Journal on Optimization Y1 - 1992 VL - 2 IS - 3 SP - 474 EP - 504 ER - TY - JOUR A1 - Ascheuer, Norbert A1 - Escudero, Laureano A1 - Grötschel, Martin A1 - Stoer, Mechthild T1 - A Cutting Plane Approach to the Sequential Ordering Problem (with Applications to Job Scheduling in Manufacturing) JF - SIAM Journal on Optimization Y1 - 1993 VL - 3 IS - 1 SP - 25 EP - 42 ER - TY - CHAP A1 - Ascheuer, Norbert A1 - Escudero, Laureano A1 - Grötschel, Martin A1 - Stoer, Mechthild ED - Kannan, Ravi ED - Pulleyblank, William T1 - On Identifying in Polynomial Time Violated Subtour Elimination and Precedence Forcing Constraints for the Sequential Ordering Problem T2 - Integer Programming and Combinatorial Optimization, Proceeedings of a Conference held at the University of Waterloo, May 28-30, 1990 Y1 - 1990 SP - 19 EP - 28 PB - University of Waterloo Press ER -