Skip to main content
Operations Research

Return to Question

Became Hot Network Question
edited tags
Link
RobPratt
RobPratt
  • 34.3k
  • 2
  • 47
  • 90
edited body
Source Link
RobPratt
RobPratt
  • 34.3k
  • 2
  • 47
  • 90

Consider the network flow polyhedron for a directed graph $G = (N, A)$. Along with the standard flow-balance and single-arc capacity constraints, we are faced with additional constraints which enforce capacities on the total flow through subsets of arcs. Formally, for (not necessarily disjoint) subsets $S_1, S_2, \ldots S_k \subseteq A$$S_1, S_2, \dots, S_k \subseteq A$ we have constraints $$\sum_{a \in S_i} x_a \leq u_{S_i} \quad \forall i \in [k].$$

Do such constraints have a specific name in the network flow literature, or have they been specifically studied? I'm mostly interested in the polyhedral aspects of these constraints, but applications would be interesting as well.

Consider the network flow polyhedron for a directed graph $G = (N, A)$. Along with the standard flow-balance and single-arc capacity constraints, we are faced with additional constraints which enforce capacities on the total flow through subsets of arcs. Formally, for (not necessarily disjoint) subsets $S_1, S_2, \ldots S_k \subseteq A$ we have constraints $$\sum_{a \in S_i} x_a \leq u_{S_i} \quad \forall i \in [k].$$

Do such constraints have a specific name in the network flow literature, or have they been specifically studied? I'm mostly interested in the polyhedral aspects of these constraints, but applications would be interesting as well.

Consider the network flow polyhedron for a directed graph $G = (N, A)$. Along with the standard flow-balance and single-arc capacity constraints, we are faced with additional constraints which enforce capacities on the total flow through subsets of arcs. Formally, for (not necessarily disjoint) subsets $S_1, S_2, \dots, S_k \subseteq A$ we have constraints $$\sum_{a \in S_i} x_a \leq u_{S_i} \quad \forall i \in [k].$$

Do such constraints have a specific name in the network flow literature, or have they been specifically studied? I'm mostly interested in the polyhedral aspects of these constraints, but applications would be interesting as well.

Source Link
dxb
dxb
  • 1.8k
  • 2
  • 13
  • 32

Combined arc capacity constraints in network flows

Consider the network flow polyhedron for a directed graph $G = (N, A)$. Along with the standard flow-balance and single-arc capacity constraints, we are faced with additional constraints which enforce capacities on the total flow through subsets of arcs. Formally, for (not necessarily disjoint) subsets $S_1, S_2, \ldots S_k \subseteq A$ we have constraints $$\sum_{a \in S_i} x_a \leq u_{S_i} \quad \forall i \in [k].$$

Do such constraints have a specific name in the network flow literature, or have they been specifically studied? I'm mostly interested in the polyhedral aspects of these constraints, but applications would be interesting as well.