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.

Les problèmes combinatoires basés sur le partitionnement de graphe permettent de modéliser un grand nombre d'applications pratiques. On retiendra des exemples aussi variés que la reconstruction de " super-arbres " en phylogénie, la planification de missions, ou la construction de tournées de véhicules en logistique. Ces applications, bien que provenant de domaines différents, peuvent toutes se voir comme un problème de partitionnement de graphe par des patrons tels que des cycles, des chemins, ou des arbres. Cependant, les problèmes pratiques se résument rarement à des problèmes " pur " comme peuvent l'être le problème de chemin Hamiltonien ou le problème des K-chemins disjoints. En effet, ils combinent bien souvent le problème de partitionnement avec un ensemble de restrictions sur la topologie des sommets et des arcs. La diversité des contraintes opérationnelles misent en jeu constitue souvent une limite à leur résolution par des approches considérant de manière séparée le problème de partitionnement et les restrictions supplémentaires imposées. Cette thèse se concentre sur les problèmes de satisfaction de contraintes li !es au partitionnement de graphe par des arbres mettant en jeu un certain nombre de restrictions sur la topologie des partitions autorisées. Notre travail se focalise d'une part sur la compréhension des propriétés structurelles inhérentes aux contraintes de partitionnement par des arbres, et d'autre part sur l'étude des interactions existantes entre le problème de partitionnement et les restrictions classiques (telles que les relations de précédences ou d'incomparabilités entre les sommets du graphe à partitionner). Nous nous attachons plus particulièrement à montrer comment prendre en compte de manière globale un certain nombre de ces restrictions au sein d'une contrainte de partitionnement de graphes par des arbres. Un autre aspect essentiel porte sur la mise en œuvre d'une telle contrainte : nous montrons en quoi une gestion dynamique des structures de données permet de s'abstraire significativement d'un problème récurrent à la plupart des contraintes globales liées aux graphes : la sensibilité des algorithmes de graphes à la densité des graphes manipulés par la contrainte.

La programmation par contraintes est une approche intéressante pour traiter des problèmes d'ordonnancement. En ordonnancement cumulatif, les activités sont définies par leur date de début, leur durée et la quantité de ressource nécessaire à leur exécution. La ressource totale disponible (la capacité) en chaque instant est fixe. La contrainte globale Cumulative modélise ce problème en programmation par contraintes. Dans de nombreux cas pratiques, la date limite de fin d'un projet est fixée et ne peut être retardée. Dans ce cas, il n'est pas toujours possible de trouver un ordonnancement des activités qui n'engendre aucun dépassement de la capacité en ressource. On peut alors tolérer de relâcher la contrainte de capacité, dans une limite raisonnable, pour obtenir une solution. Nous proposons une nouvelle contrainte globale : la contrainte SoftCumulative qui étend la contrainte Cumulative pour prendre en compte ces dépassements de capacité. Nous illustrons son pouvoir de modélisation sur plusieurs problèmes pratiques, et présentons différents algorithmes de filtrage. Nous adaptons notamment les algorithmes de balayage et d'Edge-Finding à la contrainte SoftCumulative. Nous montrons également que certains problèmes pratiques nécessitent d'imposer des violations de capacité pour satisfaire des règles métiers, modélisées par des contraintes additionnelles. Nous présentons une procédure de filtrage originale pour traiter ces dépassements imposés. Nous complétons notre étude par une approche par décomposition. Enfin, nous testons et validons nos différentes techniques de résolution par une série d'expériences.

La programmation par contraintes est une approche intéressante pour traiter des problèmes d’ordonnancement. En ordonnancement cumulatif, les activités sont définies par leur date de début, leur durée et la quantité de ressource nécessaire à leur exécution. La ressource totale disponible (la capacité) en chaque instant est fixe. La contrainte globale Cumulative modélise ce problème en programmation par contraintes. Dans de nombreux cas pratiques, la date limite de fin d’un projet est fixée et ne peut être retardée. Dans ce cas, il n’est pas toujours possible de trouver un ordonnancement des activités qui n’engendre aucun dépassement de la capacité en ressource. On peut alors tolérer de relâcher la contrainte de capacité, dans une limite raisonnable, pour obtenir une solution. Nous proposons une nouvelle contrainte globale : la contrainte SoftCumulative qui étend la contrainte Cumulative pour prendre en compte ces dépassements de capacité. Nous illustrons son pouvoir de modélisation sur plusieurs problèmes pratiques, et présentons différents algorithmes de filtrage. Nous adaptons notamment les algorithmes de balayage et d’Edge-Finding à la contrainte SoftCumulative. Nous montrons également que certains problèmes pratiques nécessitent d’imposer des violations de capacité pour satisfaire des règles métiers, modélisées par des contraintes additionnelles. Nous présentons une procédure de filtrage originale pour traiter ces dépassements imposés. Nous complétons notre étude par une approche par décomposition. Enfin, nous testons et validons nos différentes techniques de résolution par une série d’expériences. / Constraint programming is an interesting approach to solve scheduling problems. In cumulative scheduling, activities are defined by their starting date, their duration and the amount of resource necessary for their execution. The total available resource at each point in time (the capacity) is fixed. In constraint programming, the Cumulative global constraint models this problem. In several practical cases, the deadline of theproject is fixed and can not be delayed. In this case, it is not always possible to find a schedule that does not lead to an overload of the resource capacity. It can be tolerated to relax the capacity constraint, in a reasonable limit, to obtain a solution. We propose a new global constraint : the SoftCumulative constraint that extends the Cumulative constraint to handle these overloads. We illustrate its modeling power on several practical problems, and we present various filtering algorithms. In particular, we adapt the sweep and Edge-Finding algorithms to the SoftCumulative constraint. We also show that some practical problems require to impose overloads to satisfy business rules, modelled by additional constraints. We present an original filtering procedure to deal with these imposed overloads. We complete our study by an approach by decomposition. At last, we test and validate our different resolution techniques through a series of experiments.

