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. - STAMPA. - 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

Martello, Silvano;
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.
2018
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. - STAMPA. - 125:(2018), pp. 98-110. [10.1016/j.cie.2018.08.007]
Wu, Wei*; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori
File in questo prodotto:
File Dimensione Formato  
Handle_MRKP_JOC_rev.pdf

accesso aperto

Tipo: Postprint
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione - Non commerciale - Non opere derivate (CCBYNCND)
Dimensione 413.62 kB
Formato Adobe PDF
413.62 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/683153
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? 19
social impact