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.
29-dic-2016
2016 International Conference on Industrial Engineering and Engineering Management, IEEM 2016
Bali, Indonesia
4-7/12/2016
2016
726
730
Wu, W; Iori, Manuel; Martello, S; Yagiura, M.
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].
File in questo prodotto:
Non ci sono file associati a questo prodotto.
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: https://hdl.handle.net/11380/1141650
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact