Séminaires ROC

Liste des Séminaires ROC

2019

[19 juillet 2019] Séminaire ROC par Claude-Guy Quimper (Univ. Laval, Québec)

Nouvel algorithme de filtrage pour le raisonnement énergétique de la contrainte Cumulative

Par Claude-Guy Quimper, Professeur (Université Laval ) - Email: Claude-Guy.Quimper@ift.ulaval.ca - Site: http://www2.ift.ulaval.ca/~quimper/

Date: Vendredi, 19 juillet, 2019 - 11:00

Lieu : LAAS-CNRS - Salle Europe 7 avenue du Colonel Roche 31077 TOULOUSE Cedex 4

Résumé : En programmation par contraintes, la contrainte Cumulative permet de modéliser des problèmes d'ordonnancement où n tâches s'exécutent sans interruption. Des tâches peuvent s'exécuter simultanément pourvu que le taux d'utilisation total de la ressource ne dépasse pas sa capacité. Les solveurs de contraintes utilisent des algorithmes de filtrage afin de réduire la taille de l'arbre de recherche et ainsi réduire le temps de résolution d'un problème. Je présenterai un nouvel algorithme de filtrage basé sur le raisonnement énergétique. Ce raisonnement, qui permet de filtrer fortement l'espace de recherche, a longtemps souffert d'algorithmes trop lents pour être utilisé en pratique. Je présenterai le premier test du raisonnement énergétique dont le temps d'exécution est sous-quadratique: O(n log^2 n). Je présenterai aussi l'algorithme de filtrage associé à ce test qui s'exécute en O(n^2 log n).

Biographie :
Claude-Guy Quimper est professeur agrégé au département d'informatique et de génie logiciel à l’Université Laval. Ses recherches portent sur la programmation par contraintes, la recherche opérationnelle, la conception d'algorithmes et l'ordonnancement. Diplômé au doctorat de l'Université de Waterloo, il a été visiteur chez NICTA et stagiaire chez Microsoft Research. Il a fait un postdoctorat à l'École Polytechnique de Montréal sous la supervision du professeur Gilles Pesant. Il a travaillé dans l'industrie chez Oméga Optimisation, avec Louis-Martin Rousseau, et chez Google.

Mots-clés : Ordonnancement; Raisonnement énergétique; Programmation par contraintes 

[11 juillet 2019] Séminaire ROC par Gilles Hétreux (ENSIACET)

Optimisation des utilités dans les procédés industriels

Par Gilles Hétreux, Maître de Conférences (Laboratoire de Génie Chimique, Toulouse INP-ENSIACET) - Email:  gilles.hetreux@ensiacet.fr

Date: Jeudi, 11 juillet, 2019 - 11:00

Lieu : LAAS-CNRS - Salle Feynman 7 avenue du Colonel Roche 31077 TOULOUSE Cedex 4

Résumé :Dans un contexte de transition énergétique et numérique, l’Usine du Futur se définit entre autre comme économe en énergie. Aujourd’hui en France, plus de 25% de la consommation énergétique finale annuelle est attribué au secteur industriel, énergie utilisée à 70 % pour produire les utilités (vapeur, froid, air comprimé, électricité, etc.). Afin de limiter leur impact économique et environnemental, différents axes d’amélioration de l’efficacité énergétique de ces systèmes industriels existent. Dans cet exposé, deux d’entre eux sont présentées :

  • La première s’appuie sur le concept d’intégration énergétique et la mise en œuvre de réseaux d’échangeurs de chaleur. La modélisation du problème de synthèse de tels réseaux s’appuie sur un graphe de flot biparti avec contraintes de potentiel, graphe utilisé pour établir un modèle de programmation linéaire mixte. Différentes extensions sont ensuite décrites.
  • Le deuxième axe concerne la conduite de ces unités et notamment, la fonction d’ordonnancement. Pour cela, un modèle de programmation linéaire mixte à temps discret est exploité. L’instanciation de ce modèle s’appuie sur un graphe spécifique (Extended Resource Task Network) permettant de décrire de manière non ambigüe les processus de production. L’application de ce modèle est illustrée sur deux catégories de système :
    • un atelier du secteur de l’agroalimentaire soumis à nettoyage et dont l’utilité (ou ressource) critique est l’eau.
    • une centrale d’utilités permettant une production combinée chaleur/électricité (cogénération) dont on cherche à optimiser la rentabilité en la positionnant comme un acteur du marché de l’énergie

[4 juillet 2019] Séminaire ROC par Mike Hewitt (Univ. Chicago)

Dynamic Discretization Discovery for Solving the Time-Dependent Traveling Salesman Problem with Time Windows

Par Mike Hewitt, Associate Professor (Quinlan School of Business, Loyola University Chicago) - Email: mhewitt3@luc.edu

Date: Jeudi, 4 juillet, 2019 - 11:30

Lieu : LAAS-CNRS - Salle Feynman 7 avenue du Colonel Roche 31077 TOULOUSE Cedex 4

Résumé : We present a new solution approach for the Time Dependent Traveling Salesman Problem with Time Windows. This problem considers a salesman who departs from his home, has to visit a number of cities within a predetermined period of time, and then returns home. The problem allows for travel times that can depend on the time of departure. We consider two objectives for the problem: (1) a makespan objective that seeks to return the salesman to his home as early as possible, and, (2) a duration objective that seeks to minimize the amount of time he is away from his home. The solution approach is based on an integer programming formulation of the problem on a time expanded network, as doing so enables time dependencies to be embedded in the definition of the network. However, as such a time expanded network (and thus the integer programming formulation) can rapidly become prohibitively large, the solution approach employs a dynamic discretization discovery framework, which has b! een effective in other contexts. Our computational results indicate that the solution approach outperforms the best-known methods on benchmark instances and is robust with respect to instance parameters.

[23 mai 2019] Séminaire ROC par Pierre Schaus (Université Catholique de Louvain)

Discovering Regions of Interest in Trajectory Mining

Par Pierre Schaus, Professeur (Université catholique de Louvain) - Email: pierre.schaus@uclouvain.be - Site: https://www.info.ucl.ac.be/~pschaus/

Date: Jeudi, 23 mai, 2019 - 11:00

Lieu : LAAS-CNRS - Salle Feynman 7 avenue du Colonel Roche 31077 TOULOUSE Cedex 4

Résumé: Trajectory pattern mining has emerged as a practical approach to analyze and understand human mobility. Starting from a large set of trajectories, the goal is to extract spatio-temporal patterns shared among a significant number of trajectories. Based on the approach of Giannotti et al., this problem can be solved in two steps: 1) identification of regions of interest (ROI) and 2) detection of frequent sub-sequences expressed as ROIs.} This work focuses on the discovery of the regions of interest. We formulate the problem as a well-defined optimization problem aiming to compress the dense regions with parameterized shapes, such as rectangles. We give an extended linear programming formulation of the problem. Relying on the Minimum Description Length Principle, we show how the model can be transformed to also discover the number of regions of interest. Our experiments on real data and synthetic data show that the proposed approach is able to retrieve regions of interest of higher quality than those extracted with the existing greedy PopularRegion algorithm.

[11 avril 2019] Séminaire ROC par Maximilian Pohl (M.Sc, Univ Munich)

Runway Scheduling during Winter Operations

Par Maximilian Pohl M.Sc. (Université de Munich) - Email: maximilian.pohl@tum.de

Date: Jeudi, 11 avril, 2019 - 11:00

Lieu : LAAS-CNRS - Salle Feynman 7 avenue du Colonel Roche 31077 TOULOUSE Cedex 4

Résumé: We address the runway scheduling problem under consideration of winter operations. During periods of snowfall, runways have to be intermittently closed in order to clear them from snow, ice and slush. We propose an integrated discrete optimization model to simultaneously plan snow removal for multiple runways and to assign runways and starting and landing times to aircraft. 
We present a time discrete model formulation using clique inequalities. We combine Constraint Programming with a Column Generation approach to solve real-world data from Munich International Airport to optimality.

[7 février 2019] Séminaire ROC par Xavier Lorca (Ecole des Mines Albi)

Éléments de flexibilité et d'efficacité en programmation par contraintes

Xavier Lorca, Directeur du centre Génie Industriel (École des mines Albi) - Email: xavier.lorca@mines-albi.fr - Site: https://www.imt-mines-albi.fr/fr/xavier-lorca

