Capacity inverse minimum cost flow problem |
| |
Authors: | Çiğdem Güler Horst W. Hamacher |
| |
Affiliation: | (3) Dept. Industrial and Systems Engin. Univ. Florida, Gainesville, FL 32611, USA;(4) Sloan School of Management and Dept. Electrical Engin. and Computer Sci. Massachusetts Inst. Technol., Cambridge, MA 02139, USA;(5) Sloan School of Management Massachusetts Inst. Technol., Cambridge, MA 02139, USA |
| |
Abstract: | 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 1) and Chebyshev (L ∞) distances. By reduction from the feedback arc set problem we show that the capacity inverse minimum cost flow problem is NPmathcal{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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|