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 benchmark 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, Manuel; Martello, S; Yagiura, M.. - 2016:(2016), pp. 726-730. (Intervento presentato al convegno 2016 International Conference on Industrial Engineering and Engineering Management, IEEM 2016 tenutosi a Bali, Indonesia nel 4-7/12/2016) [10.1109/IEEM.2016.7797971].
An Iterated Dual Substitution Approach for the Min-Max Regret Multidimensional Knapsack Problem
IORI, MANUEL;
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 benchmark instances are carried out, and the proposed iterated dual substitution algorithm performs best on all of the tested instances.
Pubblicazioni consigliate
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
