라인 위에서의 순환외판원문제에 대한 부분역최적화
Partial Inverse Traveling Salesman Problems on the Line
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
The partial inverse optimization problem is an interesting variant of the inverse optimization problem in which the given instance of an optimization problem need to be modified so that a prescribed partial solution can constitute a part of an optimal solution in the modified instance. In this paper, we consider the traveling salesman problem defined on the line (TSP on the line) which has many applications such as item delivery systems, the collection of objects from storage shelves, and so on. It is worth studying the partial inverse TSP on the line, defined as follows. We are given n requests on the line, and a sequence of k requests that need to be served consecutively. Each request has a specific position on the real line and should be served by the server traveling on the line. The task is to modify as little as possible the position vector associated with n requests so that the prescribed sequence can constitute a part of the optimal solution (minimum Hamiltonian cycle) of TSP on the line. In this paper, we show that the partial inverse TSP on the line and its variant can be solved in polynomial time when the sever is equiped with a specific internal algorithm Forward Trip or with a general optimal algorithm.
Abstract
The partial inverse optimization problem is an interesting variant of the inverse optimization problem in which the given instance of an optimization problem need to be modified so that a prescribed partial solution can constitute a part of an optimal solution in the modified instance. In this paper, we consider the traveling salesman problem defined on the line (TSP on the line) which has many applications such as item delivery systems, the collection of objects from storage shelves, and so on. It is worth studying the partial inverse TSP on the line, defined as follows. We are given n requests on the line, and a sequence of k requests that need to be served consecutively. Each request has a specific position on the real line and should be served by the server traveling on the line. The task is to modify as little as possible the position vector associated with n requests so that the prescribed sequence can constitute a part of the optimal solution (minimum Hamiltonian cycle) of TSP on the line. In this paper, we show that the partial inverse TSP on the line and its variant can be solved in polynomial time when the sever is equiped with a specific internal algorithm Forward Trip or with a general optimal algorithm.
참고문헌 (21)
- Ravindra K. Ahuja, "Inverse Optimization", Operations Research, 49(5), pp.771~783 (2001), Institute for Operations Research and the Management Sciences (INFORMS)[DOI]
- Clemens Heuberger, "Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results", Journal of Combinatorial Optimization, 8(3), pp.329~361 (2004), Springer Science and Business Media LLC[DOI]
- Jianzhong Zhang, "A General Model of Some Inverse Combinatorial Optimization Problems and its Solution Method under ∞-norm", Journal of Combinatorial Optimization, 6(2), pp.207~227 (2002), Springer Science and Business Media LLC[DOI]
- Shaoji Xu, "An inverse problem of the weighted shortest path problem", Japan Journal of Industrial and Applied Mathematics, 12(1), pp.47~59 (1995), Springer Science and Business Media LLC[DOI]
- Ravindra K. Ahuja, "A Faster Algorithm for the Inverse Spanning Tree Problem", Journal of Algorithms, 34(1), pp.177~193 (2000), Elsevier BV[DOI]
- Yerim Chung, "The 0–1 inverse maximum stable set problem", Discrete Applied Mathematics, 156(13), pp.2501~2516 (2008), Elsevier BV[DOI]
- Yerim Chung, "Inverse chromatic number problems in interval and permutation graphs", European Journal of Operational Research, 243(3), pp.763~773 (2015), Elsevier BV[DOI]
- Y. Chung, "On Inverse Traveling Salesman Problems", 4OR-A Quarterly Journal of Operations Research, 10, pp.193~209 (2012)[DOI]
- Dimitris Bertsimas, "Inverse Optimization: A New Perspective on the Black-Litterman Model", Operations Research, 60(6), pp.1389~1403 (2012), Institute for Operations Research and the Management Sciences (INFORMS)[DOI]
- Anil Aswani, "Inverse Optimization with Noisy Data", Operations Research, 66(3), pp.870~892 (2018), Institute for Operations Research and the Management Sciences (INFORMS)[DOI]
- Timothy C. Y. Chan, "Inverse Optimization: Closed-Form Solutions, Geometry, and Goodness of Fit", Management Science, 65(3), pp.1115~1135 (2019), Institute for Operations Research and the Management Sciences (INFORMS)[DOI]
- Peyman Mohajerin Esfahani, "Data-driven inverse optimization with imperfect information", Mathematical Programming, 167(1), pp.191~234 (2018), Springer Science and Business Media LLC[DOI]
- Kimia Ghobadi, "Robust inverse optimization", Operations Research Letters, 46(3), pp.339~344 (2018), Elsevier BV[DOI]
- Xiaoguang Yang, "Partial inverse assignment problems under norm", Operations Research Letters, 35(1), pp.23~28 (2007), Elsevier BV[DOI]
- Xiaoguang Yang, "Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem", RAIRO - Operations Research, 35(1), pp.117~126 (2001), EDP Sciences[DOI]
- The Complexity of Preprocessing, "Lai T.C", MIT, ~ (2003)
- 정예림, "라인 위에서의 순환외판원문제에 대한 부분역최적화", 한국컴퓨터정보학회논문지, 24(11), pp.119~126 (2019), 한국컴퓨터정보학회[DOI]
- M. R. Garey, "Computers and Intractability-A Guide to The Theory of NP-completeness" (1979), Freeman
- S. Angelov, "Weighted Isotonic Regression under the l1-Norm", Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.783~791 (2006), SODA
- Nilotpal Chakravarti, "Isotonic Median Regression: A Linear Programming Approach", Mathematics of Operations Research, 14(2), pp.303~308 (1989), Institute for Operations Research and the Management Sciences (INFORMS)[DOI]
- T. Robertson, "Algorithms in Order Restricted Statistical Inference and the Cauchy Mean Value Property", Annals of Statistics, 8(3), pp.645~651 (1980)[DOI]