2013

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.

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..

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.

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. 

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

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Reverse Chvatal-Gomory rank.
Description:	Roland Grappe We introduce the reverse Chvatal-Gomory rank r*(P) of an integral polyhedron P, defined as the supremum of the Chvatal-Gomory ranks of all rational polyhedra whose integer hull is P. A well-known example in dimension two shows that there exist integral polytopes P with r*(P) infinite. We provide a geometric characterization of polyhedra with this property in general dimension, and investigate upper bounds on r*(P) when this value is finite. This is a joint work with Michele Conforti, Alberto Del Pia, Marco Di Summa and Yuri Faenza. 

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Accelerated Column Generation for Cutting Stock and Bin Packing
Description:	Accelerated Column Generation for Cutting Stock and Bin Packing One successful method for solving the cutting stock (CS) and bin packing problem (BP) is branch-and-price.  The column generation master program is a set covering problem where columns correspond to feasibly filled bins that cover a subset of the items.  It is known that standard column generation suffers from slow convergence (tailing off).  For CS, valid inequalities on the dual prices of the covering constraints, so-called dual optimal inequalities, were identified to be helpful to mitigate the tailing off effect.  The presentation addresses three issues:  First, the standard approach is the a priori construction of dual optimal inequalities before solving the master program.  We show that the most violated inequalities can be easily identified in the column generation process and so be added dynamically.  For standard benchmark problems, computation times were approximately halved.  Second, for BP not all CS inequalities are dual optimal, i.e., fulfilled by at least one optimal solution of the LP-relaxation of the master program.  We present a way to handle these cases and to reconstruct primal feasible solutions needed in the branch-and-bound process.  Third, we generalize our results to the BP with conflicts.