Expanding maximum capacity path under weighted sum-type distances

Javad Tayyebi; Adrian Deaconu; Javad Tayyebi; Adrian Deaconu

doi:10.3934/math.2021237

AIMS Mathematics

2021, Volume 6, Issue 4: 3996-4010. doi: 10.3934/math.2021237

Previous Article Next Article

Research article

Expanding maximum capacity path under weighted sum-type distances

Javad Tayyebi ¹,
Adrian Deaconu ^{2
,
,}

1.
Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran
2.
Department of Mathematics and Computer Science, Transilvania University, Brasov, 500091, Romania

Received: 04 December 2020 Accepted: 24 January 2021 Published: 04 February 2021
MSC : 05C85, 68R10, 90C27

This paper investigates an inverse version of maximum capacity path problems. Its goal is how to increase arc capacities under a budget constraint so that the maximum capacity among all paths from an origin to a destination is improved as much as possible. Two distinct cases are considered: fixed costs and linear costs. In the former, an algorithm is designed to solve the problem in polynomial time. In the latter, a polynomial-time approach is developed to contain two phases. The first phase applies the first algorithm as a subroutine to find a small interval containing the optimal value. The second phase converts the reduced problem into a minimum ratio path problem. Then, a Secant-Newton hybrid algorithm is proposed to obtain the exact optimal solution. Some theoretical aspects as well as experimental computations are performed to guarantee the correctness and performance of our proposed algorithm.
- reverse optimization,
- maximum capacity path,
- Secant-Newton algorithm,
- minimum ratio path
Citation: Javad Tayyebi, Adrian Deaconu. Expanding maximum capacity path under weighted sum-type distances[J]. AIMS Mathematics, 2021, 6(4): 3996-4010. doi: 10.3934/math.2021237

Related Papers:

Abstract

This paper investigates an inverse version of maximum capacity path problems. Its goal is how to increase arc capacities under a budget constraint so that the maximum capacity among all paths from an origin to a destination is improved as much as possible. Two distinct cases are considered: fixed costs and linear costs. In the former, an algorithm is designed to solve the problem in polynomial time. In the latter, a polynomial-time approach is developed to contain two phases. The first phase applies the first algorithm as a subroutine to find a small interval containing the optimal value. The second phase converts the reduced problem into a minimum ratio path problem. Then, a Secant-Newton hybrid algorithm is proposed to obtain the exact optimal solution. Some theoretical aspects as well as experimental computations are performed to guarantee the correctness and performance of our proposed algorithm.

References