Date: Jeudi, 7 février, 2019 - 11:00

Lieu : LAAS-CNRS - Salle Feynman 7 avenue du Colonel Roche 31077 TOULOUSE Cedex 4

Résumé : Cet exposé résume une tranche de 10 ans de travaux que j’ai menés autour des outils à base de contraintes. J’y parlerais tout d'abord de la structure de ces outils avec un large focus sur les contraintes globales et plus particulièrement des contraintes à base de graphes. Je parlerais ensuite de tentatives pour faire évoluer ces outils vers plus de flexibilité au détriment, malheureusement de l’efficacité. Je terminerais enfin sur une palette d’applications que j’ai pu aborder dernièrement allant de problèmes très classiques de (re-)planification à des problèmes plus exotiques liés au dimensionnent et à la sélection de réserves naturelles. 

2018

29 novembre 2018 - Séminaire ROC par Silvano Dal Zilio (Vertics, LAAS)

Trois occasions où je suis venu frapper à la porte de ROC

Silvano Dal Zilio ; Chargé de recherche (LAAS-CNRS équipe VERTICS) - Email: dalzilio@laas.fr

Date : Jeudi, 29 novembre, 2018 - 11:00

Lieu : LAAS-CNRS - Salle Bardeen 7 avenue du Colonel Roche 31077 TOULOUSE Cedex 4

Résumé : Dans cet exposé, je parlerais des travaux réalisés dans l'équipe Vertics en essayant de mettre en perspectives des résultats qui peuvent intéresser la communauté "optimisation combinatoire". L'exposé abordera les questions de l'utilisation des symétries dans le cas de systèmes exhibant des contraintes temporelles. Je vous parlerai également de méthodes symboliques et d'une nouvelle application pour les méthodes permettant de calculer le nombre de solutions positives d'un système linéaire diophantien.

6 septembre 2018 : Séminaire ROC par Nathann Cohen, Chargé de recherche (CNRS; LRI)

Quelques preuves de Noga Alon autour du vote de Condorcet

Nathann Cohen, Chargé de recherche (CNRS; LRI) - Email:  nathann.cohen@gmail.com - Site: https://www.steinertriples.fr/ncohen/

Date: Jeudi, 6 septembre, 2018 - 11:00

Lieu : LAAS-CNRS - Salle de Conférences 7 avenue du Colonel Roche 31077 TOULOUSE Cedex 4

Résumé :On parlera de votes de Condorcet, de jeux à somme nulle, de probabilités et d'écart-type, d'arrondis entiers, de permutations et de graphes dirigés. On suivra pour cela l'article intitulé "Voting paradoxes and digraphs realizations"

 

4 et 5 juin 2018 : Master Class "Méthodes hybrides pour l'optimisation combinatoire/mixte au LAAS – Labex CIMI

Le Labex CIMI de Toulouse a financé une Master Class sur les Méthodes Hybrides pour l'Optimisation Combinatoire/Mixte, qui a eu lieu au LAAS les 4 et 5 juin 2018. L'évènement a été organisé en collaboration avec l'ENAC (Sonia Cafieri), l'ISAE (Olga Battaïa), l'INRA (George Katsirelos), l'IRIT (Hélène Fargier), l'IMT (Aude Rondepierre) et le LAAS (Christian Artigues).

  • John Hooker (Cargegie Mellon University) - "Hybrid mixed-Integer Programming and Constraint Programming Methods" lien vers les planches - lien vers les vidéos (Partie 1, Partie 2, Partie 3)
  • Laurent Simon (LABRI, Bordeaux) - "Understanding, using and extending SAT solvers" lien vers les planches - lien vers la vidéo, lien vers le solveur pysat et les exercices
  • Willem van Hoeve (Carnegie Mellon University) - "Decision diagrams for Discrete Optimization, Constraint programming, and Integer Programming" lien vers les planches, lien vers les vidéos (Partie 1, Partie 2) 
  • Jean Bernard Lasserre (LAAS-CNRS, Toulouse) - "Moments & Positive Polynomials in and outside Optimization" lien vers les planches, lien vers la vidéo 
  • Paul Shaw (IBM Research) - "Combinations of local search and constraint programming" lien vers la vidéo

 

8 février 2018 - Séminaire ROC par Olivier Stasse (Equipe Gepetto, LAAS)

Optimization for humanoid robot motion generation

Résumé : In this talk, I will describe the various optimization problems used in the Gepetto team to generate motion for complex robotic systems such as humanoid robots. The main requirement is to provide every 5 ms on HRP-2 or every 1ms on Pyrene the control value for each of the 30 motors. The variables of the problem evolved on manifolds corresponding to the mechanical constraints. Some constraints are always active: balance, self-collision avoidance, joint limits torque limits, while others such as contact are non-smooth and switch according to the situation. The phase sequence can be represented by a finite state machine. This finite state machine is classically build by hand and used as a supervisor during the motion execution. Indeed the tangent space of the constraints is used on-line to adapt the robot control to the sensor information, disturbances, and errors in the model.  It has been used recently in our group to generate automatically such finite state! machine. The scientific challenges on applying this technique to industrial applications will be highlighted. Our current approaches to react to strong modifications of the environment will be presented.

2017

(Voir Onglet ROC Sessions pour les autres présentations)

  • 13 décembre 2017 - Abdallah Saffidine (University of New South Wales) The Parameterized Complexity of Positional Games

Abstract : We study the parameterized complexity of several positional games. Our main result is that Short Generalized Hex is W[1]-complete parameterized by the number of moves. This solves an open problem from Downey and Fellows’ influential list of open problems from 1999. Previously, the problem was thought of as a natural candidate for AW[*]-completeness. Our main tool is a new fragment of first-order logic where universally quantified variables only occur in inequalities. We show that model-checking on arbitrary relational structures for a formula in this fragment is W[1]-complete when parameterized by formula size. We also consider a general framework where a positional game is represented as a hypergraph and two players alternately pick vertices. In a Maker-Maker game, the first player to have picked all the vertices of some hyperedge wins the game. In a Maker-Breaker game, the first player wins if she picks all the vertices of some hyperedge, and the second player wins ot! herwise. In an Enforcer-Avoider game, the first player wins if the second player picks all the vertices of some hyperedge, and the second player wins otherwise. Short Maker-Maker, Short Maker-Breaker, and Short Enforcer-Avoider are respectively AW[*]-, W[1]-, and co-W[1]-complete parameterized by the number of moves. This suggests a rough parameterized complexity categorization into positional games that are complete for the first level of the W-hierarchy when the winning condition only depends on which vertices one player has been able to pick, but AW[*]-complete when it depends on which vertices both players have picked. However, some positional games with highly structured board and winning configurations are fixed-parameter tractable. We give another example of such a game, Short k-Connect, which is fixed-parameter tractable when parameterized by the number of moves.

This is joint work with Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, and Stefan Rümmele (ICALP 2017).

Mots-clés : Complexité, jeux combinatoires

  • 30 juin 2017  - Alexandre Papadopoulos (Sony CSL, Université Pierre et Marie Curie). Génération automatique et interactive de partitions musicales avec FlowComposer.

Résumé : En 2002, François Pachet inventait Continuator, un des premiers systèmes capables de composer de la musique en apprenant le style de son utilisateur, et en totale interaction avec celui-ci. Continuator utilisait un modèle statistique de Markov capable de générer une séquence de symboles, tels une note, une durée, ou tout autre dimension musicale. En 2016, dans une équipe réunissant des membres du LIP6 et de Sony CSL sous le projet FlowMachines, nous produisons FlowComposer, un système qui compose interactivement des «lead sheets», en se conformant à un style musical et à des contraintes imposées par son utilisateur. Une lead sheet est une partition qui représente ce qui définit une chanson : sa mélodie et sa grille harmonique. Grâce à l'utilisation d'un modèle complexe de lead sheet, nous savons maintenant gérer simultanément plusieurs modèles de Markov, pour la mélodie et l'harmonie, soumis à un riche langage de contrai! ntes, régissant la métrique, la structure et d'autres considerations temporelles, ainsi que des contraintes utilisateur.

