Capacity inverse minimum cost flow problem

Given a directed graph G=(N,A) with arc capacities u _ij and a minimum cost flow problem defined on G, the capacity inverse minimum cost flow problem is to find a new capacity vector ^(u)]\hat{u} for the arc set A such that a given feasible flow ^(x)]\hat{x} is optimal with respect to the modified capacities. Among all capacity vectors ^(u)]\hat{u} satisfying this condition, we would like to find one with minimum ||^(u)]-u||\|\hat{u}-u\| value. We consider two distance measures for ||^(u)]-u||\|\hat{u}-u\| , rectilinear (L ₁) and Chebyshev (L _∞) distances. By reduction from the feedback arc set problem we show that the capacity inverse minimum cost flow problem is NP\mathcal{NP} -hard in the rectilinear case. On the other hand, it is polynomially solvable by a greedy algorithm for the Chebyshev norm. In the latter case we propose a heuristic for the bicriteria problem, where we minimize among all optimal solutions the number of affected arcs. We also present computational results for this heuristic.