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.

$\endgroup$
5
$\begingroup$

These are called Generalized Upper Bound (GUB) constraints.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks - while searching for GUB constraints, I found that they are also sometimes referred to as "bundle" constraints. $\endgroup$ – Dipayan Banerjee Sep 28 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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