On the robustness of optimal solutions for combinatorial optimization problems

• Autorzy: Libura M.
• Języki publikacji: EN

Abstrakty

EN

We consider the so-called generic combinatorial optimization problem, where the set of feasible solutions is some family of subsets of a finite ground set with specified positive initial weights of elements, and the objective function represents the total weight of elements of a feasible solution. We assume that the weights of all elements may be perturbed simultaneously and independently up to a given percentage of their initial values. A feasible solution which minimizes the worst-case relative regret, is called a robust solution. The maximum percentage level of perturbations, for which an initially optimal solution remains robust, is called the robustness radius of this solution. In this paper we study the robustness aspect of initially optimal solutions and provide lower bounds for their robustness radii.

Słowa kluczowe

EN

robustness analysis; sensitivity analysis; combinatorial optimization; accuracy function; robustness radius

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2009
• Tom: Vol. 38, no 3
• Strony: 671--685
• Opis fizyczny: Bibliogr. 12 poz., rys., wykr.

Twórcy

autor

Libura M.

• Systems Research Institute of the Polish Academy of Sciences, Newelska 6, 01-447 Warszawa, Poland

Bibliografia

• AVERBAKH, I. (2005) Computing and minimizing the relative regret in combinatorial optimization with interval data. Discrete Optimization 2, 273-287.
• HAMACHER, H.W. and QUEYRANNE, M. (1985) K best solutions to combinatorial optimization problems. Annals of Operations Research 4, 123-143.
• KASPERSKI, A. (2008) Discrete Optimization with Interval Data. Minmax Regret and Fuzzy Approach. Springer-Verlag, Berlin, Heidelberg.
• KATOH, N., IBARAKI, T, and MINE, H. (1981) An algorithm for finding k minimum spanning trees. SIAM Journal on Computing, 10, 245-255.
• KOUVELIS, P. and YU, G. (1997) Robust Discrete Optimization and Its Applications. Kluwer Academic Publishers, Boston.
• LIBURA, M. (1999) On accuracy of solutions for combinatorial optimization problems with perturbed coefficients of the objective function. Annals of Operations Research 86, 53-62.
• LIBURA, M. (2000) Quality of solutions for perturbed combinatorial optimization problems. Control and Cybernetics 29, 199-219.
• LIBURA, M. and NIKULIN, Y. (2004) Stability and accuracy functions in multicriteria combinatorial optimization problems with E-MINMAX and S-MINMIN partial criteria. Control and Cybernetics 33, 511-524.
• LIBURA, M. and NIKULIN, Y (2006) Stability and accuracy functions in multicriteria linear combinatorial optimization problems. Annals of Operations Research 147, 255-267.
• OGUZ, O. (2000) Bounds on the opportunity costs of neglecting reoptimization in mathematical programming. Management Science 46, 1009-1012.
• VAN DER POORT, E., LIBURA, M., SIERKSMA, G. and VAN DER VEEN, J.A.A. (1999) Solving the k-best traveling salesman problem. Computers & Operations Research 26, 409-425.
• WENDELL, R.E. (2004) Tolerances sensitivity and optimality bounds in linear programming. Management Science 50, 797-803.