The inverse maximum flow problem with lower and upper bounds for the flow
DOI:
https://doi.org/10.2298/YJOR0801013DKeywords:
inverse problems, maximum flow, minimum cut, residual network, graph searchAbstract
The general inverse maximum flow problem (denoted GIMF) is considered, where lower and upper bounds for the flow are changed so that a given feasible flow becomes a maximum flow and the distance (considering l1 norm) between the initial vector of bounds and the modified vector is minimum. Strongly and weakly polynomial algorithms for solving this problem are proposed. In the paper it is also proved that the inverse maximum flow problem where only the upper bound for the flow is changed (IMF) is a particular case of the GIMF problem.References
Ahuja, R.K., Orlin, J.B. (2000) A faster algorithm for the inverse spanning tree problem. Journal of Algorithms, 34(1): 177
Ahuja, R.K., Orlin, J.B. (1998) Inverse optimization. Cambridge, MA: Sloan School of Management, Working Paper
Ahuja, R.K., Orlin, J.B. (1998) Combinatorial algorithms for inverse network flow problems. Cambridge, MA: Sloan School of Management, submitted for publication
Ahuja, R.K., Magnanti, T.L., Orlin, J.B. (1993) Network flows: Theory, algorithms and applications. Englewood Cliffs, NJ: Prentice Hall
Burton, D., Toint, P.L. (1992) On an instance of the inverse shortest paths problem. Mathematical Programming, 53(1-3): 45
Burton, D., Paulleyblank, B., Toint, Ph.L. (1997) The inverse shortest paths problem with upper bounds on shortest paths costs. u: Pardalos P., Hearn D.W., Harger W.H. [ur.] Network optimization, lecture notes in econom., math. systems 450, Berlin: Springer-Verlag, str. 156-171
Burton, D., Toint, P.L. (1994) On the use of an inverse shortest paths algorithm for recovering linearly correlated costs. Mathematical Programming, 63(1-3): 1
Cai, M., Yang, X. (1994) Inverse shortest path problems: Technical report. Beijing, China: Academia Sinica - Institute of Systems Sciences
Ciurea, E., Deaconu, A. (2007) Inverse minimum flow problem. Journal of Applied Mathematics and Computing, 23(1-2): 193
Heuberger, C. (2004) Inverse combinatorial optimization: A survey on problems, methods, and results. Journal of Combinatorial Optimization, 8(3): 329
Huang, S., Liu, Z. On the inverse version of the minimum cost flow problem. Mathematical Programming, 33, 187-203
Sokkalingam, P.T., Ahuja, R.K., Orlin, J.B. (1999) Solving inverse spanning tree problems through network flow techniques. Oper. Res, 47 291-298
Yang, C., Zhang, J. Inverse maximum capacity path with upper bound constraints. OR Spektrum
Yang, C., Zhang, J., Ma, Z. (1997) Inverse maximum flow and minimum cut problems. Optimization, 40(2): 147
Zhang, J., Cai, C. (1998) Inverse problem of minimum cuts. Mathematical Methods of Operations Research, 47(1): 51
Zhang, J., Liu, Z., Ma, Z. (1996) On the inverse problem of minimum spanning tree with partition constraints. Mathematical Methods of Operations Research, 44(2): 171
Zhang, J., Ma, Z., Yang, C. (1995) A column generation method for inverse shortest path problems. ZOR-Math. Methods Oper. Res, 41(3): 347
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
