Beam search for the elastic generalized assignment problem

The elastic generalized assignment problem (eGAP) is a natural extension of the generalized assignment problem (GAP) where the capacities are not any longer fixed but can be adjusted which is expressed by continuous variables. These variables might be unbounded or restricted by a lower or upper bound, respectively. This paper describes an algorithm based on beam search, combined with Lagrangian relaxation and local search to provide strong lower as well as upper bounds for the eGAP.