|
|
 |
|
Mardi 18 Mars
| Heure: |
12:00 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Quelques projets autour de méthodes de génération de colonnes et d'algorithmes mémétiques |
| Description: |
Daniel Porumbel Après une introduction générale, la première partie de cette communication présentera en lignes générales quelques travaux sur deux axes de recherche. 1.Bornes duales à base de méthodes de génération de colonnes Deux projets sont évoqués: 1.A. Génération de Colonnes à Base d'un (Sous-)Problème d'Intersection De point de vue dual, la génération de colonnes fonctionne comme une méthode à base de plans sécants (e.g., "Kelley's cutting plane") dans le polytope dual P. Pour ajouter itérativement des contraintes duales (colonnes), la génération de colonnes fait appel à un sous-problème de séparation sur P. On propose une méthode qui permet d'optimiser P en faisant appel à un sous-problème d'inter- section au lieu du sous-problème de séparation. Ce sous-problème d'intersection demande d'avancer sur la direction 0->r d'un "rayon" r jusqu'au moment où on intersecte une facette de P. On génère une séquence de rayons r1, r2, ... qui convergent vers 0->OPT(P) où P est la solution dual optimale. Des résultats seront présentés pour quelques versions de Cutting-Stock et sur Arc-Routing 1.B. Méthodes d'agrégation duale Pour réduire la taille du polytope dual P, nous avons groupé et agrégé les variables duales en k groups. Cela permet d'obtenir un polytope agrégé Pk complètement inclus dans P. On augment k itérativement, et ainsi, OPT(Pk) converge vers OPT(P).2. Bornes primales à l'aide d'algorithmes "Spacing Memetic" Dans ce travail, nous proposons une méthode à base de distances entre solutions candidates pour contrôler la diversité de la population d'un algorithme mémétique. L'approche possède des similarités avec "MA|PM" (Memetic Algorithms with Population Management). La deuxième partie présente plus en détail le projet 1.A. ci-dessus, suivi de différentesperspectives. |
|
|
