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 complexity class $\Sigma^p_2$ hence it is most probably not in ${\cal NP}$. In addition, even computing the regret of a solution with respect to a scenario requires the solution of an ${\cal NP}$-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.

Heuristic and exact algorithms for the interval min-max regret knapsack problem / Furini, Fabio; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - STAMPA. - 27:2(2015), pp. 392-405. [10.1287/ijoc.2014.0632]

Heuristic and exact algorithms for the interval min-max regret knapsack problem

IORI, MANUEL;
2015

Abstract

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 complexity class $\Sigma^p_2$ hence it is most probably not in ${\cal NP}$. In addition, even computing the regret of a solution with respect to a scenario requires the solution of an ${\cal NP}$-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.
5-mag-2015
27
2
392
405
Heuristic and exact algorithms for the interval min-max regret knapsack problem / Furini, Fabio; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - STAMPA. - 27:2(2015), pp. 392-405. [10.1287/ijoc.2014.0632]
Furini, Fabio; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori
File in questo prodotto:
File Dimensione Formato  
furini2015.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 320.06 kB
Formato Adobe PDF
320.06 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11380/1061623
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 26
  • ???jsp.display-item.citation.isi??? 26
social impact