2014

Heure:	12:00 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Problème de placement orthogonal
Description:	Petru Valicov Etant donné un conteneur rectangulaire C, on s'intéresse à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement et sans dépassement des bords de C. Une contrainte supplémentaire est prise en compte -- l'interdiction de rotation des items. Ce problème est NP-complet et est un sous-problème du problème de sac-à-dos orthogonal où à chaque item on associe un profit et on cherche le sous-ensemble d'items réalisable de profit total maximum. Fekete et Schepers ont introduit une caractérisation élégante des solutions du problème de placement en utilisant les graphes d'intervalles. Nous présentons une nouvelle caractérisation en utilisant des MPQ-arbres -- des structures de données qui encodent efficacement les graphes d'intervalles. Un des principaux avantages de cette caractérisation est un nombre plus restreint des solutions symétriques traitées lors de l'exécution de l'algorithme. Nous finiront par présenter une comparaison des résultats avec ceux de la littérature sur les jeux de données connus. Travail effectué en collaboration avec C. Joncour et A. Pêcher.

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.

Heure:	12:00 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	The robust vehicle routing problem with time windows and travel time uncertainty
Description:	Rosa Figueiredo This work addresses the robust vehicle routing problem with time windows. We are motivated by a problem that arises in maritime transportation where delays are frequent and should be taken into account. Our model only allows routes that are feasible for all values of the travel times in a predetermined uncertainty polytope, which yields a robust optimization problem. We propose two new formulations for the robust problem, each based on a different decomposition approach. The first formulation extends the well-known resource inequalities formulation by employing robust programming with recourse. The formulation is solved by a row-and-column generation algorithm. The second formulation generalizes a path inequalities formulation to the uncertain context and is solved through a row generation algorithm. In particular, we discuss efficient separation procedures. We compare the two formulations on maritime transportation instances.

Heure:	12:00 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Split Cuts and Separable Underestimator for non-convex quadratic problems
Description:	Emiliano Traversi In this work we investigate the computational potential of two tools for solving non-convex quadratic problems: split inequalities and separable underestimator. Split inequalities were first introduced by Letchford and further examined by Burer and Letchford. For small instances with box-constraints, we show that the resulting dual bounds are very tight.The gap can be further decreased by separating so-called non-standard split inequalities, which we examine in the case of ternary variables.Separable underestimator are used for solving constrained quadratic binary programming. Dual bounds are computed by choosing appropriate underestimators of the objective function that are separable but not necessarily convex. We explain how to embed this approach into a branch-and-bound algorithm and present experimental results for several classes of combinatorial optimization problems, including the quadratic shortest path problem, for which we provide the first exact approach available in the literature.

Heure:	12:00 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Polynomial-Time Search Algorithms for Combined Exponential and Classical Neighborhoods of the CARP
Description:	Stefan Irnich