Beam search for the elastic generalized assignment problem - Marcel Büther (Universität Kiel, Institut für Betriebswirtschaftslehre, 2008)
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.
Keywords: 650; elastic generalized assignment problem; mixed integer programming; beam search; Lagrangian relaxation; local search; binary representation; Mathematische Optimierung; Theorie