Exact and heuristic algorithms for the interval data robust assignment problem

Jordi Pereira, Igor Averbakh

Research output: Contribution to journalArticlepeer-review

36 Scopus citations

Abstract

We consider the Assignment Problem with interval data, where it is assumed that only upper and lower bounds are known for each cost coefficient. It is required to find a minmax regret assignment. The problem is known to be strongly NP-hard. We present and compare computationally several exact and heuristic methods, including Benders decomposition, using CPLEX, a variable depth neighborhood local search, and two hybrid population-based heuristics. We report results of extensive computational experiments.

Original languageEnglish
Pages (from-to)1153-1163
Number of pages11
JournalComputers and Operations Research
Volume38
Issue number8
DOIs
StatePublished - Aug 2011
Externally publishedYes

Keywords

  • Assignment problem
  • Benders decomposition
  • Genetic algorithm
  • Hybrid heuristic
  • Interval data
  • Minmax regret optimization

Fingerprint

Dive into the research topics of 'Exact and heuristic algorithms for the interval data robust assignment problem'. Together they form a unique fingerprint.

Cite this