The Inverse k-Max Combinatorial Optimization Problem
DOI:
https://doi.org/10.2298/YJOR220516037NKeywords:
Inverse optimization, k-max, bottleneck, convex, combinatorial algorithms.Abstract
Classical combinatorial optimization concerns finding a feasible subset of a ground set in order to optimize an objective function. We address in this article the inverse optimization problem with the k-max function. In other words, we attempt to perturb the weights of elements in the ground set at minimum total cost to make a predetermined subset optimal in the fashion of the k-max objective with respect to the perturbed weights. We first show that the problem is in general NP-hard. Regarding the case of independent feasible subsets, a combinatorial O(n2 log n) time algorithm is developed, where n is the number of elements in E. Special cases with improved complexity are also discussed.References
C. Heuberger, ”Inverse combinatorial optimization: A survey on problems, methods, and results”, Journal of Combinatorial Optimization, vol. 8, pp. 329-361, 2004.
D. Burton, Ph.L. Toint, ”On an instance of the inverse shortest paths problem”, Mathematical Programming, vol.53, pp. 45-61, 1992.
R.K. Ahuja, J.B. Orlin, ”Inverse optimization,” Operations Ressearch, vol. 49, no. 5, pp. 771-783, 2001.
M.C. Cai, C.W. Duin, X. Yang, J. Zhang, ”The partial inverse minimum spanning tree problem when weight increase is forbidden”, European Journal of Operational Research, vol. 188, no. 2, pp. 348-353, 2008.
D.S. Hochbaum, ”Efficient algorithms for the inverse spanning-tree problem”, Operations Research, vol. 51, no. 5, pp. 785-797, 2003.
B. Li, Z. Sheng, ”On the inverse minimum spanning tree problem with minimum number of perturbed edges”, Journal of System Science and System Engineering, vol. 12, pp. 350-359, 2003.
R.K. Ahuja, J.B. Orlin, ”Combinatorial algorithms for inverse network flow problems”, Networks, vol. 40, no. 4, pp. 181-187, 2002.
A. Deaconu, ”The inverse maximum flow problem considering l∞-norm”, RAIRO Operations Research, vol. 402, no. 3, pp. 401-414 , 2008.
M.C. Cai, Y. Li, ”Inverse matroid intersection problem”, Mathematical Methods of Operations Research, vol. 45, no. 4, 235-243, 1997.
Z. Zhang, S. Li, H.J. Lai, D.Z. Du, ”Algorithms for the partial inverse matroid problem in which weights can only be increased”, Journal of Global Optimization, vol. 65, pp. 801-811, 2016.
J. Roland, J.R. Figueira, Y.D. Smet, ”The inverse {0, 1}-knapsack problem: Theory, algorithms and computational experiment”, Discrete Optimization, vol.10, no. 2, pp. 181-192, 2013.
Y. Chung, M. Demange, ”On inverse traveling salesman problems”, 4OR, vol. 10, pp. 193- 209, 2012.
I. Keshtkar, M. Ghiyasvand, ”Inverse quickest center location problem on a tree”, Discrete Applied Mathematics, vol. 260, no. 15, pp. 188-202, 2019.
V.H. Pham, K.T. Nguyen, T.T. Le, ”Inverse stable point problem on trees under an extension of Chebyshev norm and Bottleneck Hamming distance”, Optimization Methods and Software, vol. 36, pp. 755-772 2021.
S. Taghikhani, F. Baroughi, B. Alizadeh, ”A generalized interval type-2 fuzzy random variable based algorithm under mean chance value at risk criterion for inverse 1-median location problems on tree networks with uncertain costs”, Journal of Computational and Applied Mathematics, vol. 408, 114104, 2022.
M. Hasanzadeh, B. Alizadeh, F. Baroughi, ”Optimal algorithms for some inverse uncapacitated facility location problems on networks”, Optimization Methods and Software, vol. 37, no. 3, pp. 982-1005, 2022.
X. Qian, X. Guan, J. Jia, Q. Zhang, P. M. Pardalos, ”Vertex quickest 1-center location problem on trees and its inverse problem under weighted l∞ norm”, Journal Global Optimization, 2022. Online. doi: https://doi.org/10.1007/s10898-022-01212-5.
T.H.N. Nhan, K.T. Nguyen, H. Nguyen-Thu, ”The Minmax Regret Reverse 1-Median Problem on Trees with Uncertain VertexWeights”, Asia-Pacific Journal of Operational Research, 2022. Online. doi: https://doi.org/10.1142/S0217595922500336.
S. Nickel, J. Puerto, Location Theory - A unified approach, Springer, 2005.
E. Gassner, ”An inverse approach to convex ordered median problems in trees”, Journal of Combinatorial Optimization, vol. 23, no.2, pp. 261-273, 2012.
K.T. Nguyen, A. Chassein, ”The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance”, European Journal of Operational Research, vol. 247, no. 3, pp. 774-781, 2015.
K.T. Nguyen, H. Nguyen-Thu, N.T. Hung, ”On the complexity of inverse convex ordered 1-median problem on the plane and on tree networks”, Mathematical Methods of Operations Research, vol. 88, no. 2, pp. 147-159, 2018.
V.H. Pham, K.T. Nguyen, ”Inverse anti-k-centrum problem on networks with variable edge lengths”, Taiwanese Journal of Mathematics, vol. 24, no. 2, pp. 501-522, 2020.
X. Guan, J. Zhang, ”Inverse constrained bottleneck problems under weighted l∞-norm”, Computers and Operations Research, vol. 34, no. 11, pp. 3243-3254, 2007.
X. Guan, Y. Cao, ”Constrained and bicriteria inverse bottleneck optimization problems under weighted Hamming distance”, Optimization, vol. 61, no. 2, pp. 1-14, 2012.
X. Guan, J. Zhang, ”Inverse constrained bottleneck problems on networks” In: Gervasi O. et al. (eds) Computational Science and Its Applications - ICCSA 2005. ICCSA 2005. Lecture Notes in Computer Science 3483. Springer, Berlin, Heidelberg, 2005.
J. Gorski, S. Ruzika, ”On k-max-optimization”, Operations Research Letters, vol. 37, no. 1, pp. 23-26, 2009.
M.R. Garey, D.S. Johnson, Computers and intractability: A guide to the theory of NPcompleteness, W. H. Freeman and Co., Sanfrancisco, CA, 1979.
E. Balas, E. Zemel, ”An algorithm for large zero-one knapsack problems”, Operations Research, vol. 28, no. 5, pp. 1130-1154, 1980.
J. Hershberger, ”Finding the upper envelope of n line segments in O(n log n) time”, Information Processing Letters, vol. 33, no. 4, pp. 169-174, 1989.
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
