Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints

DOI10.1137/0403043zbMath0728.90036OpenAlexW2148237104MaRDI QIDQ3352817

Clyde l. Monma, Martin Grötschel

Publication date: 1990

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0403043

zbMATH Keywords

survivabilitySteiner treeminimum spanning treespolyhedral approachminimum cost designfacet defining inequalitiesdesign problems for communication networksedge connectivity constraintspolynomial combinatoricsunreliable nodes and edges

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Communication networks in operations research (90B18) Reliability, availability, maintenance, inspection in operations research (90B25) Combinatorial optimization (90C27) Connectivity (05C40)

Related Items (35)

The Steiner cycle polytope ⋮ Minimum Cost ≤k Edges Connected Subgraph Problems ⋮ Two-edge connected spanning subgraphs and polyhedra ⋮ Survivable network design with shared-protection routing ⋮ Orientation-based models for \(\{0,1,2\}\)-survivable network design: theory and practice ⋮ Separation of partition inequalities with terminals ⋮ On perfectly two-edge connected graphs ⋮ Cutting plane versus compact formulations for uncertain (integer) linear programs ⋮ Finding Totally Independent Spanning Trees with Linear Integer Programming ⋮ A design of the minimum cost ring-chain network with dual-homing survivability: A tabu search approach ⋮ The Steiner tree packing problem in VLSI design ⋮ The dominant of the 2-connected-Steiner-subgraph polytope for \(W_ 4\)-free graphs ⋮ On finding two-connected subgraphs in planar graphs ⋮ Packing Steiner trees: Polyhedral investigations ⋮ Packing Steiner trees: A cutting plane algorithm and computational results ⋮ A deep real options policy for sequential service region design and timing ⋮ Fixed charge multicommodity network design using \(p\)-partition facets ⋮ Survivable network design with demand uncertainty ⋮ Box-total dual integrality and edge-connectivity ⋮ The \(k\) edge-disjoint 3-hop-constrained paths polytope ⋮ The Steiner connectivity problem ⋮ Facet Generating Techniques ⋮ The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points. ⋮ On survivable network polyhedra ⋮ On the Steiner 2-edge connected subgraph polytope ⋮ Minimum-weight two-connected spanning networks ⋮ A branch-and-cut algorithm for the k-edge connected subgraph problem ⋮ Using a hybrid of exact and genetic algorithms to design survivable networks ⋮ The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation ⋮ Probabilistic properties of highly connected random geometric graphs ⋮ Unnamed Item ⋮ \(k\)-edge connected polyhedra on series-parallel graphs ⋮ New modeling approaches for the design of local access transport area networks ⋮ Critical extreme points of the 2-edge connected spanning subgraph polytope ⋮ Directed Steiner problems with connectivity constraints

This page was built for publication: Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints