Reproduction de : Thèse de doctorat : Informatique : Orléans : 1995. / Résumé en français. Bibliogr. p. 264-270.

La programmation par contraintes est une approche régulièrement utilisée pour résoudre des problèmes combinatoires d'origines diverses. Dans cette thèse nous nous focalisons sur les problèmes d'ordonnancement cumulatif. Un problème d'ordonnancement consiste à déterminer les dates de débuts et de fins d'un ensemble de tâches, tout en respectant certaines contraintes de capacité et de précédence. Les contraintes de capacité concernent aussi bien des contraintes cumulatives classiques où l'on restreint la somme des hauteurs des tâches intersectant un instant donné, que des contraintes cumulatives colorées où l'on restreint le nombre maximum de couleurs distinctes prises par les tâches. Un des objectifs récemment identifiés pour la programmation par contraintes est de traiter des problèmes de grandes tailles, habituellement résolus à l'aide d'algorithmes dédiés et de métaheuristiques. Par exemple, l'utilisation croissante de centres de données virtualisés laisse apparaitre des problèmes d'ordonnancement et de placement multi-dimensionnels de plusieurs milliers de tâches. Pour atteindre cet objectif, nous utilisons l'idée de balayage synchronisé considérant simultanément une conjonction de contraintes cumulative et des précédences, ce qui nous permet d'accélérer la convergence au point fixe. De plus, de ces algorithmes de filtrage nous dérivons des procédures gloutonnes qui peuvent être appelées à chaque nœud de l'arbre de recherche pour tenter de trouver plus rapidement une solution au problème. Cette approche permet de traiter des problèmes impliquant plus d'un million de tâches et 64 ressources cumulatives. Ces algorithmes ont été implémentés dans les solveurs de contraintes Choco et SICStus, et évalués sur divers problèmes déplacement et d'ordonnancement.Mots-clés : Programmation par contraintes, ordonnancement, cumulatif, passage à l'échelle, point fixe, contraintes de ressources multidimensionelles, balayage synchronisé.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Les travaux présentés dans cette thèse portent sur la conception simultanée du produit et de sa chaîne logistique, dans le cas où la demande présente une diversité élevée. Situés entre conception de produit et dimensionnement de chaîne logistique, ces travaux se placent fondamentalement dans le domaine de l'Ingénierie Intégrée ou du Concurrent Engineering. Avec la diversité croissante des produits, cette démarche est rendue nécessaire pour pouvoir concevoir le plus rapidement possible une famille de produits et leur chaîne logistique dans le but de minimiser le coût total de fonctionnement de la chaîne logistique. La première partie de la thèse porte sur l'aide à la conception de produits. Elle présente une démarche multi-phases de préconception et de personnalisation des produits à forte diversité et des outils d'assistance à cette démarche de conception exploitant des modèles génériques à base de connaissances de type propagation et satisfaction des contraintes (modèles CSP). Le résultat de cette démarche est un ensemble de solutions de conception. La seconde partie de la thèse porte sur la conception de réseaux logistiques. Elle présente une approche permettant de sélectionner les solutions produits et de dimensionner la chaîne logistique en s'appuyant sur un modèle de recherche opérationnelle de type programmation linéaire mixte en nombres entiers et dont l'objectif est de minimiser le coût de fonctionnement global de la chaîne logistique. L'application industrielle visée, concernant la conception de systèmes de câblage pour l'industrie automobile est présentée, permettant d'illustrer la démarche proposée.

La fouille de données et la Programmation Par Contraintes (PPC) sont deux domaines de l'informatique qui ont eu, jusqu'à très récemment, des destins séparés. Cette thèse est l'une des toutes premières à s'intéresser aux liens entre la fouille de données et la PPC, et notamment aux apports de cette dernière à l'extraction de motifs sous contraintes. Différentes méthodes génériques pour la découverte de motifs locaux ont été proposées. Mais, ces méthodes ne prennent pas en considération le fait que l'intérêt d'un motif dépend souvent d'autres motifs. Un tel motif est appelé motif n-aire. Très peu de travaux concernant l'extraction de motifs n-aires ont été menés et les méthodes développées sont toutes ad hoc. Cette thèse propose un cadre unifié pour modéliser et résoudre les contraintes n-aires en fouille de données. Tout d'abord, l'extraction de motifs n-aires est modélisée sous forme de problème de satisfaction de contraintes (CSP). Puis, un langage de requêtes à base de contraintes de haut niveau est proposé. Ce langage permet d'exprimer une large panoplie de contraintes n-aires. Plusieurs méthodes de résolution sont développées et comparées. Les apports principaux de ce cadre sont sa déclarativité et sa généricité. Il s'agit du premier cadre générique et flexible permettant la modélisation et la résolution de contraintes n-aires en fouille de données.

