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., and Orlin, J.B., "A faster algorithm for the inverse spanning tree problem", Journal of Algorithms, 34 (2000) 177-193.
Ahuja, R.K., and Orlin, J.B., "Inverse optimization", Working Paper, Sloan School of Management, MIT, Cambridge, MA, 1998.
Ahuja, R.K., and Orlin, J.B., Combinatorial Algorithms for Inverse Network Flow Problems, Sloan School of Management, MIT, Cambridge, MA, submitted for publication, 1998.
Ahuja, R.K., Magnanti, T.L., and Orlin, J.B., Network flows: Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ, 1993.
Burton, D., and Toint, Ph.L., "On an instance of the inverse shortest path problem", Math. Programming, 53 (1992) 45-61.
Burton, D., Paulleyblank, B., and Toint, Ph.L., "The inverse shortest paths problem with upper bounds on shortest paths costs", in: P. Pardalos, D.W. Hearn, and W.H. Harger (eds.), Network Optimization, Lecture Notes in Econom., Math. Systems 450, Springer-Verlag, Berlin/New York, 1997, 156-171.
Burton, D., Toint, Ph.L., "On the use of an inverse shortest path algorithm for recovering linearly correlated costs", Math. Programming, 63 (1994) 1-22.
Cai, M., and Yang, X., "Inverse shortest path problems", Technical Report, Institute of Systems Sciences, Academia Sinica, Beijing, China, 1994.
Ciurea, E., and Deaconu, A., "Inverse minimum flow problem", Journal of Applied Mathematics and Computing, 23 (2007) 193-203.
Heuberger, C., "Inverse combinatorial optimization: A survey on problems, methods, and results", Journal of Combinatorial Optimization, 8 (2004) 329-361.
Huang, S., and Liu, Z., "On the inverse version of the minimum cost flow problem", Mathematical Programming, 33, 187-203.
Sokkalingam, P.T., Ahuja, R.K., and Orlin, J.B., "Solving inverse spanning tree problems through network flow techniques", Oper. Res., 47 (1999) 291-298.
Yang, C., and Zhang, J., "Inverse maximum capacity path with upper bound constraints", OR Spektrum.
Yang, C., Zhang, J., and Ma, Z., "Inverse maximum flow and minimum cut problems", Optimization, 40 (1997) 147-170.
Zhang J., and Cai, C., "Inverse problems of minimum cuts", ZOR-Math. Methods Oper. Res., 48 (1998) 51-58.
Zhang, J., Liu, Z., Ma, Z., "On the inverse problem of minimum spanning tree with partition constraints", Math. Methods Oper. Res., 44 (1996) 171-188.
Zhang, J., Ma, Z., and Yang, C., "A column generation method for inverse shortest path problems", ZOR-Math. Methods Oper. Res., 41 (1995) 347-358.
Downloads
Published
Issue
Section
License
Copyright (c) 2008 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
