# Generalized Assignment Problem as the sub-problem

I was wondering what is the state-of-the-art for solving the Generalized Assignment Problem (GAP) and if there are special cases that are polynomially solvable?

Moreover, is there any usage of this problem as a sub-problem within a decomposition algorithm such as Lagrangian relaxation algorithms?

(You can find an implementation in c of a exact knapsack separation routine here: header source, the function you need is VICkpsep())