La programmation par contraintes rencontre depuis le milieu des ann´es 90 un certain succès dans la résolution d'applications combinatoires complexes. Son extension aux contraintes d'intervalles est une approche prometteuse pour traiter des contraintes non-linéaires. La résolution de systèmes hybrides discrets-continus est pour autant restée essentiellement inexplorée. Cette thèse exploite un modèle hybride pour s'attaquer a une application en permettant d'éviter la discrétisation du problème. Les deux problèmes traités sont les suivants : 1. Contraintes globales continues : la définition de contraintes globales a permis d'améliorer substantiellement l'expressivité et l'efficacité des solveurs de contraintes discrets. Nous spécifions ici une première contrainte globale dans un solveur continu. Elle maintient des contraintes de distance euclidienne entre n points par un algorithme géométrique. 2. Résolution d'une application hybride discrète-continue : l'aide au déploiement d'antennes radio est un métissage du problèmes d'allocation de fréquences radio et d'un problème d'analyse de localisation. Nous utilisons notre contrainte globale de distance euclidienne pour obtenir une résolution hybride discrète-continue efficace de ce problème.

Les systèmes de contraintes de distance euclidienne apparaissent dans de nombreux domaines d'applications, comme en robotique, en biochimie<br />moléculaire ou en CAO. Les techniques issues de la programmation par contraintes permettent de résoudre ces problèmes en combinant une technique de bissection avec des méthodes de réduction des domaines (consistances locales ou partielles). Or, ces consistances sont des méthodes systématiques qui ne prennent pas en compte les propriétés spécifiques des contraintes.<br /><br />Nous présentons dans cette thèse deux approches pour la conception d'une contrainte globale pour la résolution de systèmes de contraintes de distance. La première approche est basée sur l'inférence de contraintes<br />redondantes directement issues de propriétés géométriques du système.<br />La deuxième approche est basée sur l'introduction d'un algorithme de filtrage global dédié aux systèmes d'équations de distance.<br />Ces travaux ont débouché sur la conception d'une<br />technique de décomposition de domaines qui exploite la structure particulière des contraintes de distance. Enfin, nous présentons une généralisation de cette heuristique de recherche à des contraintes numériques quelconques.

Dans cette thèse, nous avons considéré des problèmes de minimisation de fonctionnelles relatives à des objets géométriques en dimension 2 et 3 sous contraintes de bord. Nous considérons d'abord le cas des corps de largeur constante en dimension 2 et nous redémontrons le théorème de Blaschke-Lebesgue par la théorie du contrôle optimal en utilisant le principe de Pontryagin. Nous étudions aussi le problème de la minimisation du volume dans la classe des corps de largeur constante en dimension 3 et à symétrie de révolution. Par le principe de Pontryagin, nous obtenons des conditions nécessaires sur un minimiseur. Nous étudions également le problème de minimisation de l'aire dans la classe des rotors d'un polygone à n côtés, ce qui constitue une généralisation du problème précédent. Par le principe de Pontryagin, nous démontrons qu'un minimiseur est une réunion finie d'arcs de cercles de rayon r_i où les r_i prennent des valeurs quantifiées. Nous étudions plus spécifiquement certaines propriétés des rotors réguliers en s'intéressant à leur optimalité locale pour la fonctionnelle d'aire, et pour un certain type de déformations admissibles. Par le théorème de Kuhn-Tucker, nous généralisons au cas des rotors un résultat de Firey en montrant que les rotors réguliers du triangle équilatéral sont des maxima locaux de l'aire, et que les rotors réguliers des polygones réguliers à n>4 côtés, sont des points selles de l'aire. Enfin, nous étudions le problème de minimisation du volume en dimension 3 dans la classe des corps de largeur constante. Nous introduisons d'abord un espace fonctionnel prenant en compte la contrainte de convexité et celle de largeur. Puis nous en déduisons des conditions d'optimalité faibles, vérifiées par le solide de Meissner, dont on conjecture depuis 1934 qu'il minimise le volume dans cette classe.

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.

Dans le cadre de la Programmation par Contraintes, les contraintes globales ont amené une évolution majeure tant du point de vue modélisation (en synthétisant des ensembles de contraintes) que du point de vue résolution (grâce à des techniques de filtrage héritées d'autres domaines, comme la Recherche Opérationnelle ou l'Intelligence Artificielle). Par ailleurs, beaucoup de problèmes réels sont sur-contraints (ils ne possèdent pas de solution). Dans ce cas, il est nécessaire de relaxer certaines contraintes. De nombreuses études ont été menées pour traiter le cas des contraintes unaires et binaires, mais très peu pour le cas des contraintes globales. Dans cette thèse, nous étudions la relaxation des contraintes globales dans un cadre permettant l'expression de préférences. Pour plusieurs contraintes globales parmi les plus utilisées (c'est-à-dire AllDifferent, Gcc et Regular), nous proposons différentes sémantiques de violation ainsi que des algorithmes permettant de tester l'existence d'une solution et d'éliminer les valeurs incohérentes (filtrage). Les résultats de cette thèse ont été appliqués avec succès à des problèmes de création d'emplois du temps pour des infirmières, qui sont des problèmes sur-contraints difficiles à modéliser et surtout à résoudre. Mots-clefs : programmation par contraintes, contrainte globale, problème sur-contraints, relaxation de contraintes, contrainte globale relaxée, problème de création d'emplois du temps pour des infirmières.

De toutes les composantes de l'écriture musicale, l'orchestration - ou l'art d'assembler les timbres instrumentaux - est longtemps demeurée, dans son enseignement comme dans sa pratique, une activité empirique. La difficulté de formaliser de manière rigoureuse l'ensemble des techniques inhérentes à cette discipline fait qu'aujourd'hui encore, l'orchestration reste un domaine peu abordé par l'informatique musicale et l'aide à la composition.<br /><br />Les rares outils actuels ramènent le problème de l'orchestration à la découverte, au sein de banques d'échantillons sonores instrumentaux, de combinaisons approchant au mieux un timbre fixé par le compositeur. Cette approche sera également la nôtre. Mais là où les méthodes actuelles contournent systématiquement le problème combinatoire de l'orchestration par le recours à des principes de décomposition ou à des algorithmes de matching pursuit, l'originalité de notre démarche est de placer les enjeux combinatoires au coeur de nos travaux et de traiter l'orchestration à la mesure de sa complexité.<br /><br />Envisageant tout d'abord la question comme un problème de sac à dos multi-objectifs, nous montrons que les non-linéarités dans les modèles de perception du timbre imposent un cadre théorique plus large pour l'aide à l'orchestration. Nous proposons une formalisation générique et extensible en nous plaçant dans un cadre de recherche combinatoire multicritère sous contraintes, dans lequel plusieurs dimensions perceptives sont optimisées conjointement pour approcher un timbre cible défini par le compositeur.<br />Nous validons dans un premier temps notre approche théorique en montrant, sur un ensemble de problèmes de petite taille et pour une caractérisation exclusivement spectrale du timbre, que les solutions du problème formel correspondent à des propositions d'orchestration pertinentes. Nous présentons alors un algorithme évolutionnaire permettant de découvrir en un temps raisonnable un ensemble de solutions optimales. S'appuyant sur la prédiction des propriétés acoustiques des alliages instrumentaux, cette méthode propose des solutions d'orchestration en fonction de critères perceptifs et encourage ainsi la découverte de mélanges de timbres auxquels le savoir et l'expérience n'auraient pas nécessairement conduit.<br />En outre, la recherche peut-être à tout moment orientée dans une direction privilégiée. Parallèlement, nous définissons un cadre formel pour l'expression de contraintes globales et introduisons une métaheuristique innovante de résolution, permettant de guider la recherche vers des orchestrations satisfaisant un ensemble de propriétés symboliques en lien direct avec l'écriture musicale.<br /><br />Nous présentons enfin un prototype expérimental d'outil d'aide à l'orchestration utilisable directement par les compositeurs, dans lequel l'exploration des possibilités de timbres est facilitée à travers une représentation multi-points de vue des solutions et un mécanisme interactif des préférences d'écoute. Nous terminons avec une série d'exemples d'application de nos travaux à des problèmes compositionnels concrets.