Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem
Furini, Fabio; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori (2015), Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem, INFORMS Journal on Computing, 27, 2, p. 392-405. 10.1287/ijoc.2014.0632
TypeArticle accepté pour publication ou publié
Journal nameINFORMS Journal on Computing
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Faculty of Engineering [Bologna]
Abstract (EN)We consider a generalization of the 0–1 knapsack problem in which the profit of each item can take any value in a range characterized by a minimum and a maximum possible profit. A set of specific profits is called a scenario. Each feasible solution associated with a scenario has a regret, given by the difference between the optimal solution value for such scenario and the value of the considered solution. The interval min–max regret knapsack problem (MRKP) is then to find a feasible solution such that the maximum regret over all scenarios is minimized. The problem is extremely challenging both from a theoretical and a practical point of view. Its decision version is complete for the second level of the polynomial hierarchy hence it is most probably not in 𝒩𝒫. In addition, even computing the regret of a solution with respect to a scenario requires the solution of an 𝒩𝒫-hard problem. We examine the behavior of classical combinatorial optimization approaches when adapted to the solution of the MRKP. We introduce an iterated local search approach and a Lagrangian-based branch-and-cut algorithm and evaluate their performance through extensive computational experiments.
Subjects / Keywordsrobust optimization; knapsack problem; interval min–max regret; local search; Lagrangian relaxation; branch and cut
Showing items related by title and author.
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2007) Article accepté pour publication ou publié