Reverse maximum flow problem under the weighted Chebyshev distance
RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 4-5, pp. 1107-1121.

Given a network G(V, A, u) with two specific nodes, a source node s and a sink node t, the reverse maximum flow problem is to increase the capacity of some arcs (i, j) as little as possible under bound constraints on the modifications so that the maximum flow value from s to t in the modified network is lower bounded by a prescribed value v0. In this paper, we study the reverse maximum flow problem when the capacity modifications are measured by the weighted Chebyshev distance. We present an efficient algorithm to solve the problem in two phases. The first phase applies the binary search technique to find an interval containing the optimal value. The second phase uses the discrete type Newton method to obtain exactly the optimal value. Finally, some computational experiments are conducted to observe the performance of the proposed algorithm.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2017088
Classification : 90C35, 90B10, 05C21
Mots-clés : Maximum flow problem, reverse problem, Chebyshev distance, network design, Newton method, binary search
Tayyebi, Javad 1 ; Mohammadi, Abumoslem 1 ; Kazemi, Seyyed Mohammad Reza 1

1 
@article{RO_2018__52_4-5_1107_0,
     author = {Tayyebi, Javad and Mohammadi, Abumoslem and Kazemi, Seyyed Mohammad Reza},
     title = {Reverse maximum flow problem under the weighted {Chebyshev} distance},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1107--1121},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {4-5},
     year = {2018},
     doi = {10.1051/ro/2017088},
     mrnumber = {3878615},
     zbl = {1411.90346},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2017088/}
}
TY  - JOUR
AU  - Tayyebi, Javad
AU  - Mohammadi, Abumoslem
AU  - Kazemi, Seyyed Mohammad Reza
TI  - Reverse maximum flow problem under the weighted Chebyshev distance
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2018
SP  - 1107
EP  - 1121
VL  - 52
IS  - 4-5
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2017088/
DO  - 10.1051/ro/2017088
LA  - en
ID  - RO_2018__52_4-5_1107_0
ER  - 
%0 Journal Article
%A Tayyebi, Javad
%A Mohammadi, Abumoslem
%A Kazemi, Seyyed Mohammad Reza
%T Reverse maximum flow problem under the weighted Chebyshev distance
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2018
%P 1107-1121
%V 52
%N 4-5
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2017088/
%R 10.1051/ro/2017088
%G en
%F RO_2018__52_4-5_1107_0
Tayyebi, Javad; Mohammadi, Abumoslem; Kazemi, Seyyed Mohammad Reza. Reverse maximum flow problem under the weighted Chebyshev distance. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 4-5, pp. 1107-1121. doi : 10.1051/ro/2017088. http://www.numdam.org/articles/10.1051/ro/2017088/

[1] R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows. Prentice-Hall, Englewood Cliffs (1993). | MR | Zbl

[2] K. Ahuja and J.B. Orlin, Inverse optimization. Oper. Res. 49 (2001) 771–783. | DOI | MR | Zbl

[3] K. Ahuja and J.B. Orlin, Combinatorial algorithms for inverse network flow problems. Networks 40 (2002) 181–187. | DOI | MR | Zbl

[4] M.S. Bazaraa, J. Jarvis and H.D. Sherali, Linear Programming and Network Flows. John Wiley & Sons (2011). | MR

[5] D. Burton and Ph.L. Toint, On an instance of the inverse shortest paths problem. Math. Program. 53 (1992) 45–61. | DOI | MR | Zbl

[6] D. Burton and Ph.L. Toint, On the use of an inverse shortest paths algorithm for recovering linearly correlated costs. Math. Program. 63 (1994) 1–22. | DOI | MR | Zbl

[7] M. Call, Inverse Shortest Path Routing Problems in the Design of IP Networks. Department of Mathematics Linkping University, Sweden (2010).

[8] T. Cui and D.S. Hochbaum, Complexity of some inverse shortest path lengths problems. Networks 56 (2010) 20–29. | MR | Zbl

