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.
Wu, W., Iori, M., Martello, S., Yagiura, M. (2018). Exact and heuristic algorithms for the interval min-max regret generalized assignment problem. COMPUTERS & INDUSTRIAL ENGINEERING, 125, 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.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.