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

Salim Haddadi ()
Additional contact information
Salim Haddadi: 8 Mai 1945 University

4OR, 2019, vol. 17, issue 3, No 2, 295 pages

Abstract: Abstract 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.

Keywords: Generalized assignment; Variable-fixing; VLSN search; Subgradient optimization; Monotone binary program; 90B80; 90C06; 90C27; 90C59 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-018-0389-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:17:y:2019:i:3:d:10.1007_s10288-018-0389-z

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-018-0389-z

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().