We consider binary integer programming problems with the min-max regret objective function under interval objective coefficients. We propose a heuristic frame- work, the iterated dual substitution (iDS) algorithm, which iteratively invokes a dual substitution heuristic and excludes from the search space any solution already checked in previous iterations. In iDS, we use a best scenario–based lemma to improve performance. We apply iDS to four typical combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the generalized assignment problem, and the set covering problem. For the multidimensional knapsack problem, we compare the iDS approach with two algorithms widely used for problems with the min-max regret criterion: a fixed-scenario approach, and a branch-and-cut approach. The results of computational experiments on a broad set of benchmark instances show that the proposed iDS approach performs best on most tested instances. For the knapsack problem, the generalized assignment problem, and the set covering problem, we compare iDS with state-of-the-art results. The iDS algorithm successfully updates best-known records for a number of benchmark instances.

An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion / Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - (2022), pp. 1-18. [10.1287/ijoc.2022.1189]

An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion

Iori, Manuel;
2022

Abstract

We consider binary integer programming problems with the min-max regret objective function under interval objective coefficients. We propose a heuristic frame- work, the iterated dual substitution (iDS) algorithm, which iteratively invokes a dual substitution heuristic and excludes from the search space any solution already checked in previous iterations. In iDS, we use a best scenario–based lemma to improve performance. We apply iDS to four typical combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the generalized assignment problem, and the set covering problem. For the multidimensional knapsack problem, we compare the iDS approach with two algorithms widely used for problems with the min-max regret criterion: a fixed-scenario approach, and a branch-and-cut approach. The results of computational experiments on a broad set of benchmark instances show that the proposed iDS approach performs best on most tested instances. For the knapsack problem, the generalized assignment problem, and the set covering problem, we compare iDS with state-of-the-art results. The iDS algorithm successfully updates best-known records for a number of benchmark instances.
21-apr-2022
1
18
An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion / Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - (2022), pp. 1-18. [10.1287/ijoc.2022.1189]
Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori
File in questo prodotto:
File Dimensione Formato  
WuIoriMartelloYagiura2022.pdf

non disponibili

Descrizione: Articolo definitvo
Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 830.8 kB
Formato Adobe PDF
830.8 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: https://hdl.handle.net/11380/1274246
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
social impact