|
|
 |
|
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. |
Vendredi 21 Mars
| Heure: |
10:00 - 12:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Can Dialectica break bricks? |
| Description: |
Pierre-Marie Pédrot
The Dialectica translation is a logical transformation described by
Gödel in 1958, but designed in the 30's. At the end of the 80's, it was
given a categorical counterpart, which happened to be compatible with
the usual decomposition of intuitionistic logic into linear logic.
Still, it was lacking a true Curry-Howard interpretation.
We will fill this hole by presenting the computational content of
Dialectica by means of an untyped lambda-calculus translation. We will
show that this translation has a really simple explanation as soon as we
put our source term in the Krivine abstract machine, except for a
disturbing detail, seemingly deeply rooted in linear logic. We will also
show how our presentation can be naturally applied to a
dependently-typed system almost without adaptation, thus giving a
hindsight on how linear dependent types may be built (or not). |
|
|
