I solving a problem that is formulated as a min cost flow problem. After finding the optimal solution, I would like to determine how the objective function will change if I increase/decrease flow of one arc. It is possible determine this without resolving whole instance?
Currently, I calculate change of objective function by reconstructing simplex table for the optimal solution. But this reconstruction is very expensive for very large instances of the problem.
Best Answer
I think you could get a bound on the change by constructing a new network with the same nodes. Original arcs along which the optimal flow is less than the arc capacity are carried over into the new network. Original arcs whose capacities are exhausted (other than maybe the one whose flow you are tweaking) are not. For any arc used by the optimal solution, add an arc in the opposite direction with cost equal to the negative of the cost on the original arc. (This represents "reversing" part of the flow on the original arc.) Now suppose that you want to decrease the flow on arc $(i, j)$. You can solve a shortest path problem on the new network, with arc $(i, j)$ temporarily deleted, starting at $i$ and ending at $j$. That gives you an estimate of the incremental cost to "reroute" that unit of flow. It's a bound on the actual cost change, not exact, because the best solution with the reduced flow across $(i,j)$ might reroute the remaining flow someplace not involving node $j$. For an increase on the $(i, j)$ flow, you want a shortest path from $j$ to $i$.
If you are going to do sensitivity analysis on more than one flow in the optimal solution, the good news is that you only need to build this incremental network once, after which removing and replacing an occasional arc is fast, and large shortest path problems can be solved quickly. The bad news is that I have no idea how sloppy the bound might be.