L'élaboration de plannings de travail de personnel représente un problème majeur auquel sont confrontées la plupart des organisations. Nous nous préoccupons ici de l'automatisation de cette tâche, liant négociation et calcul combinatoire. Les modèles préférentiels sur lesquels se base l'évaluation des plannings sont complètement révisés. Une nouvelle représentation combinatoire des préférences est proposée, couplant le concept de relation binaire de préférence à celui de contrainte souple. Elle est mieux adaptée à la formulation des opinions de chaque acteur et intègre la notion d'aide à la décision et d'interactivité en admettant l'incomparabilité et l'intransitivité. Ensuite, l'agrégation des préférences individuelles est réalisée par la méthode axiomatique en usant de plusieurs principes éthiques : l'équité (Pigou-Dalton, Suppes-Sen) et l'efficacité (Pareto). Divers algorithmes de filtrage et de recherche de solution adaptés à la forme particulière des préférences et critères sont conçus. Un système interactif d'élaboration de plannings infirmiers est décrit.

Aujourd’hui, la localisation de robots sous-marins demeure une tâche complexe. L’utilisation de capteurs habituels est impossible sous la surface, tels que ceux reposant sur les systèmes de géolocalisation par satellites. Les approches inertielles sont quant à elles limitées par leur forte dérive dans le temps. De plus, les fonds marins sont généralement homogènes et non structurés, rendant difficile l’utilisation de méthodes SLAM connues, qui couplent la localisation et la cartographie de manière simultanée. Il devient donc nécessaire d’explorer de nouvelles alternatives. Notre approche consiste à traiter un problème de SLAM de manière purement temporelle. L’originalité de ce travail est de représenter le temps comme une variable classique qu’il faut estimer. Cette stratégie soulève de nouvelles opportunités dans le domaine de l’estimation d’état, permettant de traiter de nombreux problèmes sous un autre angle. Toutefois, une telle résolution temporelle demande un ensemble d’outils théoriques qu’il convient de développer. Cette thèse n’est donc pas seulement une contribution dans le monde de la robotique mobile, elle propose également une nouvelle démarche dans les domaines de la propagation de contraintes et des méthodes ensemblistes. Cette étude apporte de nouveaux outils de programmation par contracteurs qui permettent le développement de solveurs pour des systèmes dynamiques. Les composants étudiés sont mis en application tout au long de ce document autours de problèmes robotiques concrets. / The localization of underwater robots remains a challenging issue. Usual sensors, such as Global NavigationSatellite System (GNSS) receivers, cannot be used under the surface and other inertial systems suffer from a strong integration drift. On top of that, the seabed is generally uniform and unstructured, making it difficult to apply usual Simultaneous Localization and Mapping (SLAM) methods to perform a localization.Hence, innovative approaches have to be explored. The presented method can be characterized as a raw-data SLAM approach, but we propose a temporal resolution – which differs from usual methods – by considering time as a standard variable to be estimated. This concept raises new opportunities for state estimation, under-exploited so far. However, such temporal resolution is not straightforward and requires a set of theoretical tools in order to achieve the main purpose of localization.This thesis is thus not only a contribution in the field of mobile robotics, it also offers new perspectives in the areas of constraint programming and set-membership approaches. We provide a reliable contractor programming framework in order to build solvers for dynamical systems. This set of tools is illustrated throughout this document with realistic robotic applications.

