Many real life optimization problems do not have accurate estimates of the problem parameters at the optimization phase. For this reason, the min-max regret criteria are widely used to obtain robust solutions. In this paper we consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. We show that the decision version of this problem is Σp2-complete. We present two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. For the fixed-scenario approach, we show that solving the classical GAP under a median-cost scenario leads to a solution of the min-max regret GAP whose objective function value is within twice the optimal value. We also propose exact algorithms, including a Benders' decomposition approach and branch-and-cut methods which incorporate various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances.

Algorithms for the Min-Max Regret Generalized Assignment Problem with Interval Data / Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori. - STAMPA. - 2015-:(2014), pp. 734-738. ((Intervento presentato al convegno 2014 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2014 tenutosi a Selangor, Malaysia nel 09/12/2014 - 21/12/2014 [10.1109/IEEM.2014.7058735].

Algorithms for the Min-Max Regret Generalized Assignment Problem with Interval Data

IORI, MANUEL;
2014

Abstract

Many real life optimization problems do not have accurate estimates of the problem parameters at the optimization phase. For this reason, the min-max regret criteria are widely used to obtain robust solutions. In this paper we consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. We show that the decision version of this problem is Σp2-complete. We present two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. For the fixed-scenario approach, we show that solving the classical GAP under a median-cost scenario leads to a solution of the min-max regret GAP whose objective function value is within twice the optimal value. We also propose exact algorithms, including a Benders' decomposition approach and branch-and-cut methods which incorporate various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances.
2014 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2014
Selangor, Malaysia
09/12/2014 - 21/12/2014
2015-
734
738
Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori
Algorithms for the Min-Max Regret Generalized Assignment Problem with Interval Data / Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori. - STAMPA. - 2015-:(2014), pp. 734-738. ((Intervento presentato al convegno 2014 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2014 tenutosi a Selangor, Malaysia nel 09/12/2014 - 21/12/2014 [10.1109/IEEM.2014.7058735].
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/1073378
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 1
social impact