×

zbMATH — the first resource for mathematics

Complexity results and exact algorithms for robust knapsack problems. (English) Zbl 1291.90209
Summary: This paper studies the robust knapsack problem, for which solutions are, up to a certain point, immune from data uncertainty. We complement the works found in the literature, where uncertainty affects only the profits or only the weights of the items, by studying the complexity and approximation of the general setting with uncertainty regarding both the profits and the weights, for three different objective functions. Furthermore, we develop a scenario-relaxation algorithm for solving the general problem and present computational results.

MSC:
90C27 Combinatorial optimization
90C47 Minimax problems in mathematical programming
Software:
Knapsack
PDF BibTeX Cite
Full Text: DOI
References:
[1] Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004) · Zbl 1103.90003
[2] Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York (1990) · Zbl 0708.68002
[3] Eilon, S., Application of the knapsack model for budgeting, Omega Int. J. Manag. Sci., 15, 489-494, (1987)
[4] Kouvelis, P., Yu, G.: Robust Discrete Optimization and its Applications. Kluwer Academic, Norwell (1997) · Zbl 0873.90071
[5] Ben-Tal, A.; Nemirovski, A., Robust solutions of linear programming problems contaminated with uncertain data, Math. Program., Ser. A, 88, 411-424, (2000) · Zbl 0964.90025
[6] Lida, H., A note on the MAX-MIN 0-1 knapsack problem, J. Comb. Optim., 3, 94-99, (1999) · Zbl 0935.90024
[7] Kleywegt, A.; Papastavrou, J., The dynamic and stochastic knapsack problem, Oper. Res., 46, 17-35, (1998) · Zbl 0979.90103
[8] Lin, G.; Lu, Y.; Yao, D., The stochastic knapsack revisited: switch-over policies and dynamic pricing, Oper. Res., 56, 945-957, (2008) · Zbl 1167.90634
[9] Averbakh, I., On the complexity of a class of combinatorial optimization problems with uncertainty, Math. Program., Ser. A, 90, 263-272, (2001) · Zbl 0980.90070
[10] Bertsimas, D.; Sim, M., Robust discrete optimization and network flows, Math. Program., Ser. B, 98, 49-71, (2003) · Zbl 1082.90067
[11] Bertsimas, D.; Sim, M., The price of robustness, Oper. Res., 52, 35-53, (2004) · Zbl 1165.90565
[12] Sbihi, A., A cooperative local search-based algorithm for the multiple-scenario MAX-MIN knapsack problem, Eur. J. Oper. Res., 202, 339-346, (2010) · Zbl 1175.90341
[13] Taniguchi, F.; Yamada, T.; Kataoka, S., Heuristic and exact algorithms for the MAX-MIN optimization of the multi-scenario knapsack problem, Comput. Oper. Res., 35, 2034-2048, (2008) · Zbl 1139.90026
[14] Klopfenstein, O.; Nace, D., A robust approach to the chance-constrained knapsack problem, Oper. Res. Lett., 36, 628-632, (2008) · Zbl 1210.90126
[15] Assavapokee, T.; Realff, M.; Ammons, J., A new MIN-MAX regret robust optimization approach for interval data uncertainty, J. Optim. Theory Appl., 137, 297-316, (2008) · Zbl 1151.90019
[16] Aissi, H.; Bazgan, C.; Vanderpooten, D., MIN-MAX and MIN-MAX regret versions of combinatorial optimization problems: a survey, Eur. J. Oper. Res., 197, 427-438, (2009) · Zbl 1159.90472
[17] Conde, E., On the complexity of the continuous unbounded knapsack problem with uncertain coefficients, Oper. Res. Lett., 33, 481-485, (2005) · Zbl 1195.90075
[18] Aissi, H.; Bazgan, C.; Vanderpooten, D., Approximation of MIN-MAX and MIN-MAX regret versions of some combinatorial optimization problems, Eur. J. Oper. Res., 179, 281-290, (2007) · Zbl 1180.90359
[19] Talla Nobibon, F., Leus, R.: Complexity results and exact algorithms for robust knapsack problems. Research report KBI 1118, Faculty of Business and Economics, KU, Leuven (2011) · Zbl 1291.90209
[20] Martello, S.; Pisinger, D.; Toth, P., Dynamic programming and strong bounds for the 0-1 knapsack problem, Manag. Sci., 45, 414-424, (1999) · Zbl 1231.90338
[21] Pisinger, D., Where are the hard knapsack problems?, Comput. Oper. Res., 32, 2271-2284, (2005) · Zbl 1116.90089
[22] Yu, G., On the MAX-MIN 0-1 knapsack problem with robust optimization applications, Oper. Res., 44, 407-415, (1996) · Zbl 0855.90086
[23] Kress, M.; Penn, M.; Polukarov, M., The minmax multidimensional knapsack problem with application to a chance-constrained problem, Nav. Res. Logist., 54, 656-666, (2007) · Zbl 1151.90529
[24] Kalai, R.; Vanderpooten, D., Lexicographic \(α\)-robust knapsack problem: complexity results, Int. Trans. Oper. Res., 18, 103-113, (2011) · Zbl 1219.90142
[25] Chen, G.; Hwang, H.; Tsai, T., Efficient maxima-finding algorithms for random planar samples, Discrete Math. Theor. Comput. Sci., 6, 107-122, (2003) · Zbl 1036.68124
[26] Assavapokee, T.; Realff, M.; Ammons, J.; Hong, I., Scenario relaxation algorithm for finite scenario-based MIN-MAX regret and MIN-MAX relative regret robust optimization, Comput. Oper. Res., 35, 2093-2102, (2008) · Zbl 1139.90373
[27] Averbakh, I., Computing and minimizing the relative regret in combinatorial optimization with interval data, Discrete Optim., 2, 273-287, (2005) · Zbl 1172.90467
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.