2014

Heure:	12:00 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	An Exact Placement Approach for Optimizing Cost and Recovery Time under Faulty Multi-Cloud Environments
Description:	Felipe Di­az Sanchez Currently, Cloud brokers bring interoperability and portability of applications across multiple Clouds. In the future, Cloud brokers will offer services based on their knowledge of Cloud providers infrastructure to automatically and cost-effectively overcome performance degradation. In this paper, we present a Mixed-Integer Linear Program (MILP) that provides a cost-effective placement across multiple Clouds. Our MILP formulation considers parameters of Cloud providers such as price, configuration of VMs, network latency, and provisioning time. We evaluate the cost-effectiveness of deploying a Cloud infrastructure into a single or across multiple Cloud providers by using real prices and VM configurations. The results show that in some cases may be cost-effective to distribute the infrastructure across multiple Cloud providers. We also propose three placement policies for faulty multi-Cloud scenarios. The best of these policies minimizes the cost of the Cloud infrastructure under fixed provisioning time values.

Heure:	12:00 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Programmation linéaire mixte robuste avec variables de recours continues
Description:	Pierre-Louis Poirion Nous nous intéresserons aux problèmes linéaires mixtes bi-niveaux, c'est à dire aux problèmes dans lesquels le processus de décision est divisé en deux parties : dans un premier temps, les valeurs optimales des variables dites "de décisions" seront calculées ; puis, une fois que l'incertitude sur les données est levée, nous calculerons les valeurs des variables dites "de recours". Nous commencerons par résoudre un problème linéaire simplifié dans lequel l'incertitude porte seulement sur le membre droit des contraintes, et est modélisée par un polytope bien particulier. Nous supposerons en outre que le problème vérifie une propriété dite "de recours complet". Nous verrons alors une méthode permettant, à partir d'un programme robuste quelconque, de se ramener à un programme robuste équivalent dont le problème déterministe associé vérifie la propriété de recours complet. Avant de traiter le cas général, nous nous limiterons d'abord au cas où les variables de décisions sont entières. Nous testerons alors notre approche sur un problème de production.  Enfin, nous nous placerons dans un cadre probabiliste et chercherons à estimer la pertinence de l'ensemble d'incertitude choisi.

Heure:	12:00 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Capacity Planning for Natural Gas Transmission Networks
Description:	Jesco Humpola We present a procedure for capacity planning of large-scale real-world natural gas distribution networks. It decides which combination of network extensions such as additional pipelines, compressors or valves should be added to increase the network's capacity or enhance its operational flexibility. We formulate this as a mixed-integer nonlinear problem. A sub-problem has different convex reformulations. Hence we use a combination of linear outer approximation and NLP solution techniques to solve the MINLP. We show that every dual solution of the convex reformulations allows to generate capacity inequalities (or cutting planes) which reduce the overall solution time when added to the formulation. The dual solution also enables the measurement of infeasibility level of the scenario. Furthermore we give a primal heuristic for our model. We present computational results that are obtained by a special tailored version of the solvers SCIP and IPOPT.

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Circuit and bond polytopes in series-parallel graphs
Description:	Mathieu Lacroix We describe the circuit polytope in series-parallel graphs. We show the existence of a compact extended formulation for the latter, which inductively provides the description in the original space. As a consequence, using the link between bonds and circuits in planar graphs, we also describe the bond polytope in series-parallel graphs.This is a joint work with S. Borne, R. Grappe, P. Fouilhoux and P. Pesneau.

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.