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.

Cette thèse porte sur la résolution numérique de systèmes d'équations non-linéaires. Elle présente des contributions dans trois sous-domaines utilisant le calcul par intervalles : l'analyse par intervalles, les intervalles modaux et la programmation par contraintes. Le traitement des systèmes linéaires est au centre de plusieurs des travaux. Il sert notamment de base à la résolution dans le cas non-linéaire. En analyse par intervalles, nous proposons une extension de la méthode de Hansen-Bliek pour l'approximation extérieure optimale de l'ensemble des solutions d'un système linéaire dont les coefficients varient dans des intervalles. L'extension proposée prend en compte la possibilité de choisir le quanticateur (existentiel ou universel) associé à certains coefficients du système. Cette liberté permet de modéliser un plus large éventail de problèmes linéaires, notamment ceux obtenus itérativement à partir de l'opérateur de Newton (intervalle) généralisé. Une généralisation de la décomposition LU exploitant l'arithmétique de Kaucher est également proposée. Sur les intervalles modaux, nous proposons une construction originale de la théorie qui s'articule autour de la notion d'image quantiée, généralisation naturelle de la notion d'image d'une fonction. La construction proposée présente certains avantages, comme celui de pouvoir donner un sens plus concret à l'arithmétique de Kaucher. En programmation par contraintes, nous étudions de nouvelles cohérences partielles reposant sur la structure d'unions d'intervalles. Cette structure peut être utilisée pour représenter plus nement le domaine des variables dans des systèmes de contraintes numériques. Nous montrons notamment dans quelle mesure, et à quel coût, la propriété d'arc-cohérence peut ainsi être obtenue grâce à cette nouvelle représentation.

La version classique du problème d'ordonnancement de projet à contraintes de ressources (RCPSP) consiste à trouver un ordonnancement, de durée minimale, des activités d'un projet entrant en compétition sur l'usage de ressources renouvelables, cumulatives et disponibles en quantité limité. <br />La réputation d'extrême difficulté du RCPSP a mené nombre de chercheurs à proposer de nouvelles méthodes de résolution exacte toujours plus performantes pour ce problème. Malgré cela, les instances de tailles réelles, qui se recontrent fréquemment, par exemple dans la gestion de production industrielle, sont encore loins d'être résolues optimalement. Il est donc intéressant, en combinant les acquis des travaux précédents, en particulier en programmation par contraintes (PPC) et en programmation linéaire (PL), de se pencher sur des méthodes exactes innovantes ou encore de développer des procédures d'évaluation par défaut, pour permettre une meilleure estimation de la performance des heuristiques sur le RCPSP. Ce travail de thèse entre dans ce cadre.<br /><br />Dans un premier temps, nous nous attachons au calcul de bornes inférieures pour le RCPSP par relaxation lagrangienne. D'une part, nous cherchons à accélerer le calcul de la borne de Brucker et Knust (obtenue par hybridation de PPC et de génération de colonnes) en résolvant le programme linéaire sous-jacent par relaxation lagrangienne (méthodes de sous-gradient et de génération de contraintes). D'autre part, nous appliquons le même principe de relaxation lagrangienne, sur la formulation linéaire initiale de Mingozzi et al. dont est extraite la relaxation préemptive utilisée par Brucker et Knust. Une partie du problème se réduit alors, comme indiqué par Möhring et al., au calcul d'une coupe minimale dans un graphe.<br /> <br />Nous étudions ensuite, un second type de bornes inférieures, obtenu par des méthodes de coupes basées sur les relaxations continues de deux formulations linéaires entières. Ces programmes linéaires sont au préalable resserés par des techniques éprouvées de propagation de contraintes, dont la règle globale du shaving. L'originalité de notre méthode repose essentiellement dans la génération des coupes qui sont, en grande partie, directement déduites des règles de propagation de contraintes.<br /><br />Enfin, nous proposons une méthode originale de résolution exacte pour le RCPSP, basée sur la procédure de Resolution Search de Chvàtal, une alternative aux méthodes de Branch-and-Bound classiques et qui se rapproche du Dynamic Backtracking en programmation par contraintes. Dans Resolution Search, l'espace de recherche ne se présente pas comme un arbre, puisqu'il s'agit, à chaque fois qu'un noeud terminal est rencontré, de rechercher par backtrakings successifs, les fixations minimales qui font de ce noeud un noeud terminal. L'ensemble des ces fixations est alors stocké de manière intelligente de façon à les exclure de l'espace de recherche. Resolution Search a été initialement développée pour la résolution de programmes linéaires en variables binaires, mais n'a semble-t'il jamais été employée dans le cadre de problèmes spécifiques.<br />Dans le but de prouver son efficacité, nous commencons par l'appliquer basiquement à deux formulations linéaires en variables binaires pour le RCPSP et la comparons à une version tout aussi basique de Branch-and-bound.<br /> Nous en poursuivons l'étude en utilisant des règles de branchement et d'évaluation ayant déjà prouvé leur efficacité dans des implémentations classiques de méthodes arborescentes pour le RCPSP, telles que celles de Brucker et al., Carlier et Latapie, Demeulemeester et Herroelen.

Les problèmes d'ordonnancement constituent une classe importante des problèmes d'optimisation combinatoire. La plupart des travaux dans ce domaine considèrent des problèmes statiques pour lesquels toutes les données (activités, ressources, contraintes) sont connues à l'avance. En réalité, ce type de problèmes est très souvent soumis aux aléas (matières premières livrées en retard, arrivées de nouvelles commandes, pannes de machines, etc.). Aussi, l'ordonnancement se déroule rarement comme prévu. On a alors affaire à un problème d'ordonnancement dit dynamique. Dans cette thèse, nous considérons un problème d'ordonnancement très général, appelé RCPSP (Resource Constrained Project Scheduling Problem), et proposons un système permettant de résoudre le cas dynamique. Bien que beaucoup de travaux concernent le RCPSP statique, seules quelques méthodes sont proposées pour le cas dynamique. De plus ces méthodes ne sont pas satisfaisantes. La méthode que nous proposons applique au RCPSP une des techniques utilisées pour résoudre les problèmes de satisfaction de contraintes dynamiques : les explications. Une explication est un ensemble de contraintes (un sous-ensemble du système de contraintes courant) qui justifie le résultat de la recherche (déduction de nouvelles contraintes, contradiction aboutissant à un échec, etc.). Ces explications sont une trace explicite du comportement de la propagation. Elles permettent de défaire efficacement les effets passés d'une contrainte et ainsi d'ajouter et retirer dynamiquement des contraintes. Nous avons ainsi développé une recherche arborescente (inspirée d'une recherche arborescente de la littérature) qui en chaque noeud propage les contraintes temporelles et de ressources (en utilisant les techniques de core-times, task-interval et resource-histogram) tout en conservant des explications. Nous utilisons de plus une notion de distance (écart entre la fin d'une activité et le début d'une autre) permettant d'exprimer toutes les contraintes temporelles dans un cadre unique. Notre système est ainsi capable de résoudre de manière efficace (i.e. sans repartir à zéro et dans un temps raisonnable) des instances de RCPSP dynamiques (i.e. ajouts/retraits de contraintes de précédence, ajouts/retraits d'activités et de ressources). De plus, notre système étant très générique, il permet de traiter des extensions du RCPSP dynamique (précédences/disjonctions/chevauchements généralises, et variation des disponibilités des ressources).

Les structures d'hospitalisation rencontrent de nombreux problèmes de niveau opérationnel. Cette thèse propose une investigation des problématiques d'aide à la décision pour le pilotage des ressources humaines en HAD. Suite à l'étude des processus d'une structure HAD identifiant les différentes décisions logistiques dans le cadre d'une certification qualité, deux problématiques principales ont été identifiées. L'investigation du premier domaine, a permis de concevoir un outil d'aide à la décision calculant les emplois du temps des infirmiers d'une structure de soins à domicile. Il a été expérimenté pour l'HAD EOVI Drôme nord. Plusieurs modèles de décision ont été comparés à l'aide de deux méthodes de résolution : une résolution par programmation linéaire entière et une résolution par programmation par contraintes. Une deuxième problématique a été étudiée : le circuit du médicament d'une HAD, ceci en collaboration avec l'HAD Soins et Santé de Lyon afin de les aider dans la gestion de leurs livraisons urgentes à partir d'une pharmacie à usage intérieur. L'HAD rencontre en moyenne une quarantaine de livraisons urgentes par jour et ces livraisons coûtent très chers en raison des prestataires externes employés et des frais de taxi éventuels. Un outil d'aide à la décision décliné selon trois stratégies de livraisons différentes (par tranches horaires, par nombre de médicaments à livrer, par nombre de livraisons par tournées) a été développé et a été proposé à l'HAD. Une fois la stratégie choisie, cet outil a été utilisé en exploitant les données réelles de l'HAD pour comparer les coûts entre l'emploi de prestataires externes ou de livreurs salariés. Il a permis de démontrer que l'emploi de livreurs salariés serait nettement plus rentable.

Alors que la composition de musique électro-acoustique mobilise de plus en plus d'outils numériques, la question de l'interprétation de telles pièces reste ouverte. La plus part du temps, ces pièces sont un enregistrement sur support, d'une organisation temporel d'un matériau sonore. Pendant l'exécution, l'oeuvre est simplement diffusée et l'interprète peut uniquement modifier des paramètres globaux tels que le volume, la balance ou la spatialisation sur le système d'écoute. Il ne peut pas interpréter la pièce au sens où il pourrait le faire pour une partition classique. Nous souhaiterions que ce type d'interprétation soit possible pour les pièces électro-acoustiques. Cette possibilité ne peut être posible que dans le cadre de ``partitions interactives'' capables de s'adapter à leur environnement (contrôles de l'interprète, autres musiciens). Dans ce contexte, la partition est exécutée par la machine, ce qui conduit à s'intéresser à un problème différent de celui du suivi de partition. Nous cherchons à élaborer un système constitué de deux parties : un environnement de composition assistée par ordinateur permettant au compositeur de créer de telles partitions interactives, et une machine d'exécution rendant possible leur interprétation. L'environnement de composition doit disposer d'une représentation formelle de la musique ``interprétable''. Nous nous appuyons donc sur une formalisation de l'interprétation de la musique instrumentale, et cherchons alors à la généraliser à des pièces impliquant des processus génériques à la place des notes. Nous focalisons notre étude sur un certain aspet de l'interprétation : les variations agogiques, c'est à dire la possibilité pour l'interprète de modifier les date d'occurrence d'événements discrets de la pièces pendant l'exécution. Ces modifications de dates sont accessibles grace à des ``point d'interactions'' (débuts, fins, ou points intermédiaires) des processus, dont la position temporelle permet de contrôler la temporalité de la pièce. Mais ces possibilités sont encadrées par le compositeur à la création de la partition (comme dans le cas de musique instrumentale). Ces contraintes sont le résultats d'une démarche de composition, elles permettent également d'éviter une désorganisation totale de la pièce pendant l'exécution. Nous proposons une représentation formelle des partitions interactives, basées sur des blocs 2D, telle celle des Maquettes d'OpenMusic ou des Data Structures de Pure Data. Les partitions sont des ensembles d'objets organisés sur une ligne de temps ; ces objets sont eux-mêmes représentés comme des séquences de points de contrôle discrets (début, fin et points intermédiares). Ils représentent l'exécution de processus responsables du rendu sonore de la pièce (synthèse et traintement de signal ou de symboles ou même opérations algorithmiques complexes). Pour définir les limites imposées à l'interprétation, le compositeur peut poser des contraintes temporelles entre les points de contrôle de la pièce ; il peut ainsi imposer un ordre partiel entre les événements à l'aide de contraintes qualitatives, ou utiliser des contraintes quantitatives pour limiter les valeurs possibles des intervalles de temps séparant les points de contrôle. La partition est alors à la fois complètement spécifiée, mais sa temporalité reste flexible, laissant ainsi la place à l'interprétation. De plus, le compositeur peut définir certains points de contrôle comme ``interactifs'', les rendre ainsi dynamiquement déclenchables à l'arrivée d'événements extérieurs, supposés se produire pendant l'exécution de la pièce. Ces événements peuvent être produits par des interfaces de contrôle, ou par la détection de situations particulières dans le contexte musical. Lorsqu'une partition est interprétée, la machine d'exécution envoie un message aux processus lorsqu'un point de contrôle doit se produire. Ceci peut être le fait de l'écoulement du temps pour les points non dynamiques, ou de l'arrivée de événement extérieur correspondant pour les points dynamiques. Le système s'assure que les contraintes temporelles définies par le compositeur ne sont pas violées. Si l'arrivée d'un événement extérieur remet en cause la validité de contraintes, le système recalcule les dates de points de contrôle futurs pour assurer la validité des contraintes. L'ordre entre les points peut alors être modifié. Ces calculs sont effectués par un algorithme de propagation de contraintes. Le maintien des contraintes temporelles, peut amener le système à ignorer des événements extérieurs lorsque ceci risque de contredire des contraintes, tout comme il devra simuler l'arrivée d'un événement dans cas où l'absence de ce dernier conduirait à violer une contrainte. Nous proposons une struture de machine abstraite capable d'exécuter dynamiquemenr les partitions interactives. Celle-ci est basée sur les réseaux de Petri et la propagation de contraintes. Nous donnons un algorithme pour compiler les partitions depuis leur descritption formelle vers une représentation exécutable par la machine. Nous avons également développé un prototype dans OpenMusic, sous la forme d'une extension des Maquettes pour l'édition des partitions utilisant un système de propagation de contraintes. Elle contient également un compilateur de partition et une machine d'exécution envoyant des messages UDP vers des applications tierces. Les partitions sont sauvergardées grace à un format XML d'échange. Nous présentons plusieurs applications du système à la musique électro-acoustique la musique instrumentale et le théâtre.

La programmation par contraintes est une technologie pour l'optimisation qui associe des langages de modélisation riches avec des moteurs de résolution efficaces. Elle combine des techniques de plusieurs domaines tels que l'intelligence artificielle, la programmation mathématique et la théorie des graphes. Un défi majeur dans ce domaine concerne la définition de langages de haut-niveau pour faciliter la phase de modélisation des problèmes. Un autre aspect important est de concevoir des architectures robustes pour transformer des modèles de haut-niveau et obtenir des modèles exécutables efficaces, tout en visant plusieurs moteurs de résolution. Répondre à ces deux préoccupations est très difficile, car de nombreux aspects doivent être pris en compte, comme par exemple, l'expressivité et le niveau d'abstraction du langage ainsi que les techniques utilisées pour traduire le modèle de haut-niveau dans chacun des langages de résolution. Dans cette thèse, nous proposons une nouvelle perspective pour faire face à ces défis. Nous introduisons une nouvelle architecture pour la programmation par contraintes dans laquelle le problème est défini comme un ensemble d'objets contraints dans un nouveau langage de modélisation haut-niveau. La transformation des modèles est réalisée à l'aide de l'ingénierie des modèles. Les éléments des langages sont alors considérés comme des concepts définis dans un modèle de modèles appelé métamodèle. Cette nouvelle architecture permet d'aborder les phases de modélisation et de transformation de modèles en raisonnant à un niveau d'abstraction supérieur et, par conséquent, de réduire la complexité inhérente à ces deux phases.