Solving a real world assignment problem with a metaheuristic

This paper investigates a real world assignment problem, which slightly dif fers from the classical generalized assignment problem (GAP). The large-sca le number of variables in the related 0-1 linear program makes the use of c ommercial optimization packages impractical. We present here a metaheuristi c using simulated annealing. It is based on successive reductions of the se arch space by identification of locally active constraints. Our approach em ploys a heuristic procedure to compute an initial (feasible or infeasible) 0/1 solution, and a double-criterion acceptance rule. The performance of th e algorithm is demonstrated on real data sets.