ABSTRACT. There is much hype surrounding quantum computing and its potential applications for optimization. However, the technical details are often lost in translation. This talk provides an overview of quantum algorithms that could potentially be useful for continuous or discrete optimization. Most of the discussion will be devoted to the benefits and limitations of algorithms for SDP and LP via faster solution of linear systems, or with the multiplicative weights update method. We will also discuss some fundamental open questions, highlighting what algorithmic limitations need to be overcome for quantum computing to have an impact on the practice of optimization.

ABSTRACT. La planification de personnel est une activité fréquente dans tous les types d'organisation et peut représenter un défi. Nous présentons ici la première étape d'un projet de création de plannings pour le personnel non médical (infirmiers, aide-soignants, ...) du Centre Hospitalier Universitaire de Nantes (CHU). Nous nous interessons à la création de plannings cycliques dans lesquels les jours de remplacements sont positionnés de façon à faciliter la gestion des absences.

ABSTRACT. Cet exposé retrace les dix dernières années de développement de LocalSolver et présente la feuille de route pour la version 10 à venir. LocalSolver a été pensé dès son origine pour être l’outil principal du chercheur opérationnel. Notre ambition est de donner accès aux techniques de résolution de l’état de l’art en utilisant un langage de modélisation mathématique de haut niveau, accessible au plus grand nombre. Tout comme les solveurs de programmation linéaire en nombres entiers ont permis d’exploiter les techniques de séparation et évaluation via des modèles mathématiques, la première version de LocalSolver permettait de déléguer la résolution à une heuristique de recherche locale. Algorithmiquement très différente des précédentes, celle-ci permet d’obtenir – sans aucune ligne de code spécifique – des solutions de qualité en des temps très courts aux problèmes combinatoires de grande taille.

Le formalisme de modélisation et les techniques de résolution de LocalSolver ont été largement enrichis grâce aux retours d’expérience de nos utilisateurs et de nos projets de service. Le langage a été étendu pour modéliser plus facilement des problèmes comme les tournées de véhicules ou l’ordonnancement de tâches. L’heuristique de résolution a été renforcée pour obtenir les résultats de l’état de l’art sur ces nouveaux problèmes. Elle a été ensuite complétée par des techniques d’optimisation globale qui permettent de tirer parti des propriétés mathématiques du modèle (par exemple, sa linéarité ou sa convexité), en le reformulant automatiquement si besoin. LocalSolver est ainsi devenu un solveur global capable de calculer des bornes et de prouver l’optimalité dans nombre de cas.

Les prochaines versions de LocalSolver garderont comme objectif de toujours mieux traiter les problèmes de nos utilisateurs. Un effort particulier sera mis sur la résolution des problèmes en variables mixtes tels que la planification de production ainsi que les problèmes d’optimisation boite noire. La résolution des problèmes de routing et de packing sera aussi renforcée par des techniques de programmation mathématique relatives à la génération de coupes et de colonnes.

ABSTRACT. The problem of finding the k-shortest (simple) paths between a pair of nodes is a fundamental problem in graph theory, which is used in various kinds of applications in road networks, transportation networks, communication networks, etc.
Here, we study variants of this problem in which the reported paths must satisfy a pairwise threshold of dissimilarity. More precisely, we study the problem of finding k-shortest dissimilar paths (paths with similarity bounded by a threshold theta) with different variants and with different similarity measure.  We prove this problem to be NP-Complete for every similarity measure and we also prove the NP-Completeness of the problem even if a part of the solution is already given. Finally, we present several algorithms / methods that can solve the described problem in a reasonable time (using dynamic programming, enumeration methods and integer linear programming ILP).

ABSTRACT. In this work, we explore a new way of breeding individuals in a population-based metaheuristic, by exploiting the ability of autoencoders to interpolate representation of candidate solutions in a learned latent space. In the remaining of this document, we present in more details our idea and show its application to the traveling salesman problem.

ABSTRACT. Nous étudions dans ce travail le problème de l'élicitation incrémentale des préférences d'un décideur susceptible de présenter certaines contradictions dans ses réponses à des questions préférentielles du fait d'éventuelles réponses éronnées. Étant donné un ensemble d'alternatives multicritères (ensemble de choix) et une fonction d'agrégation dont la valeur des paramètres est inconnue, nous proposons une nouvelle méthode d'élicitation incrémentale dans laquelle l'espace des paramètres est partitionné en polyèdres d'optimalité de la même manière que dans les méthodes SMAA (Stochastic Multiobjective Acceptability Analysis). L'incertitude concernant les réponses du décideur est modélisée par une distribution de probabilité sur les polyèdres de la partition. À chaque étape de la procédure d'élicitation, la distribution est révisée de manière Bayésienne à l'aide de questions de comparaisons par paires. Le choix des questions est basé sur sur la minimisation des regrets espérés (voir définition plus bas). Nous alternons l’analyse de l’ensemble des alternatives avec l’élicitation des paramètres de la fonction d’agrégation: somme pondérée ou moyenne pondérée ordonnée.

ABSTRACT. Nous nous intéressons au problème du dimensionnement d'une flotte de robots capables d'exécuter des opérations de transport dans un entrepôt logistique. Les opérations d'un robot sont découpées en plusieurs phases : chargement, déplacement chargé, déchargement et déplacement à vide. L'objectif est de déterminer le nombre minimal de robots nécessaires pour transporter un ensemble de charges de même type d'un point A à un point B sur un horizon de temps déterminé. Pour un même nombre de robots, plusieurs ordonnancements peuvent exister. Nous nous intéressons en particulier à celui qui équilibre le plus les charges entre les robots afin, d’une part, d’équilibrer l’utilisation de robots et d’autre part, de minimiser la date de fin de la dernière tâche de transport.  Si l'on considère une infinité de stations de chargement, nous obtenons une formule analytique simple pour le nombre optimal de robots. Avec une seule station de chargement, nous proposons un algorithme simple qui permet de calculer le nombre optimal de robots.

ABSTRACT. We consider the problem of scheduling independent jobs with a common due date on a single machine with the objective of maximizing the number of early jobs. The processing times are uncertain and take any value from a certain job dependent interval. For measuring the quality of an algorithm for that problem with imprecise data we use the concept of minimizing the maximum regret. We present complexity results and some dominance properties.