FlowComposer est utilisé avec succès par des compositeurs professionels. Benoît Carré s'en est servi pour créer la chanson «Daddy's Car», ayant reçu plus d'un million et demi de vues sur YouTube. Un album complet est actuellement en préparation, réunissant plusieurs compositeurs de prestige. En retraçant l'historique du projet, j'expliquerai les différentes étapes qui ont mené au développement de FlowComposer, en les illustrant par de nombreux exemples, et je ferai le point sur nos problèmes encore ouverts dans le domaine de l'échantillonnage de modèle statistiques sous contraintes. 

  • 06 Avril 2017 - Alessandro Agnetis (Univ Siene, Italy). Integrated production and delivery scheduling with inventory holding costs (joint work with Mohamed Ali Aloulou et Mikhail Kovalyov)

Résumé : In order to enhance performance level in a supply chain, it is crucial to coordinate the decisions of involved actors, namely suppliers, manufacturers, 3PL providers, and customers. We consider a scenario with a single manufacturer (modeled as a single machine), processing a specific set of jobs (products). Each job requires a certain processing time. After their processing is completed, products are shipped to a single customer by means of vehicles. The set of jobs assigned to the same vehicle in one delivery is called a delivery batch. Resulting problems consist in concurrently finding: i) a production schedule of the jobs on the machine, ii) a partition of jobs into delivery batches, and iii) an assignment of delivery batches to vehicles (and hence, to delivery times), so that total costs are minimized.

We focus on scenarios characterized by the following distinctive features:  1) Fixed delivery dates. There is a set of fixed departure times, and for each of them there is a number of vehicles. In general, there exist both per-product and fixed delivery costs.  2) Inventory holding costs. These costs are proportional to the length of the time span from a job completion time to its delivery departure time. Within this general framework, in this talk we present a number of results.

i) Problems are NP-hard (in the ordinary sense) even if there are onlytwo departure dates, no delivery costs, no deadlines, and all holding costs are identical.

ii) For the single-manufacturer case, we address the cases with unit processing times for all jobs. We provide polynomial algorithms for the problems when either of the following issues holds: vehicles have limited capacity, the number of delivery batches is limited, jobs deadlines are specified. We also discuss some open issues.

  • 21 Mars 2017 - Journée MAORE-ROC

Une journée d'échanges scientifiques entre l'équipe MAORE du LIRMM et l'équipe ROC s'est déroulée le 21 Mars en salle de conférences. Au programme, 3 présentations MOARE (Michael Poss, Rodolphe Giraudeau et Eric Bourreau) et 3 présentations ROC (Laurent Houssin, Margaux Nattaf et Nicolas Jozefowiez) sur les thèmes de la robustesse, de la complexité, des méthodes hybrides PLNE/PPC, des méthodes de programmation mathématique bi-objectif.

2016

(Voir Onglet ROC Sessions pour les autres présentations)

  • 19 octobre 2016 - Tamas Kis (Computer and Automation Research Institute of the Hungarian Academy of Sciences) a donné un séminaire intitulé "Complex Scheduling Problems" dans le cadre des séminaires du thème Décision et Optimisation.

Résumé : In the talk, I give an overview of some of my past work on project and machine scheduling problems including project scheduling with variable intensity activities, resource leveling in a machine environment, and bilevel machine scheduling problems.

  • 29 septembre 2016 - Romain Guillaume (UT2, IRIT) a donné un séminaire intutulé "Plan de production robuste sous incertitude de la demande modélisée par des distributions de possibilité".

Résumé : Cette présentation traite d'un problème de planification de la production mono-produit avec une demande incertaine modélisé par des intervalles flous dont les fonctions d’appartenance sont des distributions de possibilité. Nous nous intéressons à un critère d'optimisation, dans le cadre de la théorie des possibilités, qui conduisent à choisir des plans de production robustes sous incertitude de la demande. Des Algorithmes sont proposés pour calculer des plans optimaux de production robustes. De plus des résultats  expérimentaux seront présentés.

  • 21 septembre 2016 - Séminaires de Lorena Pradenas et Victor Parada (Universidad de Santiago de Chile​ / Universidad de Concepción)
    •     Lorena Pradenas : Optimizing nutritional menus for healthy meals
    •     Victor Parada : Automatic generation of algorithms for optimization problems

Résumé : Optimizing nutritional menus for healthy meals by Lorena Pradenas: The nutritional menu planning problem (NMPP) consists of assigning meals to an established structure of mealtimes and dishes. The traditional menu must fulfill several requirements, such as being inexpensive, meeting nutrient requirements, satisfying the conditions of the food pyramid, and so on. In this study, a multi-objective mathematical model for planning traditional menus for several days is proposed. The objectives of this study are to improve the minimum cost and adequacy of the menu. The model is tested with an actual case containing 73 meals. The model is solved by scaling through the e-constraint method. The results present a Pareto efficient frontier. The strength of this approach is that the proposed model can be used for different types of patients and users, providing a tool for decision-making in the public health area.

Résumé : Automatic generation of algorithms for optimization problems by Víctor Parada: The design of efficient algorithms for difficult combinatorial optimization problems is still a challenging field. In fact, designing an algorithm intended to solve an optimization problem is also an optimization task in which the performance should be optimized on a solution space composed by all possible algorithms that solve such problem. Thus, by means of an appropriate searching method, the best algorithm for the problem can be determined, and consequently, the design of an algorithm is a task that can be tackled by a computer. The search method in this case is genetic programming that, from an initial set of potential components of an algorithm, allows the evolution of new algorithms by gradually assembling the components in a tree of instructions. In this talk a procedure to automatically produce new algorithms for optimization problems is described and algorithms generated in this way for the binary knapsack, and travelling salesman problems are presented.

  • 15 septembre 2016 - Séminaire de Denis Arzelier (ROC) - "Linearized Fuel-Optimal Space rendezvous: Some theoretical and numerical aspects"

Résumé: The optimal fuel impulsive time-fixed rendezvous problem is shortly reviewed in the context of the more general problem of impulsive optimal control. In a linear setting, it may be reformulated as a non convex polynomial optimization problem for a pre-specified fixed number of velocity increments. Some theoretical results are first recalled and different algorithms are presented. In particular, when addressing the problem of a free number of maneuvers, one has to resort to a mixed iterative algorithm involving the solution of a convex optimization problem at each step.  Examples of realistic rendezvous missions will illustrate this talk.

  • 13 septembre 2016 - Séminaire de Patrick Schittekat (SINTEF) - "Presentation of the Applied Mathematics and Optimization Group at SINTEF".

Résumé :  SINTEF is the largest independent research institute in Scandinavia (www.sintef.no/en) . This non-profit foundation with its 2000 employees performs applied research in a variety of research fields going from Renewable Energy over Nanotechnology to optimization-based Decision Support Systems. In this seminar, Patrick would like to share a quite broad picture of SINTEF and the focus areas of SINTEFs department Applied Mathematics and Optimization Group. If time permits, we could touch upon some more recent on-going work such as human-machine collaboration and its importance.  The goal of this seminar is to be interactive and find some potential collaboration topics to work together on in the future.

  • 9 juin 2016 - Eliott Roynette (ONERA, ADS) - Designing Spacecraft Command Loops Using Two-dimension Vehicle Routing

2015

  • 3 décembre 2015 - Séminaire de Yun He (ROC). Pour la V0 des Roc'Sessions, Yun a présenté le travail qu'elle développe dans le cadre de sa thèse sur l'Inventory Routing Problem et son application au challenge ROADEF/EURO.

Résumé : le challenge ROADEF/EURO 2016 consiste à résoudre un problème industriel de transfert de gaz pour Air Liquide. Ce problème est classifié comme "Invetory Routing Problem (IRP) dans la littérature, avec des caractéristiques propres à l'application proposée par Air Liquide. Dans cette présentation, je vais présenter l'IRP et ses spécificités pour ce challenge. Ensuite, je vais parler des méthodes de résolution en développement. L'équipe ROC participant au challenge est composée de Yun, Cyril, Nicolas, Christian et Sandra.

  • 16 octobre 2015 - Séminaire de Dimitrios Letsios (Univ. Nice Sophia Antipolis) - Algorithms for Energy Efficiency in Computing Systems

