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.
Accepté le :
DOI : 10.1051/ro/2017088
Mots-clés : Maximum flow problem, reverse problem, Chebyshev distance, network design, Newton method, binary search
@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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ro/2017088/
[1] , and , Network Flows. Prentice-Hall, Englewood Cliffs (1993). | MR | Zbl
[2] and , Inverse optimization. Oper. Res. 49 (2001) 771–783. | DOI | MR | Zbl
[3] and , Combinatorial algorithms for inverse network flow problems. Networks 40 (2002) 181–187. | DOI | MR | Zbl
[4] , and , Linear Programming and Network Flows. John Wiley & Sons (2011). | MR
[5] and , On an instance of the inverse shortest paths problem. Math. Program. 53 (1992) 45–61. | DOI | MR | Zbl
[6] and , On the use of an inverse shortest paths algorithm for recovering linearly correlated costs. Math. Program. 63 (1994) 1–22. | DOI | MR | Zbl
[7] , Inverse Shortest Path Routing Problems in the Design of IP Networks. Department of Mathematics Linkping University, Sweden (2010).
[8] and , Complexity of some inverse shortest path lengths problems. Networks 56 (2010) 20–29. | MR | Zbl
[9] , The inverse maximum flow problem considering l∞ norm. RAIRO: OR 42 (2008) 401–414. | DOI | Numdam | MR | Zbl
[10] , 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] and , An introduction to inverse combinatorial problems, in Paradigms of Combinatorial Optimization (Problems and New Approaches), edited by . Wiley, London, Hoboken (2010). | Zbl
[12] and , Some inverse optimization problems under the Hamming distance. Eur. J. Oper. Res. 170 (2006) 887–899. | DOI | MR | Zbl
[13] and , On random graphs I. Publ. Math. 6 (1959) 290–297. | MR | Zbl
[14] , , and , The complexity of an inverse shortest paths problem, in Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, edited by , , and . American Mathematical Society DIMATIA-DIMACS Conference, Stirin Castle, Czech Republic (1997) 49–113. | MR | Zbl
[15] and , Maximal flow through a network. Can. J. Math. 8 (1956) 399–404. | DOI | MR | Zbl
[16] , Inverse optimization: a survey on problems, methods, and results. J. Comb. Optim. 8 (2004) 329–336 | DOI | MR | Zbl
[17] , , , and , Operations Research Proceedings 1998 – Selected Papers of the International Conference on Operations Research, Zurich, August 31–September 3, 1998 (1998) 158–167. | Zbl
[18] and , Inverse maximum flow problems under the weighted Hamming distance. J. Comb. Optim. 12 (2006) 395–408. | DOI | MR | Zbl
[19] , Inverse Maximum Flow Problems under the Combining Norms, edited by , , and . In: FAW-AAIM, Vol. 7924 of Lecture Notes in Computer Science (2013) 221–230. | DOI | Zbl
[20] , Parametric flows, weighted means of cuts, and fractional combinatorial optimization, in Complexity in Numerical Optimization, edited by . World Scientific Publishing Co. (1993) 351–386. | DOI | MR | Zbl
[21] and , 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] and , On inverse linear programming problems under the bottleneck-type weighted Hamming distance. Discret. Appl. Math. 240 (2018) 92–10. | DOI | MR | Zbl
[23] , and , Inverse maximum flow and minimum cut problems. Optimization 40 (1997) 147–170. | DOI | MR | Zbl
[24] , and , Some reverse location problem. Eur. J. Oper. Res. 124 (2000) 77–88. | DOI | MR | Zbl
[25] , and , Reverse Center Location Problem. Vol. 1741 of Lecture Notes in Computer Science (1999) 279–294. | DOI | MR | Zbl
[26] , and , The shortest path improvement problems under Hamming distance. J. Comb. Optim. 12 (2006) 351–361. | DOI | MR | Zbl
[27] and , Computation of the reverse shortest path problem. J. Glob. Optim. 25 (2003) 243–261. | DOI | MR | Zbl
Cité par Sources :
