×

Capacity inverse minimum cost flow problem. (English) Zbl 1185.90025

Summary: 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 \(\hat{u}\) for the arc set \(A\) such that a given feasible flow \(\hat{x}\) is optimal with respect to the modified capacities. Among all capacity vectors \(\hat{u}\) satisfying this condition, we would like to find one with minimum \(\|\hat{u}-u\|\) value.
We consider two distance measures for \(\|\hat{u}-u\|\) , rectilinear \((L _{1})\) and Chebyshev \((L _{\infty })\) distances. By reduction from the feedback arc set problem we show that the capacity inverse minimum cost flow problem is \(\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.

MSC:

90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
90C60 Abstract computational complexity for mathematical programming problems

Software:

NETGEN; Boost; BGL
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms and applications. Prentice Hall, New York
[2] Ahuja RK, Orlin JB (2001) Inverse optimization. Oper Res 49:771–783 · Zbl 1163.90764 · doi:10.1287/opre.49.5.771.10607
[3] Ahuja RK, Orlin JB (2002) Combinatorial algorithms of inverse network flow problems. Networks 40:181–187 · Zbl 1026.90089 · doi:10.1002/net.10048
[4] Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M (1999) Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer, Berlin · Zbl 0937.68002
[5] Burkard RE, Hamacher HW (1981) Minimal cost flows in regular matroids. Math Program Stud 14: 32–47 · Zbl 0449.90095
[6] Burton D, Toint PL (1992) On an instance of the inverse shortest paths problem. Math Program 53:45–61 · Zbl 0756.90089 · doi:10.1007/BF01585693
[7] Burton D, Toint PL (1994) On the use of an inverse shortest paths algorithm for recovering linearly correlated costs. Math Program 63:1–22 · Zbl 0795.90080 · doi:10.1007/BF01582056
[8] Caprara A, Fischetti M, Toth P (2000) Algorithms for the set covering problem. Ann Oper Res 89:353–371 · Zbl 0974.90006 · doi:10.1023/A:1019225027893
[9] Demetrescu C, Finocchi I (2003) Combinatorial algorithms for feedback problems in directed graphs. Inf Process Lett 86:129–136 · Zbl 1173.68586 · doi:10.1016/S0020-0190(02)00491-X
[10] Garey MR, Johnson DS (1979) Computers and intractability: a guide to theory of NP-completeness. Freeman, New York · Zbl 0411.68039
[11] Goldfarb D, Grigoriadis MD (1988) A computational comparison of the dinic and network simplex methods for maximum flow. Ann Oper Res 13:83–123 · doi:10.1007/BF02288321
[12] Hamacher HW, Küfer K-H (2002) Inverse radiation therapy planning–a multiple objective optimization approach. Discrete Appl Math 118:145–161 · Zbl 0995.92024 · doi:10.1016/S0166-218X(01)00261-X
[13] Heuberger C (2004) Inverse optimization: a survey on problems, methods, and results. J Comb Optim 8:329–361 · Zbl 1084.90035 · doi:10.1023/B:JOCO.0000038914.26975.9b
[14] Kann V (1992) On the approximability of NP-complete optimization problems. PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Sweden
[15] Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations, pp 85–103
[16] Klingman D, Napier A, Stutz J (1974) NETGEN: a program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems. Manage Sci 20:814–820 · Zbl 0303.90042 · doi:10.1287/mnsc.20.5.814
[17] Saab Y (2001) A fast and effective algorithm for the feedback arc set problem. J Heuristics 7:235–250 · Zbl 0972.68633 · doi:10.1023/A:1011315014322
[18] Siek JG, Lee L-Q, Lumsdaine A (2002) The boost graph library: user guide and reference manual. Addison-Wesley, Reading
[19] Yang C, Zhang J, Ma Z (1997) Inverse maximum flow and minimum cut problems. Optimization 40: 147–170 · Zbl 0880.90041 · doi:10.1080/02331939708844306
[20] Zhang J, Liu L (2006) Inverse maximum flow problems under the weighted hamming distance. J Comb Optim 12:395–408 · Zbl 1126.90072 · doi:10.1007/s10878-006-9000-1
[21] Zhang J, Liu Z (1996) Calculating some inverse linear programming problems. J Comput Appl Math 72:261–273 · Zbl 0856.65069 · doi:10.1016/0377-0427(95)00277-4
[22] Zhang J, Liu Z (2002) A general model of some inverse combinatorial optimization problems and its solution method under l norm. J Comb Optim 6:207–227 · Zbl 1032.90030 · doi:10.1023/A:1013807829021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.