Résumé : Energy consumption of computing devices has become an important issue nowadays. Two major mechanisms for energy management in the system level are dynamic speed scaling and transitions into low-power sleep states.In this context, there is an increasing interest for efficient algorithms  which compute good trade-off solutions with respect to energy consumption and performance. The goal of the talk is to present algorithmic techniques with provably good performances for fundamental problems of the area.

  • 23 juillet 2015 - Séminaire de Roel Leus (KU Leuven, Belgique)  - An exact algorithm for parallel machine scheduling with conflicts.

Résumé : We consider an extension of classic parallel machine scheduling, where an undirected conflict graph is part of the input. Each node in the graph represents a job and an edge implies that its two jobs cannot be scheduled on the same machine. The goal is to find an assignment of the jobs to the machines such that the maximum completion time is minimized. We present an exact algorithm based on branch and price.

  • 15 juillet 2015 - Séminaire d'Alain Hait (ISAE, chercheur associé ROC) - Modèles à temps mixte pour la planification et l'ordonnancement d'activités: bilan et perspectives.

Résumé : Les modèles traditionnels de planification et d'ordonnancement de projets et de production sont soit à temps continu, soit à temps discret. Le choix dépend de la difficulté de modélisation et résolution du problème, ainsi qu'éventuellement de l'application. Nous avons proposé des modèles originaux à temps mixte, c'est-à-dire qui mélangent temps continu et discret, pour ces mêmes problèmes. Ils se distinguent par une grande souplesse de modélisation (permettent de choisir la structure temporelle la plus intéressante pour représenter telle ou telle contrainte) et ont montré des performances de bon niveau pour la résolution. Je présenterai un bilan des travaux menés depuis une dizaine d'année en collaboration avec l'équipe ROC et les poursuites envisagées sur ce thème, qui reste encore largement ouvert.

  • 8 juillet 2015 - Séminaire de Frédéric Semet (Ecole Centrale de Lille) - Reactive optimization methods for a field service routing problem with stochastic travel and service times. Ce séminaire est issu d'un travail conjoint avec Sixtine BINART, Michel GENDREAU, Pierre DEJAX.

Résumé : In this talk, we consider a single period problem in which a service company must design tours for its field technicians in order to provide specific services to its customers in the most cost effective fashion.
Each tour (or route)corresponds to the sequence of customers that a given field service technician is scheduled to visit during that period. A key feature of the problem is that both travel times between locations and service times of customers are stochastic.
 To solve this problem, we propose three different solution approaches consisting in a planning stage followed by an execution stage. In the planning stage, we assume that minimal, modal and maximal values for travel and service times are  known a priori and we use these values to build routes. In the execution stage, we use a dynamic programming algorithm to determine the optimal policy, given the realization of the stochastic values for travel and service times.
The proposed solution approaches have been tested and validated on instances based on realistic data. Simulations were also run to assess the effectiveness of these approaches with stochastic travel and
service times. Results from the computational experiments and the simulations will be reported and discussed.

  • 8 juin 2015 -  Séminaire d'Hadrien Cambazard (G-Scop, Grenoble) - Lagrangian relaxation for domain filtering: the case of the NValue global constraint

Résumé : Lagrangian relaxation (LR) is a very important technique in operations research to reformulate and solve an integer linear program. From a Constraint Programming (CP) point of view, it offers a very simple and powerful framework to perform cost-based filtering. We believe that LR can provide relatively generic and powerful mechanisms for domain filtering in CP. We investigate the case of a well-known global constraint, AtMostNValue, and presents a new filtering algorithm for this constraint based on LR.

The AtMostNValue global constraint, which restricts the maximum number of distinct values taken by a set of variables, is a well known NP-Hard global constraint. The weighted version of the constraint, AtMostWValue, where each value is associated with a weight or cost, is a useful and natural extension. Both constraints occur in many industrial applications where the number and the cost of some resources have to be minimized.

  • 26 mai 2015 - Séminaire de Nestor Miguel Cid Garcia (Universidad Autonoma de Nuevo León) - Exact solutions for the 2D-bin packing problems using integer linear programming.

Abstract: We present a novel MIP-based two-stage approach to solve the two-dimensional bin packing problem (2DBPP). In the literature, the best resolution methodologies focussed on metaheuristics methods, which do not guarantee the solution quality. Therefore the optimality of the best known solutions from the 2DBPP benchmark had not been proven. With our approach we were able to solve optimally medium-sized instances. An overview about the work developed during the research stay with the ROC team at LAAS also is presented, which aimed at solving larger instances.

  • 13 mars 2015 - Séminaire de Martin Fink (TUM, School of Management) - Synchronized Worker and Vehicle Routing for Ground Handling at Airports.

Abstract: Ground handling planning deals with routing workers to jobs while meeting each job's timeliness, qualification requirement and workforce demand. Workers with hierarchical skills use vehicles to travel to another job, which calls for movement synchronization. We introduce a new problem, the vehicle routing problem with worker and vehicle synchronization (VRPWVS), propose a mathematical model and a hybrid metaheuristic with tabu search, guided local search and large neighborhood search.Ground handling planning deals with routing workers to jobs while meeting each job's timeliness, qualification ! requirement and workforce demand. Workers with hierarchical skills use vehicles to travel to another job, which calls for movement synchronization. We introduce a new problem, the vehicle routing problem with worker and vehicle synchronization (VRPWVS), propose a mathematical model and a hybrid metaheuristic with tabu search, guided local search and large neighborhood search.

  • 16 janvier 2015 - Séminaire de Christos Dimopoulos (European University Cyprus)  - Design of interdisciplinary Decision Support Systems in SME environments

Abstract : The talk will introduce i-DESME, an interdisciplinary framework for the design of IT scheduling Decision Support Systems in small-sized SME industrial environments. The proposed framework aims to help practitioners in such environments design support systems which are not only effective, but are also being trusted and adopted for use by human schedulers. The talk will also introduce the activities of the Decision Support & Systems Optimisation (DSSO) research laboratory.

2014

  • Dominique Feillet (Ecole des mines de Saint-Etienne)  - Multi-Variant Time Constrained FlexRay Static Segment Scheduling
    Date : 07 novembre 2014 à 14h00 - salle Hourgade
    In this presentation, a variant of the Vehicle Routing Problem, namely the Vehicle Routing Problem with Swap Bodies (SB-VRP) is investigated. This typ! e of problem involves swap locations where different actions can take place. For example, the swap body can be parked in order to visit customers where only a truck configuration can be used. For supporting the planning of a SB-VRP, an Iterated Variable Neighborhood Search is formulated. Computational results are provided and the solvability of the model under different types of test instances, which are released by the VeRoLog Solver Challenge 2014, is assessed.
  • Jan Dvorak (Czech Technical University in Prague)  - Multi-Variant Time Constrained FlexRay Static Segment Scheduling
    Date : 02 octobre 2014 à 14h00 - salle Vignemale
    The FlexRay bus is a modern standard used in the automotive industry. It offers deterministic message transmission with zero jitter while using time-triggered scheduling in the static segment. When several vehicle variants (i.e. different models and their versions) share the same signal, the car manufacturers require to schedule such signal at the same time in all vehicle variants. This requirement simplifies the signal traceability and diagnostics in different vehicle variants using the same platform and simplifie! s reuse of components and tools. In this talk, we propose a first fit based heuristic algorithm which creates the schedules for several vehicle variants at once, while transmitting a given signal at the same time in all the schedules. The scheduling algorithm also takes the time constraints as release dates and deadlines into account. Finally, different algorithm versions are compared on benchmark sets and low computational time demands are validated on large instances.
  • Barry Hurley (Insight Centre for Data Analytics)  - Numberjack: cutting exponential search trees into logs
    Date : 21 août 2014 à 15h30 - salle du conseil  
    Numberjack is a Python platform for combinatorial optimization. It offers a single interface to a number of efficient CP, MIP, SAT, and WCSP backends such as Mistral, Gurobi, CPLEX, SCIP, Toulbar2, and many SAT solvers. In this demo we will give a brief introduction to Numberjack by demoing a number of its powerful capabilities, in particular highlighting some more recent additions, and finally invite a discussion of other use cases and possible future directions.
  • Rob Fitzpatrick (NICTA)  - Order from Chaos: Capturing new profit and capex return from smart analytics
    Date : 24 avril 2014 à 15h30 - salle Vignemale  
    The increasing availability of massive amounts of data is driving profound changes across all areas of industry and holds the potential to transform supply chain operations. The major opportunity in this new era is 'analytics' - how all of this data is managed, aggregated and transformed into knowledge and actionable information. Rob will give examples of solutions to the data analytics challenge, which has presented one of the greatest challenges and opportunities for logistics officers in all spheres over the next decade.
  • Emmanuel Hébrard (LAAS-CNRS)  - The thousand faces of constraint propagation
    Date : 24 février 2014 à 14h00 - salle Hourgade  
    I will first introduce, and give a viewpoint on, constraint propagation. Then, I will show through examples the multiple forms that this key aspect of constraint progra! mming can take, from greedy approximations to exponential algorithms. A complex combinatorial problem can always be seen as the conjunction of more primitive relations or subproblems. These subproblems range from constant time solvable relations to NP-complete problems such as Hitting Set or Max Clique. In constraint programming, these subproblems are referred to as constraints, irrespective of their complexities. The existence of a solution for each individual constraint does not entail the existence of a solution of the composite problem. As a consequence, knowing how to solve efficiently each constraint is not sufficient. Constraint propagation is the mechanism that connects the different reasonings done on each constraint. Rather than solving a constraint, the key idea is to consider the dual task of its reduction by removal of inconsistent solutions. Such reductions remain correct globally and can therefore be propagated to other constraints. Typically, a propagation a! lgorithm achieves domain consistency, that is, remove all inco! nsistent values from domains, in polynomial time. However, this is not set in stone. Weaker or stronger properties can be targeted, and we do not necessarily have to be complete for a given property. Examples illustrating these possibilities will be drawn from constraints linked to matching, hitting set and sequencing.