Ce mémoire présente une approche basée sur des méthodes garanties pour résoudre des problèmes d’optimisation de systèmes dynamiques multi-physiques. Ces systèmes trouvent des applications directes dans des domaines variés tels que la conception en ingéniérie, la modélisation de réactions chimiques, la simulation de systèmes biologiques ou la prédiction de la performance sportive.La résolution de ces problèmes d’optimisation s’effectue en deux phases. La première consiste à mettre le problème en équations sous forme d’un modèle mathématique constitué d’un ensemble de variables, d’un ensemble de contraintes algébriques et fonctionelles ainsi que de fonctions de coût. Celles-ci sont utilisées lors de la seconde phase qui consiste à d’extraire du modèle les solutions optimales selon plusieurs critères (volume, poids, etc).Les contraintes algébriques permettent de manipuler des grandeurs statiques (quantité, taille, densité, etc). Elles sont non linéaires, non convexes et parfois discontinues.Les contraintes fonctionnelles permettent de manipuler des grandeurs dynamiques. Ces contraintes peuvent être relativement simples comme la monotonie ou la périodicité, mais aussi bien plus complexe par la prise en compte de contraintes différentielles simples ou définies par morceaux. Les équations différentielles sont utilisées pour modéliser des comportements physico-chimiques (magnétiques, thermiques, etc) et d’autres caractéristiques qui varient lors de l’évolution du système.Il existe plusieurs niveaux d’approximation pour chacune de ces deux phases. Ces approximations donnent des résultats pertinents, mais elles ne permettent pas de garantir l’optimalité ni la réalisabilité des solutions.Après avoir présenté un ensemble de méthodes garanties permettant de résoudre de manière garantie des équations différentielles ordinaires, nous formalisons un modèle particulier de systèmes hybrides sous la forme d’équations différentielles ordinaires par morceaux. A l’aide de plusieurs preuves et théorèmes nous étendons la première méthode de résolution pour résoudre de manière garantie ces équations différentielles par morceaux. Dans un second temps, nous intégrons ces deux méthodes au sein d’un module de programmation par contracteurs, que nous avons implémenté. Ce module basé sur des méthodes garantie permet de résoudre des problèmes de satisfaction de contraintes algébriques et fonctionnelles. Ce module est finalement utilisé dans un algorithme d’optimisation globale déterministe modulaire permettant de résoudre les problèmes considérés. / In this thesis a set of tools based on guaranteed methods are presented in order to solve multi-physics dynamic problems. These systems can be applied in various domains such that engineering design process, model of chemical reactions, simulation of biological systems or even to predict athletic performances.The resolution of these optimization problems is made of two stages. The first one consists in defining a mathematical model by setting up the equations for the problem. The model is made of a set of variables, a set of algebraic and functional constraints and cost functions. The latter are used in the second stage in order to extract the optimal solutions from the model depending on several criteria (volume, weight, etc).Algebraic constraints are used to describe the static properties of the system (quantity, size, density, etc). They are non-linear, non-convex and sometimes discontinuous. Functional constraints are used to manipulate dynamic quantities. These constraints can be quite simple such as monotony or periodicity or they can be more complex such as simple or piecewise differential constraints. Differential equations are used to describe physico-chemical properties (magnetic, thermal, etc) and other features evolving with the component use. Several levels of approximation exist for each of these two stages. These approximations give some relevant results but they do not guarantee the feasibility nor the optimality of the solutions.After presenting a set of guaranteed methods in order to perform the guaranteed integration of ordinary differential equations, a peculiar type of hybrid system that can be modeled with piecewise ordinary differential equation is considered. A new method that computes guaranteed integration of these piecewise ordinary differential equations is developed through an extension of the initial algorithm based on several proofs and theorems. In a second step these algorithms are gathered within a contractor programming module that have been implemented. It is used to solve algebraic and functional constraint satisfaction problems with guaranteed methods. Finally, the considered optimization problems are solved with a modular deterministic global optimization algorithm that uses the previous modules.

Cette thèse a pour objectif d'étudier l'utilisation de la programmation par contraintes pour développer un solveur de planification de production. Nous nous concentrons sur des problèmes de dimensionnement de lots de production (lot-sizing) qui sont des problèmes majeurs et difficiles de la planification de la production et profitons d'une des principales forces de la programmation par contraintes, à savoir les contraintes globales. Nous définissons une contrainte globale LotSizing qui s'appuie sur un problème générique de lot-sizing mono-produit à un seul niveau, qui tient compte des capacités de production et de stockage, des coûts unitaires de production et de stockage et des coûts fixes. Cette contrainte globale est un outil de modélisation intuitif pour les problèmes complexes de lot-sizing car elle permet de modéliser chaque nœud des réseaux de distribution. Nous utilisons des techniques de programmation dynamique classiques du lot-sizing pour développer des algorithmes de filtrage pour la contrainte globale. Nous modélisons également des problèmes multi-produits.Enfin, nous introduisons un nouvel algorithme de filtrage générique s'appuyant sur la programmation linéaire. Nous montrons que la cohérence d'arc pour les contraintes considérées peut être obtenue avec la résolution d'un seul programme linéaire lorsque la contrainte a une formulation idéale et nous généralisons le résultat pour faire du filtrage partiel lorsqu'aucune restriction n'est faite sur ces contraintes. Cette technique peut être pertinente lors de la résolution de sous-problèmes de flot ou de séquence sous-jacents au lot-sizing. / In this thesis we investigate the potential use of constraint programming to develop a production planning solver. We focus on lot-sizing problems that are crucial and challenging problems of the tactical level of production planning and use one of the main strengths of constraint programming, namely global constraints. The goal of this work is to set the grounds of a constraint programming framework for solving complex lot-sizing problems. We define a LotSizing global constraint based on a generic single-item, single-level lot-sizing problem that considers production and inventory capacities, unitary production and inventory costs and setup costs. This global constraint is an intuitive modeling tool for complex lot-sizing problems as it can model the nodes of lot-sizing networks. We use classical dynamic programming techniques of the lot-sizing field to develop powerful filtering algorithms for the global constraint. Furthermore we model multi-item problems that are natural extensions of the core problem.Finally we introduce a new generic filtering algorithm based on linear programming. We show that arc consistency can be achieved with only one call to a linear programming solver when the global constraint has an ideal formulation and adapt the result to provide partial filtering when no restriction is made on the constraints. This technique can be useful to tackle polynomial lot-sizing underlying flow and sequence sub-problems.

Le trafic aérien en Europe représente environ 30 000 vols quotidiens actuellement. Selon les prévisions de l’organisme Eurocontrol, ce trafic devrait croître de 70% d’ici l’année 2020 pour atteindre 50 000 vols quotidiens. L’espace aérien, découpé en zones géographiques appelées secteurs de contrôle, atteindra bientôt son niveau de saturation vis-à-vis des méthodes actuelles de planification et de contrôle. Afin d’augmenter la quantité de trafic que peut absorber le système, il est nécessaire de diminuer la charge de travail des contrôleurs aériens en les aidant dans leur tâche de séparation des avions. En se fondant sur les demandes de plans de vol des compagnies aériennes, nous proposons une méthode de planification des trajectoires en 4D permettant de présenter au contrôleur un trafic dont la plupart des conflits auront été évités en avance. Cette planification s’établit en deux étapes successives, ayant chacune un unique degré de liberté : une allocation de niveaux de vol permettant la résolution des conflits en croisière puis une allocation d’heures de décollage permettant de résoudre les conflits restants. Nous présentons des modèles pour ces deux problèmes d’optimisation fortement combinatoires, que nous résolvons en utilisant la programmation par contraintes ou les algorithmes évolutionnaires, ainsi que des techniques permettant de prendre en compte des incertitudes sur les heures de décollage ou le suivi de trajectoire. Les simulations conduites sur l’espace aérien français mènent à des situations où tous les conflits sont évités, avec des retards alloués de l’ordre d’une minute en moyenne (80 à 90 minutes pour le vol le plus retardé) et un écart par rapport à l’altitude optimale limité à un niveau de vol pour la quasi totalité des vols. La prise en compte d’incertitudes de manière statique dégrade fortement ces solutions peu robustes, mais nous proposons un modèle dynamique utilisant une fenêtre glissante susceptible de prendre en compte des incertitudes de quelques minutes avec un impact réduit sur le coût de l’allocation. / Air traffic in Europe represents about 30,000 flights each day and forecasts from Eurocontrol predict a growth of 70% by 2020 (50,000 flights per day). The airspace, made up of numerous control sectors, will soon be saturated given the current planification and control methods. In order to make the system able to cope with the predicted traffic growth, the air traffic controllers workload has to be reduced by automated systems that help them handle the aircraft separation task. Based on the traffic demand by airlines, this study proposes a new planning method for 4D trajectories that provides conflict-free traffic to the controller. This planning method consists of two successive steps, each handling a unique flight parameter : a flight level allocation phase followed by a ground holding scheme.We present constraint programming models and an evolutionary algorithm to solve these large scale combinatorial optimization problems, as well as techniques for improving the robustness of the model by handling uncertainties of takeoff times and trajectory prediction. Simulations carried out over the French airspace successfully solved all conflicts, with a mean of one minute allocated delay (80 to 90 minutes for the most delayed flight) and a discrepancy from optimal altitude of one flight level for most of the flights. Handling uncertainties with a static method leads to a dramatic increase in the cost of the previous non-robust solutions. However, we propose a dynamic model to deal with this matter, based on a sliding time horizon, which is likely to be able to cope with a few minutes of uncertainty with reasonable impact on the cost of the solutions.