Robust capacitated Steiner trees and networks with uniform demands
From MaRDI portal
(Redirected from Publication:6179720)
Robust capacitated Steiner trees and networks with uniform demands
Robust capacitated Steiner trees and networks with uniform demands
Abstract: We are interested in the design of robust (or resilient) capacitated rooted Steiner networks in case of terminals with uniform demands. Formally, we are given a graph, capacity and cost functions on the edges, a root, a subset of nodes called terminals, and a bound k on the number of edge failures. We first study the problem where k = 1 and the network that we want to design must be a tree covering the root and the terminals: we give complexity results and propose models to optimize both the cost of the tree and the number of terminals disconnected from the root in the worst case of an edge failure, while respecting the capacity constraints on the edges. Second, we consider the problem of computing a minimum-cost survivable network, i.e., a network that covers the root and terminals even after the removal of any k edges, while still respecting the capacity constraints on the edges. We also consider the possibility of protecting a given number of edges. We propose three different formulations: a cut-set based formulation, a flow based one, and a bilevel one (with an attacker and a defender). We propose algorithms to solve each formulation and compare their efficiency.
Recommendations
- Formulations for designing robust networks. An application to wind power collection
- Survivable network design: the capacitated minimum spanning network problem
- Chance-constrained multi-terminal network design problems
- scientific article; zbMATH DE number 795223
- Designing networks with resiliency to edge failures using two-stage robust optimization
Cites work
- A catalog of steiner tree formulations
- A directed cycle-based column-and-cut generation method for capacitated survivable network design
- A polyhedral approach to multicommodity survivable network design
- A survey of network interdiction models and algorithms
- A survey on mixed-integer programming techniques in bilevel optimization
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Design of Survivable Networks: A survey
- Designing networks with resiliency to edge failures using two-stage robust optimization
- Deterministic network interdiction
- Efficient determination of the k most vital edges for the minimum spanning tree problem
- Finding minimum cost directed trees with demands and capacities
- Finding the n Most Vital Links in Flow Networks
- Foundations of bilevel programming
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 795223 (Why is no real title available?)
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Multicriteria optimization
- Network flows. Theory, algorithms, and applications.
- On the edge capacitated Steiner tree problem
- Optimizing the Design of a Wind Farm Collection Network
- Optimizing wind farm cable routing considering power losses
- Robust and adaptive network flows
- Robust optimization
- Solving Steiner tree problems in graphs to optimality
- Steiner 2-Edge Connected Subgraph Polytopes on Series-Parallel Graphs
- Steiner k-edge connected subgraph polyhedra
- Strong inequalities for capacitated survivable network design problems.
- Survivable networks, linear programming relaxations and the parsimonious property
- The complexity of the capacitated tree problem
- The Price of Robustness
- The Steiner tree problem
Cited in
(1)
This page was built for publication: Robust capacitated Steiner trees and networks with uniform demands
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6179720)