2013

  • Gilbert Laporte (HEC Montréal)  - Minimizing Greenhouse Emissions in Vehicle Routing
    Date : 2 décembre 2013 à 11h00 - salle Hourgade  
    The Vehicle Routing Problem  holds a central place in distribution management. In the classical version of the problem the aim is to distribute goods to a set of geographically dispersed customers under a cost minimization objective and various side constraints. In recent years a number of researchers have started investigating the joint minimization of cost and greenhouse emissions in vehicle routing, giving rise to the so-called “Pollution-Routing Problem”.  Whereas cost depends primarily on distance travelled, emissions are a function of distance, vehicle load, speed and a variety of other factors. The aim of this talk is to describe recent research results in this context.
  • Sonia Cafieri (ENAC)  - Modèles d'optimisation mixte en nombres entiers pour des problèmes d'évitement des conflits d'aéronefs
    Date : 28 novembre 2013 à 14h00 - salle Bardeen  
    L'optimisation non-linéaire mixte en nombres entiers (MINLP) se pose naturellement dans la formulation de problèmes d'évi! tement des conflits d'aéronefs, où la nécessité de modéliser des choix logiques suggère la présence simultanée des variables discrètes ainsi que continues, et les contraintes non-linéaires résultent de la modélisation de la condition de séparation des aéronefs. Nous présentons et discutons des modèles MINLP, l'un basé sur des manœuvres de séparation par des changements de vitesse des aéronefs (en gardant les trajectoires inchangées) et un autre combinant des changements de cap et de vitesse. Les modèles sont suffisamment générales pour éviter d'imposer, comme on fait habituellement dans ce type de modèles, que les manœuvres de séparation soient réalisées simultanément par tous les aéronefs, les instants de temps pour effectuer des manœuvres étant des variables de décision du problème pour chaque aéronef. Nous discutons les avantages et les inconvénients de ces modèles.
  • Matias Urenda Moris (University of Skövde, Suède)  - Simulation-based Multi-objective Optimization for Lean production and logistic Networks (SimMOLN)
    Date : 24 octobre 2013 à 14h30 - salle Hourgade  

    Lean production has become a standard approach for improvement projects in many industrial companies and organizations. But despite all the benefits that Lean philosophy can offer, it lacks the scientific methods and models to support the evaluations of different improvement 

    alternatives. Many researchers have proposed that simulation is the perfect tool to complement Lean by addressing its deficiencies. Recently, meta-heuristic optimization has endowed simulation to be an even more powerful technique to identify and evaluate other possible improvements, which are impossible or too time-consuming to be found manually. Particularly, when there exist multiple conflicting objectives, simulation-based multiobjective optimization (SMO) is a promising approach to generate multiple trade-off solutions, so-called Pareto-optimal solutions, so that the decision maker is provided with the “best” alternatives to consider before making the final choice. On the other hand, Lean can provide a methodological framework to guide the managers to use SMO tools in the improvement projects. The primary aim of SimMOLN is therefore to develop a new continuous improvement methodology which is based on a synergy of simulation-based optimization ! (SBO), particularly SMO, and Lean management processes

  • Thomas Schiex (INRA Toulouse)  - Computational Protein Design as a Cost Function Network
    Date : 27 juin 2013 à 14h00 - salle Europe  

Les protéines sont des chaînes de molécules simples appelées acides aminés. Chaque acide aminé est caractérisé par une chaîne latérale spécifique, ayant la capacité de s'ori! enter selon différents degrés de libertés, définissant un continuum de conformations possibles. In fine, la forme tri-dimensionnelle d'une protéine et sa composition en acide aminés définissent sa fonction biochimique. La conception de protéines offrant des propriétés spécifiques est d'un intérêt majeur, avec des applications en médecine, en biotechnologie, en biologie synthétique et en nanotechnologies. 

L'approche traditionnelle du "Computational Protein Design" consiste, à partir d'un squelette de protéine fixé, à choisir, pour un ensemble de positions sélectionnées, un acide aminé et une conformation associée parmi un ensemble fini de conformations fréquentes appelées "rotamères". Afin que la protéine ainsi définie se replie préférentiellement sur le squelette initial, on cherche un ensemble de séquences et conformations qui ont une énergie la plus basse possible: (GMEC: Global Minimum-Energy Conformation). Ce problème d'optimisation combinatoire NP-difficile a été abordé en biologie structurale via une combinaison d'algorithmes appelés DEE/A* (Dead End Elimination/A*), disponible par exemple dans la plateforme OSPREY (Duke Lab). Il peut aussi se formuler naturellement sous la forme d'un réseau de fonctions de coûts (ou WCSP, Weighted Constraint Satisfaction Problem), comme un programme linéaire 0/1, comme un programme quadratique 0/1 ou comme un problème de! satisfiabilité pondéré (Weighted Partial MaxSAT).

Sur un ensemble d'instances réelles, nous observons que l'approche par réseau de fonctions de coûts, s'appuyant sur l'outil d'optimisation toulbar2, offre une efficacité très supérieure au DEE/A* implémenté dans OSPREY et reste très compétitif vis-à-vis des autres outils testés. Sur les instances étudiées, toulbar2 est également capable de rapidement produire des ensembles de solutions proches de l'optimum, information qui peut être intégrée dans la construction rationelle de librairies d'enzymes, une minimisation locale post-hoc permettant de prendre en compte un peu de la flexibilité des protéines.

  • Claude Guy-Quimper (Université Laval)  - Global Constraints for Scheduling with Equal Processing Times
    Date : 7 juin 2013 à 14h00 - salle Feynman  
    Constraint programming offers a large collection of constraints to model scheduling problems. Four constraints, in particular, can encode scheduling problems where tasks have equal processing times: All-Different, GCC, Inter-Distance, and Multi-Inter-Distance. I will survey the techniques used to filter these constraints by enforcing bounds consistency. I will conclude by presenting complexity results about combining these four constraints with precedence constraints. La programmation par contraintes offre un large éventail de contraintes pour modéliser des problèmes d'ordonnancement. Quatre contraintes en particulier peuvent encoder des problèmes où les tâches ont le même temps de traitement: All-Different, GCC, Inter-Distance, and Multi-Inter-Distance. Je présenterai les techniques utilisées pour filtrer ces contraintes afin de maintenir la cohérence de bornes. Je conclurai en présentant des résultats de complexité à propos de la combinaison entre ces quatre contraintes et des contraintes de précédence.
  • Maria Angélica Salazar Aguilar (Universidad Autónoma de Nuevo León, México)  - Vehicle routing problems with synchronization constraints
    Date : 18 janvier 2013 à 10h30 - salle Hourgade  
    In this talk, two problems arising from road maintenance operations will be described. A solution procedure based in the ALNS metaheuristic will be! presented as well as some computational results over a set of artificial instances and a real case from Dieppe City.
