Flow Cover Inequalities for Fixed-Charge Networks

The single-node fixed-charge flow model is the mixed-integer set

$$\sum_{j \in N} x_j \le b, \qquad 0 \le x_j \le u_j y_j, \qquad y_j \in \{0,1\}, \qquad j \in N,$$

where $x_j \ge 0$ is the continuous flow on arc $j$ (with capacity $u_j > 0$), $b > 0$ is the demand at the node, and the binary $y_j$ indicates whether arc $j$ is open (incurring a fixed charge). This is the flow analogue of a knapsack: each arc $j$ carries a yes/no decision $y_j$ paired with a continuous payload $x_j$ capped at $u_j$.

A subset $C \subseteq N$ is a flow cover if its total capacity exceeds the demand:

$$\sum_{j \in C} u_j > b.$$

The strictly positive quantity

$$\lambda = \sum_{j \in C} u_j - b$$

is called the excess of the cover. Intuitively, $\lambda$ measures how much spare capacity the cover carries: if every arc in $C$ were fully open, the cover could push $\lambda$ units more than the node can absorb.

Illustration: with $N=\{1,2,3,4\}$, $u=(7,5,4,2)$, and $b=10$:

• $C=\{1,2\}$: $\sum u_j = 7+5 = 12 > 10$, so $C$ is a flow cover with $\lambda = 2$.
• $C=\{2,3\}$: $\sum u_j = 5+4 = 9 \not> 10$, so $C$ is not a flow cover.