We consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. This problem models many real-world applications in which jobs must be assigned to agents but the costs of assignment may vary after the decision has been taken. We computationally examine two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. We also examine exact algorithmic approaches (Benders-like decomposition and branch-and-cut) and further introduce a more sophisticated algorithm that incorporates various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances.

Exact and heuristic algorithms for the interval min-max regret generalized assignment problem / Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori. - In: COMPUTERS & INDUSTRIAL ENGINEERING. - ISSN 0360-8352. - 125:(2018), pp. 98-110. [10.1016/j.cie.2018.08.007]

Exact and heuristic algorithms for the interval min-max regret generalized assignment problem

Iori, Manuel;MARTELLO, Silvano;YAGIURA, MUTSUNORI
2018

Abstract

We consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. This problem models many real-world applications in which jobs must be assigned to agents but the costs of assignment may vary after the decision has been taken. We computationally examine two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. We also examine exact algorithmic approaches (Benders-like decomposition and branch-and-cut) and further introduce a more sophisticated algorithm that incorporates various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances.
14-ago-2018
125
98
110
Exact and heuristic algorithms for the interval min-max regret generalized assignment problem / Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori. - In: COMPUTERS & INDUSTRIAL ENGINEERING. - ISSN 0360-8352. - 125:(2018), pp. 98-110. [10.1016/j.cie.2018.08.007]
Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori
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/1164978
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 14
social impact