[9] A. Deaconu, The inverse maximum flow problem considering l∞ norm. RAIRO: OR 42 (2008) 401–414. | DOI | Numdam | MR | Zbl

[10] A. Deaconu, The inverse maximum flow problem with lower and upper bounds for the flow. Yugosl. J. Oper. Res. 18 (2008) 13–22. | DOI | MR | Zbl

[11] M. Demange and J. Monnot, An introduction to inverse combinatorial problems, in Paradigms of Combinatorial Optimization (Problems and New Approaches), edited by V.Th. Paschos. Wiley, London, Hoboken (2010). | Zbl

[12] C.W. Duin and A. Volgenant, Some inverse optimization problems under the Hamming distance. Eur. J. Oper. Res. 170 (2006) 887–899. | DOI | MR | Zbl

[13] P. Erds and A. Rnyi, On random graphs I. Publ. Math. 6 (1959) 290–297. | MR | Zbl

[14] S.P. Fekete, W.H. Hochstattler, S. Kromberg and C. Moll, The complexity of an inverse shortest paths problem, in Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, edited by R.L. Graham, J. Kratochvil, J. Nesetrol and F.S. Roberts. American Mathematical Society DIMATIA-DIMACS Conference, Stirin Castle, Czech Republic (1997) 49–113. | MR | Zbl

[15] L.R. Ford and D.R. Fulkerson, Maximal flow through a network. Can. J. Math. 8 (1956) 399–404. | DOI | MR | Zbl

[16] C. Heuberger, Inverse optimization: a survey on problems, methods, and results. J. Comb. Optim. 8 (2004) 329–336 | DOI | MR | Zbl

[17] S.O. Krumke, H. Noltemeier, S. Schwarz, H.-C. Wirth and R. Ravi, Operations Research Proceedings 1998 – Selected Papers of the International Conference on Operations Research, Zurich, August 31–September 3, 1998 (1998) 158–167. | Zbl

[18] L.C. Liu and J.Z. Zhang, Inverse maximum flow problems under the weighted Hamming distance. J. Comb. Optim. 12 (2006) 395–408. | DOI | MR | Zbl

[19] L. Liu, Inverse Maximum Flow Problems under the Combining Norms, edited by M. Fellows, X. Tan, and B. Zhu. In: FAW-AAIM, Vol. 7924 of Lecture Notes in Computer Science (2013) 221–230. | DOI | Zbl

[20] T. Radzik, Parametric flows, weighted means of cuts, and fractional combinatorial optimization, in Complexity in Numerical Optimization, edited by P.M. Pardalos. World Scientific Publishing Co. (1993) 351–386. | DOI | MR | Zbl

[21] J. Tayyebi and M. Aman, Efficient algorithms for the reverse shortest path problem on trees under the Hamming distance. Yugosl. J. Oper. Res. 27 (2017) 46–60. | DOI | MR | Zbl

[22] J. Tayyebi and M. Aman, On inverse linear programming problems under the bottleneck-type weighted Hamming distance. Discret. Appl. Math. 240 (2018) 92–10. | DOI | MR | Zbl

[23] C. Yang, J. Zhang and Z. Ma, Inverse maximum flow and minimum cut problems. Optimization 40 (1997) 147–170. | DOI | MR | Zbl

[24] J. Zhang, Z. Liu and Z. Ma, Some reverse location problem. Eur. J. Oper. Res. 124 (2000) 77–88. | DOI | MR | Zbl

[25] J. Zhang, X. Yang and M. Cai, Reverse Center Location Problem. Vol. 1741 of Lecture Notes in Computer Science (1999) 279–294. | DOI | MR | Zbl

[26] B.W. Zhang, J.Z. Zhang and L.Q. Qi, The shortest path improvement problems under Hamming distance. J. Comb. Optim. 12 (2006) 351–361. | DOI | MR | Zbl

[27] J.Z. Zhang and Y.X. Lin, Computation of the reverse shortest path problem. J. Glob. Optim. 25 (2003) 243–261. | DOI | MR | Zbl

Cité par Sources :