Relaxation techniques and valid inequalities applied to the generalized assignment problem

In this paper, the authors present two algorithms for the generalized assignment problem in which the bounds derived are generated through the use of surrogate and Lagrangean duality respectively, in conjunction with the addition and relaxation of valid inequalities. Fathoming tests are also carried out during the solution procedures in order to reduce the problem size. It is shown that the generation of valid inequalities combined with a relaxation strategy can give better lower bounds from the relaxed problems than those that can be obtained by standard applications of relaxation techniques (Lagrangean and surrogate). The methods are illustrated by a small example and computational tests are carried out on five problems with 100 0/1-variables.