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 / Wu, W.; Iori, M.; Martello, Silvano; Yagiura, M.. - STAMPA. - 2016-:(2016), pp. 7797971.726-7797971.730. (Intervento presentato al convegno 2016 International Conference on Industrial Engineering and Engineering Management, IEEM 2016 tenutosi a idn nel 2016) [10.1109/IEEM.2016.7797971].
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
