A stepwise incomplete branch-and-bound method for the generalized assignment problem

An optimization based algorithm for solving the generalized assignment problem (GAP) is proposed in the paper. The primary concept underlying our algorithm is a stepwise incomplete branch and bound method guided by the information of bases and reduced costs revealed in solving linear programming (LP) relaxations of the GAP. We repeatedly used the information to fix binary integer variables of GAP at either 1 or 0 to obtain a reduced GAP. In addition, extended cover cuts generated with respect to the reduced GAP are then added before we start calling a branch and bound solver. The proposed algorithm was tested on several benchmark data sets with binary variables up to 148,000. The preliminary results obtained positively demonstrate that our algorithm appears to be effective and efficient.