Complexity Results and Exact Algorithms for Robust Knapsack Problems |
| |
Authors: | Fabrice Talla Nobibon Roel Leus |
| |
Institution: | 1. PostDoc researcher for Research Foundation—Flanders, Brussels, Belgium 2. QuantOM, HEC-Management School, University of Liège, Liège, Belgium 3. ORSTAT, Faculty of Business and Economics, KU Leuven, Leuven, Belgium
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|