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?
I have used a GAP as a subproblem in a previous project where the aim was to solve the single source capacitated facility location problem. I tried several things in order to speed up the computations, and found that the most effective approach was to use exact knapsack separation from the capacity constraints. That is, I basically solved the dual of the "natural" column generation master.
The way I implemented it was using CPLEX by first solving the LP relaxation at the root node, then I ran several cut-loops until I experienced too much trailing off. After that, I converted the problem to an IP and added a cut callback, which used the same separation routine as I used at the root node. After experimenting a bit, I found that I got the best results this way, as CPLEX wanted to stop the cut-loop at the root node earlier than I did. I am definitely not saying this is the best way to do it, but in my experience, it worked quite okay.
But, given that it is an NP-annoying (complexity class formally defined by @prubin, I think) problem, you will have to expect that in some cases the computation time explodes!
(You can find an implementation in c of a exact knapsack separation routine here: header source, the function you need is VICkpsep())
AFAIK, one of an efficient way to solve Generalized Assignment Problem (GAP), is using Branch and Price technique. I will hope, this or this link be useful.
