TY - JOUR
T1 - Exact and heuristic algorithms for the interval data robust assignment problem
AU - Pereira, Jordi
AU - Averbakh, Igor
N1 - Funding Information:
The research of the first author was partially supported by the Spanish CICYT Grant DPI2007-63026. The research of the second author was supported by a discovery Grant from the Natural Sciences and Engineering Research Council (NSERC) of Canada.
PY - 2011/8
Y1 - 2011/8
N2 - 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.
AB - 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.
KW - Assignment problem
KW - Benders decomposition
KW - Genetic algorithm
KW - Hybrid heuristic
KW - Interval data
KW - Minmax regret optimization
UR - http://www.scopus.com/inward/record.url?scp=78650512128&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2010.11.009
DO - 10.1016/j.cor.2010.11.009
M3 - Article
AN - SCOPUS:78650512128
VL - 38
SP - 1153
EP - 1163
JO - Computers and Operations Research
JF - Computers and Operations Research
SN - 0305-0548
IS - 8
ER -