Solving a real world assignment problem with a metaheuristic

This paper investigates a real world assignment problem, which slightly differs from the classical generalized assignment problem. The large-scale number of variables in the related 0–1 linear program makes the use of commercial optimization packages impractical. We present here a metaheuristic using simulated annealing. It is based on successive reduction of the search space by identification of locally active constraints. Our approach employs a heuristic procedure to compute an initial (feasible or infeasible) 0/1 solution, and a double-criterion acceptance rule. The performance of the algorithm is demonstrated on real data sets.