5
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

These are called Generalized Upper Bound (GUB) constraints.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks - while searching for GUB constraints, I found that they are also sometimes referred to as "bundle" constraints. $\endgroup$
    – dxb
    Commented Sep 28, 2020 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.