[1]	R. K. Ahuja, Minimum cost-reliability ratio path problem, Comput. Oper. Res., 15 (1988), 83–89. doi: 10.1016/0305-0548(88)90031-7
[2]	R. K. Ahuja, J. L. Batra, S. K. Gupta, Combinatorial optimization with rational objective functions: A communication, Math. Oper. Res., 8 (1983), 314–314. doi: 10.1287/moor.8.2.314
[3]	R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network flows: theory, algorithms, and applications, USA: Prentice Hall, 1993.
[4]	B. Alizadeh, E. Afrashteh, F. Baroughi, Inverse obnoxious p-median location problems on trees with edge length modifications under different norms, Theor. Comput. Sci., 772 (2019), 73–87. doi: 10.1016/j.tcs.2018.11.020
[5]	O. Berman, G. Y. Handler, Optimal minimax path of a single service unit on a network to nonservice destinations, Transport. Sci., 21 (1987), 115–122. doi: 10.1287/trsc.21.2.115
[6]	R. E. Burkard, Y. X. Lin, J. Z. Zhang, Weight reduction problems with certain bottleneck objectives, Eur. J. Oper. Res., 153 (2004), 191–199. doi: 10.1016/S0377-2217(02)00713-0
[7]	Y. Chao, L. J. lin, A capacity expansion problem with budget constraint and bottleneck limitation, Acta Math. Sci., 21 (2001), 428–432. doi: 10.1016/S0252-9602(17)30430-7
[8]	Y. Chao, Z. J. Zhong, On the bottleneck capacity expansion problems on networks, Acta Math. Sci., 26 (2006), 202–208. doi: 10.1016/S0252-9602(06)60042-8
[9]	A. Ghate, Inverse optimization in semi-infinite linear programs, Oper. Res. Lett., 48 (2020), 278–285. doi: 10.1016/j.orl.2020.02.007
[10]	K. Ghobadi, T. Lee, H. Mahmoudzadeh, D. Terekhov, Robust inverse optimization, Oper. Res. Lett., 46 (2018), 339–344. doi: 10.1016/j.orl.2018.03.007
[11]	K. Kar, M. Kodialam, T. V. Lakshman, Minimum interference routing of bandwidth guaranteed tunnels with MPLS traffic engineering applications, IEEE J. Sel. Area. Comm., 18 (2000), 2566–2579. doi: 10.1109/49.898737
[12]	X. Y. Li, X. C. Shu, H. J. Huang, J. J. Bai, Capacitated partial inverse maximum spanning tree under the weighted Hamming distance, J. Comb. Optim., 38 (2019), 1005–1018. doi: 10.1007/s10878-019-00433-x
[13]	J. P. Li, J. P. Zhu, The capacity expansion path problem in networks, J. Appl. Math., 2013 (2013), 156901.
[14]	A. Mohammadi, J. Tayyebi, Maximum capacity path interdiction problem with fixed costs, Asia-Pac. J. Oper. Res., 36 (2019), 1950018. doi: 10.1142/S0217595919500180
[15]	A. P. Punnen, A linear time algorithm for the maximum capacity path problem, Eur. J. Oper. Res., 53 (1991), 402–404. doi: 10.1016/0377-2217(91)90073-5
[16]	T. Radzik, Fractional combinatorial optimization, In: Handbook of combinatorial optimization, Boston, MA: Springer, 1998,429–478.
[17]	J. Tayyebi, M. Aman, On inverse linear programming problems under the bottleneck-type weighted Hamming distance, Discrete Appl. Math., 240 (2018), 92–101. doi: 10.1016/j.dam.2015.12.017
[18]	J. Tayyebi, A. Mohammadi, S. M. R. Kazemi, Reverse maximum flow problem under the weighted Chebyshev distance, RAIRO-Ope. Res., 52 (2018), 1107–1121. doi: 10.1051/ro/2017088
[19]	J. Tayyebi, M. Aman, Efficient algorithms for the reverse shortest path problem on trees under the hamming distance, Yugoslav J. Oper. Res., 27 (2016), 46–60.
[20]	J. Tayyebi, A. Deaconu, Inverse generalized maximum flow problems, Mathematics, 7 (2019), 899. doi: 10.3390/math7100899
[21]	A. Tayyebi, A. R. Sepasian, Partial inverse min-max spanning tree problem, J. Comb. Optim., 40 (2020), 1075–1091. doi: 10.1007/s10878-020-00656-3
[22]	C. Yang, J. Z. Zhang, A constrained capacity expansion problem on networks, Int. J. Comput. Math., 70 (1998), 19–33. doi: 10.1080/00207169808804733
[23]	J. Z. Zhang, C. Yang, Y. X. Lin, A class of bottleneck expansion problems, Comput. Oper. Res., 28 (2001), 505–519. doi: 10.1016/S0305-0548(99)00130-6
[24]	B. W. Zhang, X. C. Guan, P. M. Pardalos, C. Y. He, An algorithm for solving the shortest path improvement problem on rooted trees under unit hamming distance, J. Optim. Theory Appl., 178 (2018), 538–559. doi: 10.1007/s10957-018-1221-9
[25]	B. W. Zhang, J. Z. Zhang, L. Q. Qi, The shortest path improvement problems under Hamming distance, J. Comb. Optim., 12 (2006), 351. doi: 10.1007/s10878-006-9000-1
[26]	J. Z. Zhang, Z. H. Liu, An oracle strongly polynomial algorithm for bottleneck expansion problems, Optim. Methods Software, 17 (2002), 61–75. doi: 10.1080/10556780290027819

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)