|
|
 |
|
Mardi 8 Janvier
| Heure: |
12:30 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Aller-retour et voyageur de commerce dans les réseaux de transports urbain |
| Description: |
Pierre Parent Le problème de l'aller-retour se pose lorsque l'on dispose d'un véhicule
personnel, et que l'on peut faire une partie du trajet à l'aide de celui-ci,
et le restant via les transports en communs. Il s'agit alors de trouver quel
trajet choisir à l'aller et au retour, pour minimiser le temps total, sachant
que si la voiture est garée à un endroit à l'aller on doit passer la
rechercher à ce même endroit au retour.
Dans le problèmes de voyageur de commerce nous avons un certain nombre
d'endroit à visiter en ville, et il s'agit de trouver le trajet optimal
passant par tout ces points en utilisant les transports en commun. La difficulté
réside dans le fait que les trains, arrivent et partent à des heures fixées de
la journée.
Nous proposerons des méthodes de résolution pour les deux problèmes, ainsi que
des résultats expérimentaux. |
Mardi 29 Janvier
| Heure: |
12:30 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Combinaison automatique d'algorithmes et heuristiques |
| Description: |
Yanik Ngoko Sur de nombreux problèmes combinatoires comme SAT ou CSP, on peut
facilement trouver, étant donné un sous ensemble d'heuristiques, un sous
ensemble d'instances du problème sur lequel aucune heuristique ne domine
complètement les autres(*). Ceci a motivé de nombreux travaux ayant pour
but de combiner plusieurs heuristiques résolvant le même problème afin
d'exploiter leur diversité.
Dans cet exposé, nous nous intéressons à cette problématique en contexte
parallèle et homogène. Dans les solutions décrites, une combinaison est
obtenue en exécutant de façon concurrente dans le temps et dans l'espace
(coeurs, processeurs, régistres caches etc.) plusieurs heuristiques,
jusqu'à ce que l'une d'elles trouve une solution satisfaisante. Pour
apprendre à construire de telles combinaisons, nous proposons une
solution d'apprentissage basée sur une estimation du temps d'exécution
des heuristiques sur un jeu d'instances représentatives. Le coeur de
notre proposition peut être formulé comme un  problème combinatoire dont
nous prouvons la  np-completude et l'inapproximabilité. Nous proposons
pour sa résolution plusieurs heuristiques, avec garanti de performance
sous certaines hypothèses.
Finalement, nous présentons quelques résultats de notre approche de
combinaison sur les problèmes SAT et CSP.
(*) Par exemple dans le temps pris pour donner une solution satisfaisante.. |
Mardi 5 Février
| Heure: |
12:30 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Separable non-convex underestimators for binary quadratic programming |
| Description: |
Emiliano Traversi We present a new approach to constrained quadratic binary
programming. Dual bounds are computed by choosing appropriate global
underestimators of the objective function that are separable but not
necessarily convex. Using the binary constraint on the variables, the
minimization of this separable underestimator can be reduced to a linear
minimization problem over the same set of feasible vectors. For most
combinatorial optimization problems, the linear version is considerably
easier than the quadratic version. We explain how to embed this approach
into a branch-and-bound algorithm and present experimental results. |
Mardi 19 Février
| Heure: |
12:30 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Discrete optimization using semidefinite methods |
| Description: |
Angelika Wiegele Many real-world applications, although being non-linear, can be well
described by linearized models. Therefore, Linear Programming (LP)
became a widely studied and applied technique in many areas of science,
industry and economy. Semidefinite Programming (SDP) is an extension of
LP. A matrix-variable is optimized over the intersection of the cone of
positive semidefinite matrices with an affine space. It turned out, that
SDP can provide significantly stronger practical results than LP. Since
then SDP turned out to be practical in a lot of different areas, like
combinatorial optimization, control theory, engineering, and more
recently in polynomial optimization.
In this talk I will present some ideas how to model discrete
optimization problems using semidefinite programming in order to obtain
semidefinite relaxations. Some of this relaxations proved to be
succesful when using in a branch-and-bound framework. Furthermore, I
want to present a new idea of how to strengthen semidefinite relaxations.  |
Mardi 26 Février
| Heure: |
12:30 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
 Réservation de voies dans un réseau de transport |
| Description: |
Feng Chu |
|
|