2012  
  • Mohamed Ali Aloulou (LAMSADE - Université Paris-Dauphine) - Coordination of production and delivery scheduling: two models
    Date : 7 novembre 2012 à 11h00 - salle Feynman  
    A supply chain is the set of all the stages at which value is added to a manufactured product. Its structure is more and more complex involving a large number of actors providing supply of raw materials and components, manufacturing of finished products, transportation, warehousing and logistics operations. It is well understood that, to enhance supply chain performance and to improve custom service level, there is a need to reduce inventory levels. In their literature review of integrated production and distribution models, (Sarmiento et al. 1999) point out that this trend leads to a closer link between different stages of the supply chain and highlights the need for better coordination in decision making. In this presentation, we focus on the coordination of scheduling and delivery operations. This problem has received a great deal of attention from a number of researchers. Most of the work considers various integrated production-distribution models at the strategic and tactical planning levels (Chen 2010). The need for considering operational aspects of supply chains, already pointed out by (Erenguc et al. 1999), is still topical (Chen 2010). Two models will be presented. In the first model, we consider the problem of jointly planning production scheduling and delivery operations of a set of suppliers producing time-sensitive products in a make-to-order context. Thus, products should be delivered immediately or shortly after the production to the customer location. We provide some solution's properties and algorithms when suppliers are considering delivery synchronization (Joint work with A. Ghaffari, S. Kedad-Sidhoum and A. Oulamara). In the second model, a manufacturer has to process a set of $n$ jobs, each job is first processed on machine $M_1$ then on machine $M_2$. The machines are located into two different cities, thus implying that, after processing on $M_1$, the jobs have to be shipped from $M_1$ location to $M_2$ location for further processing. A 3PL provider is in charge of the intermediate transportation. The 3PL proposes different shipping offers with associated total shipping price $P_1 > … >P_k$ and shipping time guarantee $T_1 < … 
  • Leo Liberti (Ecole Polytechnique) - Symmetry in Mathematical Programming
    Date : 2 octobre 2012 à 10h30 - salle Feynman 
    We present techniques for automatically detect symmetries in mathematical programming formulations, and discuss some approaches to exploit them in order to reduce the number of nodes in Branch-and-Bound type algorithms.
  • Shoshana Anily (Tel Aviv University) - Capacity sharing: capacity or labor division? A cooperative game approach
    Date : 7 septembre 2012 à 14h00 - salle Feynman 
    In this talk we discuss two types of capacity sharing approaches to model various service/production system! s as cooperative games with transferrable utility, and we analyze their core.  The literature on cooperative games usually assumes that total capacity is divisible and allocable additively. This premise is reasonable in some settings, but in others it may yield unacceptable solutions. We suggest another approach, which is aligned with the concept of division of labor, where total processing time, rather than total capacity over all resources, is allocated additively.
  • Cyril Briand (LAAS-CNRS, UPS) - Ordonnancement de projet multi-agent : recherche de stratégies efficaces et stables
    Date : 9 mai 2012 à 14h00 - salle Europe 
    Cet exposé s’intéresse à l'organisation de projets coopératifs, où un ensemble d’agents, c! hacun prenant en charge une partie des activités du projet, doivent s’entendre pour mener à bien l'exécution d'un projet pour le compte d'un client. Nous supposons que chaque agent est capable de contrôler la durée de ses activités, et donc d'influencer la durée totale du projet, ces durées étant spécifiées par des intervalles. En outre, lorsque les agents parviennent à finir le projet plus tôt que prévu, le client offre une récompense proportionnelle à la réduction de durée obtenue. Nous supposons que la récompense est partagée entre les agents selon une politique pré-définie par le client. Chaque agent est intéressé par la maximisation de son profit (correspondant à sa part de récompense de laquelle est déduit le coût lié à la réduction de la durée de ses activités). En lien avec l'optimisation multiobjectif et la théorie des jeux, nous nous intéressons aux stratégies de décision des agents et à la politique de partage choisie par le client. Nous montrons en particu! lier que déterminer une stratégie stable (équilibre de Nash) m! inimisan t la durée du projet est un problème difficile et nous proposons un programme mathématique à variables mixtes pour le résoudre. Nous montrons également comment déterminer une politique de partage qui soit la plus favorable pour le client. Plusieurs perspectives d'extension de ce travail seront également décrites.
  • Angel A. Juan (Open University of Catalonia) - Using Biased Randomization and Simulation to solve Stochastic Vehicle Routing Problems
    Date : 6 avril 2012 à 11h15 - salle Europe 

    This seminar discusses a hybrid approach combining randomized heuristics, Monte Carlo simulation (MCS), and parallel computing for solving the Vehicle Routing Problem with Stochastic Demands (VRPSD). Our approach deals with uncertainty in the customer demands by considering safety stocks, i.e. when designing the routes, part of the vehicle capacity is reserved to deal with potential emergency situations caused by unexpected demands. Thus, for a given VRPSD instance, different levels of safety stocks are considered and, for each of these levels, a different scenario is defined. Then, each scenario is solved by integrating MCS inside a heuristic-randomization process. This way, expected variable costs due to route failures can be naturally estimated even when customer demands follow a non-normal probability distribution. Use of parallelization strategies is then considered to run multiple instances of the algorithm in a concurrent way. The resulting concurrent solutions are then compared and the one with the minimum total costs is selected.

  • Alexandre Gondran (ENAC) - Coloration de graphes : méthodes de résolution et applications
    Date : 5 mars 2012 à 14h00 - salle Feynman 

    La coloration de graphe est un problème d'optimisation combinatoire difficile qui compte de très nombreuses applications : emplois du temps, allocation de! fréquence radio, ordonnancement, allocation de registres en informatique,... Je rappellerai dans une première partie le problème, ses variantes et ses applications. Je détaillerai également les principales stratégies et algorithmes utilisés pour le résoudre. Dans une seconde partie, je présenterai mes expériences de coloration dans le trafic aérien et en télécommunications. Je tacherai d'expliquer comment tenir compte des interférences multiples dans les réseaux mobiles c'est-à-dire de contraintes n-aires et in fine la notion de T-coloration d'hypergraphe.

  • Nicolas Jozefowiez (LAAS-CNRS, INSA) - Solution de problèmes multi-objectif : Principes et nouvelles méthodes
    Date : 16 Janvier 2012 à 10h30 - salle Bardeen 

    Dans une première partie de cette présentation, les concepts clefs de l'optimisation mult! iobjectif seront présentés. Des approches existantes types seront présentées dans cette partie. Les motivations pour l'étude de problèmes multiobjectif seront aussi discutées ainsi qu'une manière d'utiliser ces méthodes pour résoudre des problèmes complexes et de grandes tailles malgré la difficulté intrinsèque des problèmes multiobjectif. Dans la seconde partie, des méthodes originales et nouvelles seront décrites. Ces méthodes illustrent les points de recherche actuels dans l'optimisation multiobjectif telle que l'optimisation basée sur la recherche d'ensembles ou la définition de méthodes exactes. Plus précisément deux méthodes seront présentées : un algorithme génétique et un algorithme de séparations et coupes.

