• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

A two-phase path-relinking algorithm for the generalized assignment problem

Thumbnail
View/Open
path_relinking.pdf (169.3Kb)
Date
2001
Dewey
Recherche opérationnelle
Sujet
combinatorial optimization; assignment; heuristics
Conference name
4th Metaheuristics International Congress (MIC'01)
Conference date
07-2001
Conference city
Porto
Conference country
Portugal
URI
https://basepub.dauphine.fr/handle/123456789/5967
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Alfandari, Laurent
Plateau, Agnès
Tolla, Pierre
Type
Communication / Conférence
Item number of pages
13
Abstract (EN)
We propose a two-phase Path-Relinking (PR) heuristic for the NP-hard Generalized Assignment Problem. The first 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-off between feasibility and infeasibility is controlled through a penalty coefficient 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 efficiency of the method.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.