Consider the minimum cost flow problem as in https://en.wikipedia.org/wiki/Minimum-cost_flow_problem#:~:text=The%20minimum%2Dcost%20flow%20problem,flow%20through%20a%20flow%20network.
Suppose $f_0$ is an optimal solution for $G$ with given costs and capacities. Let $H$ be a subgraph of $G$, let $e\in H$ be an edge and now consider the following variation of the min-cost flow problem on $G$:
- We impose the additional constraint that the flow on $e$ equals some given integer $X$.
- We impose the additional constraint that the flow on each edge of $G$ which is not $H$ equals the flow given by $f_0$.
Let $f_1$ be the new optimal solution (assume that such exists). If $S_0$ and $S_1$ are the total costs from the edges of $H$ (under $f_0$ and $f_1$, respectively), is it always true that $S_0 \leq S_1$?
(Of course, it must be the case that the total cost from the edges of $G$ has become greater or stayed the same. The question is whether this is also forced on subgraphs of $G$.)
I have tested this with python code on several graphs and so far have not found a counterexample; however I also do not know how to proceed for a proof. Any help appreciated!