2011 
  • Gilles Simonin (LAAS-CNRS) - Impact de la contrainte d’incompatibilité sur la complexité et l’approximation des problèmes d’ordonnancement en présence de tâches-couplées
    Date : 13 décembre 2011 à 9h45 - salle Feynman 
    Depuis quelques années les véhicules sous-marins autonomes sont en plein essor, les torpilles sous-marines d'exploration en sont le parfait exemple. Les roboticiens du Lirmm travaille sur un modèle de torpille nommé TAIPAN. Cette torpille a pour objectif d'exécuter deux types de tâches : celles d'acquisition et celles de traitement. Les tâches d'acquisition sont semblables à des tâches-couplées, et les tâches de traitement sont des tâches classiques. La torpille utilise différents capteurs pour réaliser les acquisitions, certains capteurs ne peuvent pas être utilisés en même temps pour cause d'interférences. Nous introduisons donc un graphe de compatibilité permettant de représenter les tâches d'acquisition pouvant avoir leurs exécutions qui se chevauchent. La torpille possède un monoprocesseur embarqué permettant d'exécuter toutes la tâches. Nous nous ! intéresserons dans un premier temps à une modélisation du problème, puis dans un second temps je présenterai une étude de la complexité et de l'approximation des différents problèmes que nous pourrons rencontrer selon le type des tâches d'acquisition étudiées. Cette étude sera décomposée en trois parties, où nous prendrons en compte la présence de la contrainte d'incompatibilité et/ou celle des tâches de traitement.
  • Teodor Gabriel Crainic (CIRRELT et ESG-UQAM) - Planification des systèmes de logistique urbaine et l'incertitude de la demande
    Date : 5 décembre 2011 à 10h00 - salle de conférences 
    City Logistics, ou logistique urbaine, est à la fois un concept plutôt révolutionnaire dans la façon d’envisa! ger le transport de marchandise en ville, un ensemble de propositions, visions, projets, réalisations et rêves, ainsi que des possibilités et défis importants pour la recherche opérationnelle. C’est dans ce contexte que nous nous intéressons aux problèmes de planification des systèmes de logistique urbaine, notamment à la planification tactique des systèmes à deux échelons et au traitement de l’incertitude, particulièrement relativement à la demande de transport, dans ce contexte. Nous discuterons ces concepts, décrirons un cadre de modélisation du problème de planification tactique, pour ensuite présenter deux modèles, un déterministe et un deuxième de programmation stochastique à deux étapes prenant explicitement en compte l’incertitude sur le niveau réel de demande à satisfaire par un plan déterminé à priori sur la base de prévisions. Nous regarderons, en particulier, la question de la capacité additionnelle qu’il faudra, probablement, prévoir, ai! nsi que qu’un certain nombre de politiques de modificati! on du pl an, les « recours », suite à l’observation de la demande « réelle ».  Dans tous les cas, il s’agit non seulement de chercher la « meilleure solution » d’un point de vue conceptuel et mathématique, mais aussi de ne pas oublier les objectifs de société de la logistique urbaine – moins d’impacts négatifs sur la ville et ces citoyens –,  ainsi que les questions relatives à la gestion du système et de ses ressources. Ce séminaire a lieu dans le cadre de la journée du groupe de travail Transport et Logistique du GdR Recherche Opérationnelle du CNRS.
  • Přemysl Šůcha - A Multistage Approach for an Employee Timetabling Problem with a High Diversity of Shifts as a Solution for a Strongly Varying Workforce Demand
    Date : 20 Octobre 2011 a 15h00 - salle Feynman
    This work deals with the employee rostering problem at the airport. Such problems, related to the time varying demand of the transport services, use many (e.g. about a hundred) diverse shifts to cover the workforce demand during the day. Together, with the strict constraints, given by the collective agreement, the problem becomes difficult to solve. In our case, one stage algorithms, used to solve the usual employee rostering problems, produce an unusable roster in practice. This work suggests a three stage approach for the employee rostering problem where a set of different shifts is needed to satisfy the coverage requirements. The solution is based on the problem transformation to a simpler problem which is used to determine a rough position of the shifts in the roster. The maximal weighted matching in the bipartite graph is used as the inverse transformation of the problem and the final roster is obtained by the optimization based on a Tabu Searc! h algorithm.
  • Alessandro Agnetis -  
    Date : 19 Mai 2011 -14h00 - Salle Feynman

    In this talk we address a relatively novel class of scheduling problems, arising in various different contexts, in which jobs are characterized by a certain revenue (if successfully carried out) and a certain chance of success. If a job fails, the corresponding machine is blocked and no further job can be executed. The problem is to allocate and sequence the jobs on m parallel, identical machines in order to maximize expected revenue. For this problem, which is strongly NP-hard, we give some approximation results for the case m=2, and discuss the special case in which machines fail according to an exponentially distributed random process.

  • Alessandro Agnetis -  Multi-agent scheduling problems
    Date : 13 Mai 2011 -14h00 - Salle Feynman 

    Multi-agent scheduling refers to a class of multi-objective scheduling problems in which the objectives correspond to different decision makers (agents), each owning a subset of jobs. Each agent is only concerned with how his/her jobs are scheduled, so a compromise schedule must be sought, accounting for each agent's performance criterion. Multi-agent scheduling problems arise in several contexts, including transportation logistics, telecommunications and distributed computing systems. The multi-agent nature of these problems can be addressed by a wide range of methodological tools, including combinatorial optimization, game theory, bargaining models. In this talk we review the main approaches and results, pointing out open problems and venues for future research.

  • Sandra U. Ngueveu - Algorithmes efficaces basés sur la génération de colonnes: application aux tournées de véhicules m-péripatétiques
    Date : 8 avril 2011 -10h30 - Salle Europe
    La génération de colonnes est aujourd'hui largement répandue/utilisée pour la résolution de problèmes d'optimisation combinatoire. Cet exposé passera en revue les principes, avantages et inconvénients de cette approche avant de présenter l'adaptation et l'application au problème de tournées de véhicules m-péripatétiques (m-PVRP). Le m-PVRP modélise par exemple le transport de fonds régulier, les tournées de gardiennage, … où par sécurité, la séquence de visite des clients doit varier d'une période à l'autre. L'exposé illustrera l'intérêt des méthodes proposées, en particulier pour obtenir des bornes inférieures de bonne qualité (entre 1 et 3% de l'optimum) pour des temps de calculs raisonnables (quelques secondes).
  • Pierre Jean Meyer - Simulation de la gestion des bagages dans un aériport international
    Date : 29/03/2011 -16h00 - Salle Feynman
    Cet exposé présente les résultats d'un projet tutoré de l'ENSEEIHT, effectué en collaboration avec Florian Bonneau et Antoine Prost, en relation avec le sujet de thèse de Markus Frey (doctorant de l'Université de Munich). Une démonstration du simulateur réalisé avec le logiciel ARENA a été effectuée.
  • Julien Darlay -  Méthodes de la recherche opérationnelle pour l'analyse de données
    Date : 27/01/2011 - 11h30 - Salle de Direction
    L'analyse de données (ou datamining) a pour but d'extraire des informations originales à partir d'un grand volume de données. On peut trouver de nombreuses applications dans le domaine médical, dans l'ingénierie... Les problèmes d'analyse de données peuvent se ramener à des problèmes d'optimisation, la plupart du temps difficiles au sens de la complexité. Nous donnerons une illustration avec une modélisation en programmation linéaire d'un problème de catégorisation d'observations. Dans un deuxième temps, nous verrons une méthode particulière, l'analyse combinatoire de données. Cette méthode a la spécificité d'être développée par des chercheurs en recherche opérationnelle et repose sur des fondements théoriques forts (l'extension de fonctions booléennes partiellement définies). Elle se base sur des techniques classiques d'optimisation: algorithme glouton, programmation linéaire en nombres entiers, recherche exhaustive pour fournir des modèles performants et facilement interprétables.
2010
  • Nicolas Barnier -  Automatisation de la gestion du trafic aérien en Europe
    Date : 30/11/2010 - 14h00 - Salle Vignemale
    Malgré les récessions temporaires qui ont suivis les années 2001 et 2008, le trafic aÈrien connait une progression importante depuis  plusieurs décennies, ce qui mène fréquemment l'espace aérien à saturation et génère des retards de plus en plus importants. Contrairement à l'automatisation des systèmes embarqués dans les aéronefs, l'optimisation de la gestion du trafic aérien (Air Traffic Management - ATM) n'a connu que très peu d'Èvolutions depuis trenteans, si bien que la plupart des tâches du contrôle aérien et de l'ATM reposent toujours sur l'expertise d'opérateurs humains. Pourtant, l'automatisation de l'ATM fait l'objet de nombreux projets de recherche et une pression de plus en plus importante de la part des compagnies aériennes et de la Commission Européenne incite à l'amélioration de la capacité de l'espace aérien à l'Èchelle continentale. Le projet SESAR (Single European Sky ATM Research) a ainsi pour objectifs d'augmenter la capacité, améliorer la sécurité, diminuer l'impact environnemental des vols ainsi que le coût du contrôle. Mais l'ATM est un système complexe et de grande taille, sujet à de nombreuses sources d'incertitude et qui nécessite des transitions continues . Sur le plan théorique, la recherche en ATM est un domaine relativement récent, et nombreux sont les projets qui ont dû être abandonnés car ils sous-estimaient les difficultés techniques liées à l'un ou l'autre de ces paramètres. Ainsi, les systèmes automatisés qui permettent aujourd'hui d'améliorer opérationnellement l'ATM sont relativement anecdotiques et peu  optimisés. Deux voies principales se distinguent néanmoins pour tenter d'absorber la croissance du trafic en Europe dans la prochaine décennie : une approche centralisée fondée sur la gestion précise de trajectoires 4D et destinée aux espaces à forte densité, et une approche distribuée rendant les avions autonomes en utilisant des solveurs embarqués pour les zones de plus faible trafic. Pour répondre à ces attentes, les partenaires industriels de SESAR tentent de développer des systèmes de gestion de vol toujours plus précis, tandis que la recherche en ATM propose d'optimiser la structure du réseau de routes, la répartition du trafic, voire la gestion dynamique de trajectoires 4D, tout en conservant le rôle central de l'opérateur humain dans la décision
    finale.
     
  • Markus Frey -  Scheduling and planning the outbound baggage process at international airports
    Date : 29/09/2010 - 11h00 - Salle du conseil
    The planning of outbound baggage at international airports is a challenging task in the airport industry. The issue is to control the incoming baggage flow in order to balance the workload over the baggage handling system. The resource consumption of the the di fferent activities, which have to be scheduled, are depending on the arrival process of baggage. Because of high complexity we suggest a decomposition heuristic to tackle this problem.
  • Rainer Kolisch -  An efficient hybrid metaheuristic for integrated scheduling and
    staffing IT--projects based on a generalized minimum cost flow network
    Date : 03/06/2010 - 14h00 - Salle de Conférences
    Scheduling IT--projects and assigning the project work to human resources is an important and common task in almost any IT service company. It is particularly complex because human resources usually have multiple skills. Up to now only little work has considered IT-specific properties of the project structure and human resources.  In this paper we present an optimization model which simultaneously schedules the activities of multiple IT-projects with serial network structures and assigns the project work to multi-skilled internal and external human resources with static and heterogeneous efficiencies. The goal is to minimize costs. We solve the mixed--binary linear program with ILOG CPLEX and a hybrid metaheuristic which employs an efficient evaluation function exploiting the network structure of the staffing subproblem. The impacts of characteristic problem parameters on computation time and solution gaps are assessed in an experimental study. Our results show that by exploiting the network structure we can solve the staffing subproblem up to 7 times faster than CPLEX. Hence, the hybrid metaheuristic is superior to standard solvers especially for large problem instances.
  • Julien Moncel -  Problèmes d'ordonnancement avec usure ou apprentissage
    Date : 22/04/2010 - Salle Europe
    Jusque dans les années 90, la théorie classique de l'ordonnancement n'a considéré que des problèmes où les temps opératoires des tâches étaient considérés comme étant des paramètres statiques. Cependant, dans certaines situations, une telle modélisation est insuffisante car les temps opératoires des tâches dépendent essentiellement du moment où la tâche est réalisée. C'est par exemple le cas pour les incendies, qui peuvent s'étendre et donc prendre un temps plus important à maitriser si l'on tarde à les traiter.  Les problèmes d'ordonnancement avec usure ou apprentissage concernent donc des cas où les durées des tâches dépendent fortement du moment où ces tâches sont réalisées. On distingue de façon classique deux cas, celui de l'apprentissage (les tâches réalisées en fin d'ordonnancement sont réalisées plus rapidement qu'au début) et celui de l'usure (cas inverse : plus on attend, plus cela prend du temps).  Dans cet exposé on fera une brève revue de la littérature sur ce sujet, et on proposera quelques résultats théoriques sur l'existence d'algorithmes efficaces pour les problèmes à une machine.
  • Emmanuel Hébrard -  Contraintes molles d'égalité et de différence
    Date : 18/03/2010 - Salle de Conférences
    Les contraintes "AllDifferent" ou "Global Cardinality" sont
    essentielles dans de nombreux modeles de problemes combinatoires. Par
    exemple pour les problemes de "sport scheduling" ou de "car sequencing"
    ou elles permettent d'obtenir des resultats meilleurs que la PLNE.
    Nous avons etudie cette famille de contraintes qui permettent de
    favoriser la diversite ou la similarite entre variables. Apres avoir
    aborde les applications possibles de cette famille de contraintes, je
    montrerai les resultats algorithmiques que nous avons obtenu, en
    partculier sur la contrainte "SoftAllEqual".
  • Claire Hanen - Ordonnancements périodiques de graphes d'événements généralisés temporisés
    Date : 15/01/2010 - Salle Vignemale
    Les graphes d'évènements temporisés constituent un modèle intéressant et facilement analysable pour des problèmes d'ordonnancement cycliques sans conflits de ressource.
    Nous nous intéressons ici à l'extension de ce modèle construite en valuant les arcs du réseau de Petri sous-jacent. Ce modèle permet d'exprimer de manière concise des contraintes d'assemblage ou de limitation de buffers. Mais bien que les conflits de ressource en soient exclus, il apparait que l'analyse de faisabilité et de performance d'un tel modèle pose des problèmes difficiles qui pour beaucoup restent ouverts. Nous évoquerons quelques unes de ces difficultés, et monterons que les ordonnancements périodiques peuvent se calculer en temps polynomial, mais que, contrairement au modèle simple, ils ne sont pas dominants.
2009
  • Fawzi Bessaih - Validation de la charge utile d'un satellite de télécommunication
    Date : 26/11/2009 - Salle Moore
  • William Mangoua Sofack - Ordonnancement sous contraintes de consommation énergétique
    Date : 15/10/2009 - Salle de Conférences
  • Pauline Desseaux - Méthode de recherche arborescente pour un problème d'ordonnancement bi-objectif
    Date : 15/10/2009 - Salle de Conférences
  • Jean Charles Billaut - Doit-on croire le classement de Shangaï ? Une approche par l'analyse multicritères
    Date : 22/6/2009 - Salle Vignemale 
    Présentation
  • Philippe Laborie - Modéliser et résoudre les problèmes d'ordonnancement avec IBM ILOG CP Optimizer
    Date : 24/4/2009 - Salle Vignemale 
    Présentation
  • Christian Artigues - Présentation du challenge ROADEF
    Date : 3/4/2009 - Salle Moore 
    Présentation
  • Pierre Lopez - Recherche à divergences limitées pour des problèmes d'ordonnancement d'atelier flexibles
    Date : 3/4/2009 - Salle Moore 
    Présentation
  • David Allouche - Sélection de TagSNP par réseau de contraintes pondérées
    Date : 6/3/2009 - Salle Tourmalet 
    Présentation
2008
  • Murat Afsar - Partitionnement d'un graphe orienté acyclique par la génération de colonnes
    Date : 18/12/2008 - Salle Bardeen 
    Présentation
  • Alain Berro - Algorithmes évolutionnaires pour l'optimisation multiobjectif
    Date : 4/11/2008 - Salle Bardeen 
    Présentation
  • Roel Leus - Ordonnancement de projet avec échec des activités
    Date : 11/09/2008 - Salle Vignemale 
    Présentation
  • François Galasso - Aide à la décision pour la planification de chaînes logistiques dyadiques
    Date : 12/06/2008 - Salle Vignemale 
    Présentation
  • Nicolas Jozefowiez - A branch-and-bound algorithm for a traveling salesman problem with colors and two objectives
    Date : 12/06/2008 - Salle Vignemale 
    Présentation
  • Rémy Dupas - Routage de véhicules en dynamique
    Date : 20/05/2008 - Salle Feynman 
    Présentation
  • Julien François - Planification des chaines logistiques - Modélisation du système décisionnel et performance
    Date : 12/03/2008 - Salle Vignemale 
    Présentation
  • Laurent Houssin - Commande de systèmes (max,+)-linéaires
    Date : 10/01/2008 - Salle Vignemale
    Présentation
2007
  • Djamel Berkoune - Optimisation de l'ordonnancement en milieu prévisionnel incertain
    Date : 29/11/2007 - Salle Vignemale
    Présentation
  • Thierry Garaix - Optimisation et qualité de service pour le transport à la demande
    Date : 01/10/2007 - Salle Bardeen
    Présentation