A two-phase path-relinking algorithm for the generalized assignment problem
Alfandari, Laurent; Plateau, Agnès; Tolla, Pierre (2001), A two-phase path-relinking algorithm for the generalized assignment problem, 4th Metaheuristics International Congress (MIC'01), 2001-07, Porto, Portugal
TypeCommunication / Conférence
Conference title4th Metaheuristics International Congress (MIC'01)
MetadataShow full item record
Abstract (EN)We propose a two-phase Path-Relinking (PR) heuristic for the NP-hard Generalized Assignment Problem. The ﬁrst phase of the algorithm combines LP-solving, cuts and local search for obtaining a population of solutions with guided diversity. The second phase applies the PR template to the population built at phase one. Both feasible and infeasible solutions are inserted in the reference set during combinations of PR. The trade-oﬀ between feasibility and infeasibility is controlled through a penalty coeﬃcient for infeasibility which is dynamically updated throughout the search for maintaining a balance between feasible and infeasible solutions in the reference set. Numerical experiments on classical testbed instances of the OR-library show the practical eﬃciency of the method.
Subjects / Keywordscombinatorial optimization; assignment; heuristics
Showing items related by title and author.
Valid Inequalities and Branch-and-Cut Algorithm for the Constrained-Routing and Spectrum Assignment Problem Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021) Document de travail / Working paper