We introduce a new heuristic for the generalized assignment problem (GAP) based on the concepts of VLSN search and VN search. Our algorithm can be viewed as a k -exchange heuristic; but unlike traditional k -exchange algorithms, we choose larger values of k resulting in neighborhoods of very large size. Searching this exponential neighborhood (approximately) amounts to solving a sequence of smaller GAPs either by exact algorithms or by heuristics. Preliminary computational results on benchmark test problems are presented. The central idea of our heuristic may be used to develop efficient heuristics for other combinatorial optimization problems as well.