Adaptive stability: general approach and examples
Tóm tắt
In this article we study the situation, where an optimal solution of a combinatorial optimization problem is known and we are equipped with the simple algorithms allowing to adapt our solution to different distortions of the initial data set. We wish to describe the distortions which allow the adaptation of the given optimal solution by the given simple algorithm preserving the optimality of the first. This approach, lying between common stability and reoptimization, is called adaptive stability. In the article we construct the conditions of adaptive stability for a range of combinatorial optimization problems having a particular structure. The obtained conditions allow to build efficiently the corresponding adaptive stability areas. The stability areas may be used for postoptimal preferring among different optimal solutions whether these are multiple solutions belonging to a single mathematical model or a set of optimal solutions corresponding to different models. The abstract concept is illustrated by two examples of combinatorial optimization problems: traveling salesman problem and task distribution problem.
Tài liệu tham khảo
Ausiello G, Bonifaci V, Escoffier B (2010) Complexity and approximation in reoptimization. In: Cooper SB, Sorbi A (eds) Computability in context: computation and logic in the real world. Imperial College Press/World Scientific, Singapore, pp 101–129
Bellman R (1957) Dynamic programming. Princeton University Press, Princeton
Bockenhauer HJ, Hromkovic J, Momke T, Widmayer P (2008) On the hardness of reoptimization. In SOFSEM 2008, vol 4910 of LNCS pp 50–65
Böckenhauer HJ, Hromkovič J, Sprock A (2011) Computation, cooperation, and life. In: Kelemen J, Kelemenová A (eds) Knowing All Optimal Solutions Does Not Help for TSP Reoptimization. Lecture notes in computer science, vol 6610. Springer, Berlin, pp 7–15
Chentsov AG, Chentsov PA (2002) Dynamic programming in the problem of decomposition optimization. Autom Remote Control 63(5):815–828
Concorde (2014) http://www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm
Deineko VG, Rudolf R, Woeginger GJ (1998) Sometimes travelling is easy: the master tour problem. J Discrete Math 11(1):81–93
Efron B (1979) Bootstrap methods: another look at the jackknife. Ann Stat 7(1):1–26
Gutin G, Punnen A (2006) The traveling salesman problem and its variations. Springer, Berlin
Held M, Karp RM (1962) A dynamic programming approach to sequencing problems. J Soc Ind Appl Math 10(1):196–210
Ivanko E (2012) Optimal solutions stability criterium for min-max task distribution problem in case of the initial data set distortion. Proc IMM UBr RAS 4:180–194
Ivanko E (2013) Stability and instability of discrete problems. PPD UBr RAS, Ekaterinburg
Ivanko E (2014) Adaptive stability in graph placement problem. In: Proceedings of the 14th international conference on mathematical methods in science and engineering (CMMSE-2014), pp 739–742
Ivanko E (2014) On one approach to tsp structural stability. Advances in operations research. http://www.hindawi.com/journals/aor/2014/397025/
Papadimitriou C (1994) Computation complexity. University of California, San Diego
Shachnai H, Tamir G, Tamir T (2012) A theory and algorithms for combinatorial reoptimization. LNCS, Vol 7256, pp 618–630
Tsplib (2014) http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/a280.tsp.gz
Zych A (2012) Reoptimization of np-hard problems. Ph.D. thesis, Zurich