Variable-fixing then subgradient optimization guided very large scale neighborhood search for the generalized assignment problem

We propose a two-phase heuristic for the generalized assignment problem (GAP). The first phase—a generic variable-fixing method—heuristically eliminates up to 98% of the variables without sacrificing the solution quality. The second phase takes as input the small reduced GAP obtained during the first phase and applies a very large scale neighborhood search. The definition of the successive exponential size neighborhoods is guided by the subgradient method applied to the Lagrangian relaxation of the knapsack constraints via the reduced costs. Searching the proposed neighborhood is NP-hard and amounts to solving a monotone binary program (BP) with m constraints and p variables, where m and p are respectively the number of agents and tasks of the reduced GAP (monotone BPs are BPs with two nonzero coefficients of opposite sign per column). To the best of our knowledge, this is the first time the above ideas are exposed. Extensive testing on large scale GAP instances is presented and previously unknown better values for eight instances are obtained. Comparison to well-established methods shows that this new approach is competitive and constitutes a substantial addition to the arsenal of tools for solving GAP.