We consider the multidimensional knapsack problem (MKP) with min-max regret criterion under interval profits. We examine three typical algorithms widely applied for min-max regret criterion: fixed-scenario approach, Benders-like decomposition and branch-and-cut. We further propose a new heuristic framework, which we call the iterated dual substitution algorithm. Computational experiments on a wide set of bench-mark instances are carried out, and the proposed iterated dual substitution algorithm performs best on all of the tested instances.

An iterated dual substitution approach for the min-max regret multidimensional knapsack problem

MARTELLO, SILVANO;
2016

Abstract

We consider the multidimensional knapsack problem (MKP) with min-max regret criterion under interval profits. We examine three typical algorithms widely applied for min-max regret criterion: fixed-scenario approach, Benders-like decomposition and branch-and-cut. We further propose a new heuristic framework, which we call the iterated dual substitution algorithm. Computational experiments on a wide set of bench-mark instances are carried out, and the proposed iterated dual substitution algorithm performs best on all of the tested instances.
IEEE International Conference on Industrial Engineering and Engineering Management
726
730
Wu, W.; Iori, M.; Martello, Silvano; Yagiura, M.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/586782
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact