Th. doct.--Informatique--Orléans, 1997. / Bibliogr. p. 133-140. Résumé. 1997 d'après la déclaration de dépôt légal.

Les diagrammes de décision Multi-valués (MDD) sont des structures de données efficaces et largement utilisées dans les domaines tels que la vérification, l’optimisation et la programmation dynamique. Dans cette thèse, nous commençons par améliorer les principaux algorithmes tels que la réduction de MDD, permettant aux MDD de potentiellement compresser exponentiellement des ensembles de tuples, ou la combinaison de MDD, tels que l’intersection ou l’union. Ensuite, nous proposons des versions parallèles de ces algorithmes ainsi que des versions permettant de travailler avec la version non déterministe des MDD. De plus, dans le domaine des MDD relâchés, un domaine de plus en plus étudié, nous définissons les notions de réduction et combinaison relâchés, ainsi que leurs algorithmes associés. Nous résolvons le problème de l’échantillonnage des solutions d’un MDD avec respect de loi de probabilité tels que des fonctions de probabilité de masse ou des chaines de Markov. Pour permettre d’utiliser les MDD dans les solveurs de programmation par contraintes, nous proposons de nouveaux propagateurs pour toutes les contraintes basées sur des MDD, améliorant les performances des algorithmes existants, puis nous en introduisons une nouvelle contrainte, la contrainte de channeling. Grâce à eux, nous montrons que nous pouvons reformuler plusieurs contraintes et en définir de nouvelles tout en étant basés sur des MDD. Finalement nous appliquons nos algorithmes à des problèmes industriels réels de génération de texte et musique, et de modélisation de réservoir de pétrole. / Multivalued Decision Diagrams (MDDs) are efficient data structures widely used in several fields like verification, optimization and dynamic programming. In this thesis, we first focus on improving the main algorithms such as the reduction, allowing MDDs to potentially exponentially compress set of tuples, or the combination of MDDs such as the intersection of the union. We go further by designing parallel algorithms, and algorithms handling non-deterministic MDDs. We then investigate relaxed MDDs, that are more and more used in optimization, and define the notions of relaxed reduction or operation and design efficient algorithms for them. The sampling of solutions stored in a MDD is solved with respect to probability mass functions or Markov chains. In order to combine MDDs with constraint Programming, we design the propagators of all the types of MMDD constraints in solvers, and introduce a new one, the channeling constraint. These new propagators outperform the existing ones and allow the reformulation of several other constraints such as the dispersion constraint, and even to define new ones easily. We finally apply our algorithm to several real world industrial problems such as text and music generation and geomodeling of a petroleum reservoir.

Ce mémoire traite de la résolution de problèmes d’ordonnancement à l’aide de la programmation par contraintes. Il s’intéresse principalement aux contraintes globales et particulièrement à la contrainte cumulative. Il passe en revue les règles permettant de la filtrer et les principaux algorithmes qui les appliquent. Il explique le Edge-Finder de Vilím et son arbre cumulatif. Il propose un algorithme plus performant et plus général pour appliquer les règles découlant du raisonnement énergétique. Le mémoire traite du cas particulier où toutes les tâches sont de durée identique. Pour modéliser efficacement ce type de problèmes, on y conçoit la contrainte multi-inter-distance. L’algorithme d’ordonnancement de López-Ortiz et Quimper est adapté pour réaliser un algorithme qui applique la cohérence de bornes. La contrainte multi-inter-distance s’avère efficace à résoudre le problème de séquençage des atterrissages d’avions du banc d’essai d’Artiouchine et Baptiste. / This thesis discusses how to solve scheduling problems using constraint programming. We study global constraints and particularly the Cumulative constraint. We survey its main filtering rules and their state-of-the-art filtering algorithms. We explain the Vilím’s Edge-Finder and its cumulative tree.We introduce a more efficient and more general algorithm that enforces the filtering rules from the energetic reasoning. We study the special case where all tasks have identical processing times. To efficiently model such problems, we introduce the Multi-Inter-Distance constraint. The scheduling algorithm by López-Ortiz and Quimper is adapted to produce a filtering algorithm enforcing bounds consistency. The constraint Multi-Inter-Distance is proved efficient to solve the runway scheduling problem on the benchmark by Artiouchine and Baptiste.

Les contraintes sont un moyen générique de représenter les règles qui gouvernent notre monde. Étant donné un ensemble de contraintes, une question centrale est de savoir s'il existe une possibilité de toutes les satisfaire simultanément. Cette problématique est au cœur de la programmation par contraintes, un paradigme puissant pour résoudre efficacement des problèmes qui apparaissent dans de nombreux domaines de l'activité humaine. Initialement dédiée, dans les années 1980, à la résolution de problèmes d'intelligence artificielle à variables entières, c'est dans les années 1990 que la programmation par contraintes a été employée à la résolution de problèmes à variables réelles. Cependant, les problèmes mixtes —utilisant à la fois variables entières et réelles— n'ont été que très peu considérés jusqu'ici par la programmation par contraintes. Dans cette thèse, nous nous plaçons du point de vue de la résolution de problèmes continus. Nous proposons et mettons en oeuvre différentes améliorations de ce cadre de résolution : • Intégration de la notion de recherche rigoureuse d'optimum au cadre classique de résolution sans objectif, afin de modéliser et résoudre un problème de conception en robotique ; • Collaboration de deux solveurs, l'un discret l'autre continu, plus efficace que chacun des outils pour résoudre les problèmes utilisant contraintes continues et contraintes discrètes ; • Comparaison des différentes modélisations et filtrages possibles de la contrainte globale discrète alldifferent, permettant de l'utiliser dans un solveur dédié au continu ; • Spécialisation des techniques de filtrage basées sur l'arithmétique des intervalles, augmentant la puissance de filtrage des contraintes arithmétiques discrètes et mixtes.

Nous proposons plusieurs techniques visant à résoudre en pratique le problème NP-complet de satisfaction de contraintes de manière générique. Nous distinguons deux grands axes de techniques de résolution de CSP : l'infrence et la recherche. Nous avons contribué l'amélioration des techniques d'inférence en nous concentrant sur la propriété centrale qu'est la consistance d'arc : optimisations des algorithmes de consistance d'arc, comportement de plusieurs algorithmes d'inférence aux bornes de domaines discrets, et enfin une alternative intéressante à la consistance de chemin : la consistance duale. Cette propriété nous a amené à concevoir des algorithmes de consistance de chemin forte très efficaces. La variante conservative de cette consistance est de plus plus forte que la consistance de chemin conservative, tout en restant plus rapide à établir en pratique.<br />Par ailleurs, nous avons également cherché à améliorer MGAC, tout d'abord en équipant celui-ci d'heuristiques de choix de valeurs. Nous nous sommes pour cela basés sur l'heuristique de Jeroslow-Wang, issue du problème SAT. En utilisant deux techniques de conversion de CSP vers SAT, nous montrons comment cette heuristique se comporterait sur un CSP. Enfin, nous avons cherché à utiliser une hybridation entre un algorithme de recherche locale basé sur la pondération des contraintes et un algorithme MGAC équipé de l'heuristique dom/wdeg, en exploitant les possibilités d'apprentissage de l'un et l'autre algorithmes.<br />De manière transversale, l'ensemble des techniques développées dans le cadre de cette thèse a amené à la réalisation d'une API pour le langage Java, capable de résoudre un CSP au sein d'une application Java quelconque. Cette API a été développée dans l'optique "boîte noire" : le moins de paramètres et d'expertise possibles sont demandés à l'utilisateur. Un prouveur basé sur CSP4J a concouru lors les compétitions internationales de prouveurs CSP avec des résultats encourageants.

La composition musicale utilise de plus en plus les outils informatiques, mais la question de l'interprétation des pièces soit résoule. Dans le cas des pièces électro-acoustiques sur support, enregistrement d'une organisation temporelle de sons, l'exécution des oeuvres se restreint à leur diffusion. A la différence des pièces instrumentales, un interprète ne peut modifier certains paramètres musicaux lors de l'exécution. Nous cherchons à définir un système de composition et d'exécution de pièces interprétables, en nous focalisant sur les modifications de dates d'événements de la partition. Nous proposons un formalisme de partitions interactives utilisant la programmation par contraintes pour définir l'organisation temporelle et les limites de l'interprétation. Nous présentons un modèle de machine abstraite pour l'exécution des partitions, basée sur les réseaux de Petri et la propagation de contraintes. Enfin, nous exposons quelques applications du système. / Abstract

La vérification de programmes avec des calculs sur les nombres à virgule flottante est une étape très importante dans le développement de logiciels critiques. Les calculs sur les nombres flottants sont généralement imprécis, et peuvent dans certains cas diverger par rapport au résultat attendu sur les nombres réels. L’objectif de cette thèse est de concevoir un solveur de contraintes sur les nombres à virgule flottante dédié à la vérification de programmes. Nous présentons dans ce manuscrit une nouvelle méthode de résolution de contraintes sur les flottants. Cette méthode se base principalement sur la sur-approximation des contraintes sur les flottants par des contraintes sur les réels. Cette sur-approximation doit être conservative des solutions sur les flottants. Les contraintes obtenues sont ensuite résolues par un solveur de contraintes sur les réels. Nous avons proposé un algorithme de filtrage des domaines sur les flottants basé sur le concept de la sur-approximation qui utilise des techniques de programmation linéaire. Nous avons aussi proposé une méthode de recherche de solutions basée sur des heuristiques. Cette méthode offre aussi la possibilité de comparer le comportement des programmes par rapport à une spécification sur les réels. Ces méthodes ont été implémentées et expérimentées sur un ensemble de programmes avec du calcul sur les nombres flottants. / The verification of programs with floating-point numbers computation is an important issue in the development of critical software systems. Computations over floating-point numbers are not accurate, and the results may be very different from the expected results over real numbers. The aim of this thesis is to design a constraint solver over floating-point numbers for program verification purposes. We introduce a new method for solving constraints over floating-point numbers. This method is based on an over-approximation of floating-point constraints using constraints over real numbers. This overapproximation is safe, that’s to say it doesn’t loose any solution over the floats. The generated constraints are then solved with a constraint solver over real numbers. We propose a new filtering algorithm using linear programming techniques, which takes advantage of these over-approximations of floating-point constraints. We introduce also new search methods and heuristics to find floating-point solutions of these constraints. Using our implementation, we show on a set of counter-examples the difference of the execution of programs over the floats with the specification over real numbers.

L’agriculture de précision est un mode de culture qui consiste à prendre en compte la variabilité intra-parcellaire afin d'appliquer le bon traitement au bon endroit. Depuis les années 80, l’agriculture de précision s’est développée grâce à l’arrivée d’outils de géolocalisation (GPS), de matériels permettant une gestion modulée des cultures et surtout d'une multitude de données issues de prélèvements sur le terrain, d'images et de capteurs. Dans ce contexte, l’agriculture de précision a fait émerger de nouveaux problèmes à la fois combinatoires et complexes afin de répondre à des enjeux de performance économique, technique et environnementale.Cette thèse porte sur l'utilisation de la programmation par contraintes pour résoudre des problèmes de tournées dans le contexte de l’agriculture de précision et, plus précisément, en viticulture de précision.Un problème de tournées de véhicule consiste à déterminer une flotte de véhicules afin de visiter une liste de clients ou de réaliser des tournées d’interventions. Le but est de minimiser le coût total des tournées tout en respectant différentes contraintes. Ce problème est une extension classique du problème du voyageur de commerce et fait partie des problèmes NP-difficiles.La programmation par contraintes est un outil très puissant capable de résoudre des problèmes combinatoires comme les problèmes de tournées. Elle fournit des algorithmes de filtrage dédiés à des contraintes de circuits qui permettent de résoudre de façon efficace des problèmes associant ces contraintes de circuit à d'autres contraintes plus spécifiques.La première contribution de cette thèse est la formalisation du problème de la vendange sélective et sa modélisation sous la forme d’un problème d’optimisation sous contraintes. Le problème de la vendange sélective consiste à trouver la trajectoire optimale d’une machine à vendanger qui récolte et sépare deux qualités de raisins. En plus d’être un problème de tournées peu commun, la gestion du remplissage simultané des deux bacs augmente la combinatoire du problème. Plusieurs modèles sont présentés et testés sur des données réelles provenant de vignobles situés dans le sud de la France.La deuxième contribution est l’établissement d’une nouvelle contrainte globale de tournées nommée WeightedSubCircuits. Elle permet d'aborder le problème plus général de tournées multiples dans lequel on cherche à couvrir une partie du graphe par un ensemble de circuits disjoints de coût minimal. Un algorithme de filtrage partiel de cette contrainte est également présenté. Des expérimentations ont été réalisées, notamment sur un problème de planning de techniciens intervenant sur des vignobles en Californie qui a été modélisé dans le cadre de cette thèse. Ces résultats préliminaires ont montré l'intérêt du filtrage apporté par cette nouvelle contrainte. / L’agriculture de précision est un mode de culture qui consiste à prendre en compte la variabilité intra-parcellaire afin d'appliquer le bon traitement au bon endroit. Depuis les années 80, l’agriculture de précision s’est développée grâce à l’arrivée d’outils de géolocalisation (GPS), de matériels permettant une gestion modulée des cultures et surtout d'une multitude de données issues de prélèvements sur le terrain, d'images et de capteurs. Dans ce contexte, l’agriculture de précision a fait émerger de nouveaux problèmes à la fois combinatoires et complexes afin de répondre à des enjeux de performance économique, technique et environnementale.Cette thèse porte sur l'utilisation de la programmation par contraintes pour résoudre des problèmes de tournées dans le contexte de l’agriculture de précision et, plus précisément, en viticulture de précision.Un problème de tournées de véhicule consiste à déterminer une flotte de véhicules afin de visiter une liste de clients ou de réaliser des tournées d’interventions. Le but est de minimiser le coût total des tournées tout en respectant différentes contraintes. Ce problème est une extension classique du problème du voyageur de commerce et fait partie des problèmes NP-difficiles.La programmation par contraintes est un outil très puissant capable de résoudre des problèmes combinatoires comme les problèmes de tournées. Elle fournit des algorithmes de filtrage dédiés à des contraintes de circuits qui permettent de résoudre de façon efficace des problèmes associant ces contraintes de circuit à d'autres contraintes plus spécifiques.La première contribution de cette thèse est la formalisation du problème de la vendange sélective et sa modélisation sous la forme d’un problème d’optimisation sous contraintes. Le problème de la vendange sélective consiste à trouver la trajectoire optimale d’une machine à vendanger qui récolte et sépare deux qualités de raisins. En plus d’être un problème de tournées peu commun, la gestion du remplissage simultané des deux bacs augmente la combinatoire du problème. Plusieurs modèles sont présentés et testés sur des données réelles provenant de vignobles situés dans le sud de la France.La deuxième contribution est l’établissement d’une nouvelle contrainte globale de tournées nommée WeightedSubCircuits. Elle permet d'aborder le problème plus général de tournées multiples dans lequel on cherche à couvrir une partie du graphe par un ensemble de circuits disjoints de coût minimal. Un algorithme de filtrage partiel de cette contrainte est également présenté. Des expérimentations ont été réalisées, notamment sur un problème de planning de techniciens intervenant sur des vignobles en Californie qui a été modélisé dans le cadre de cette thèse. Ces résultats préliminaires ont montré l'intérêt du filtrage apporté par cette nouvelle contrainte.

