Consider the following min-cost flow variant:
Input:
- a positively-weighted complete bipartite graph $G = (S, T, c)$ and extra vertices $s, t$
- edges from $s$ to $S$ and from $T$ to $t$.
- lower and upper capacity bounds $l_i, u_i$ on each edge $(s, s_i)$
- flow values $g_i$ for each edge $(t_i, t)$ with the constraint that $\sum_i g_i = 1$
For any flow assignment $f$ on the edges $(s, s_i)$ (note that by flow conservation $\sum_i f_i = 1$), let $\text{cost}(f)$ be the cost of a min-cost flow satisfying the upper and lower bounds.
Problem:
Find an $f$ satisfying all capacity constraints such that $\text{cost}(f)$ is maximized.