La programmation par contraintes est un cadre puissant utilisé pour modéliser et résoudre des problèmes combinatoires, employant des techniques d'intelligence artificielle, de la recherche opérationnelle, de théorie des graphes,..., etc. L'idée de base de la programmation par contraintes est que l'utilisateur exprime ses contraintes et qu'un solveur de contraintes cherche une ou plusieurs solutions.Les problèmes de satisfaction de contraintes (CSP), sont au cœur de la programmation par contraintes. Ce sont des problèmes de décision où nous recherchons des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Ces problèmes de décision revoient vrai, si le problème admet une solution, faux, sinon. Les problèmes de satisfaction de contraintes sont le sujet de recherche intense tant en recherche opérationnelle qu'en intelligence artificielle. Beaucoup de CSPs exigent la combinaison d'heuristiques et de méthode d'inférences combinatoires pour les résoudre dans un temps raisonnable.Avec l'amélioration des ordinateurs, la résolution de plus grands problèmes devient plus facile. Bien qu'il y ait plus de capacités offertes par la nouvelle génération de machines, les problèmes industriels deviennent de plus en plus grand ce qui implique un espace _norme pour les stocker et aussi plus de temps pour les résoudre.Cette thèse s'articule autour des techniques d'optimisation de la résolution des CSPs en raisonnant sur plusieurs axes.Dans la première partie, nous traitons la compression des contraintes table. Nous proposons deux méthodes différentes pour la compression des contraintes de table. Les deux approches sont basées sur la recherche des motifs fréquents pour éviter la redondance. Cependant, la façon de définir un motif, la détection des motifs fréquents et la nouvelle représentation compacte diffère significativement. Nous présentons pour chacune des approches un algorithme de filtrage.La seconde partie est consacrée à une autre façon d'optimiser la résolution de CSP qui est l'utilisation d'une architecture parallèle. Nous proposons une méthode où nous utilisons une architecture parallèle pour améliorer le processus de résolution en établissant des cohérences parallèles. En fait, les esclaves envoient à leur maître le résultat obtenu après avoir établi la cohérence partielle en tant que nouveaux faits. Le maître, à son tour essaye de profiter d'eux en enlevant les valeurs correspondantes. / Constraint Programming (CP) is a powerful paradigm used for modelling and solving combinatorial constraint problems that relies on a wide range of techniques coming from artificial intelligence, operational research, graph theory,..., etc. The basic idea of constraint programming is that the user expresses its constraints and a constraint solver seeks a solution. Constraint Satisfaction Problems (CSP), is a framework at the heart of CP problems. They correspond to decision problems where we seek for states or objects satisfying a number of constraints or criteria. These decision problems have two answers to the question they encode: true, if the problem admits a solution, false, otherwise. CSPs are the subject of intense research in both artificial intelligence and operations research. Many CSPs require the combination of heuristics and combinatorial optimization methods to solve them in a reasonable time.With the improvement of computers, larger and larger problems can be solved. However, the size of industrial problems grow faster which requires a vast amount of memory space to store them and entail great difficulties to solve them. In this thesis, our contributions can be divided into two main parts. In the first part, we deal with the most used kind of constraints, which are table constraints. We proposed two compressed forms of table constraints. Both of them are based on frequent patterns search in order to avoid redundancy. However, the manner of defining pattern, the patterns-detecting process and the new compact representation differ significantly. For each form, we propose a filtering algorithm. In the second part, we explore another way to optimize CSP solving which is the use of a parallel architecture. In fact, we enhance the solving process by establishing parallel consistencies. Different workers send to their master the result of establishing partial consistencies as new discovered facts. The master, in its turns tries to benefit from them by removing corresponding values.

Ce travail porte sur le test fonctionnel, basé sur les spécifications et complètement automatisé des logiciels synchrones. Nous proposons une extension des techniques de test proposées par l'outil Lutess afin de prendre en compte des logiciels qui comportent des entrées/sorties numériques. La génération de données de test est abordée en s'appuyant sur les techniques de programmation par contraintes.<br /><br />Nous avons redéfini les méthodes de guidage de la génération afin de les adapter à ce nouveau contexte numérique. Ainsi, nous proposons, en plus de la génération aléatoire respectant les propriétés invariantes de l'environnement, le guidage du test basé sur des probabilités conditionnelles ou sur des propriétés de sûreté. Des connaissances partielles sur le logiciel, que nous appelons hypothèses de test, peuvent être intégrées dans le processus de génération et contribuer à l'amélioration du pouvoir de détection de fautes du guidage par propriétés de sûreté. Enfin, nous permettons l'utilisation conjointe de plusieurs techniques de guidage dans une même spécification.<br /><br />Une implémentation de ces méthodes de test a été réalisée dans une nouvelle version de l'outil, que nous appelons Lutess V2. L'applicabilité de ces méthodes dans un contexte plus réaliste a été évaluée sur une étude de cas significative d'un contrôleur de niveau d'eau dans une chaudière.