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.

Dès lors qu'une structure est organisée, la capacité de placer les bonnes personnes au bon moment devient cruciale pour satisfaire les besoins d'un service, d'une école ou d'une entreprise. On définit les problèmes de planification de personnel comme le procédé consistant à construire de manière optimisée les emplois du temps de travail du personnel. La motivation de cette thèse est de proposer un moyen d'exprimer ces problèmes de manière simple et automatique, sans avoir à intervenir ensuite dans le processus de résolution. Pour cela, nous proposons de rassembler le pouvoir de modélisation des automates avec la capacité de la programmation par contraintes à résoudre efficacement des problèmes complexes. Le caractère expressif des automates est ainsi utilisé pour modéliser des règles de séquencement complexes. Puis, afin d'intégrer ces automates multi-pondérés dans un modèle de programmation par contraintes, nous introduisons un nouvel algorithme de filtrage basé sur la relaxation lagrangienne : multicost-regular. Nous présentons également une version souple de cette contrainte permettant de pénaliser les violations d'une règle modélisée par un tel automate : soft-multicost-regular. Le modèle contraintes basé sur ces contraintes est automatiquement construit. Il est résolu à l'aide de la librairie de contraintes CHOCO et à été testé sur des instances réalistes issues des librairies ASAP et NRP10. La recherche de solution est améliorée par l'utilisation d'heuristiques spécifiques basées sur les regrets et s'appuyant sur la structure des contraintes multicost-regular et soft-multicost-regular.

Nous présentons une méthode d'aide à la décision pour la définition d'un système éolien qui prend en compte les composants du système, les spécificités du vent et du réseau de distribution proche du site. La démarche globale utilisée permet, par l'utilisation des outils de l'analyse fonctionnelle et par l'analyse des flux fonctionnels, de mettre en place des modèles utiles pour l'aide à la décision en définition préliminaire d'un système éolien. L'ensemble complet de solutions est déterminé par un moteur d'inférence CSP (Constraint Satisfaction Problem) qui recherche la satisfaction de toutes les contraintes. La capacité intrinsèque d'un modèle à produire une aide à la décision en conception préliminaire est estimée au travers des quatre caractéristiques suivantes : la parcimonie, l'exactitude, la précision et la spécialisation du modèle. Le modèle global intègre des connaissances issues du fabricant, du distributeur et de l'investisseur pour calculer les critères qui permettent de discriminer les alternatives de conception. Une alternative est définie par un site (vent et réseau) et une architecture du système éolien (7 variables de conception). Les critères, nécessaires à la prise de décision, calculés sont : le coût du kWh produit, la quantité de l'énergie produite, le coût total actualisé du projet. Concernant la connexion au réseau, nous avons pris en compte les variations lentes de la tension et le phénomène de Flickers. Nous avons cherché, en premier lieu, à déterminer le taux maximal de pénétration de la production éolienne dans un réseau de distribution donné. En deuxième lieu, nous avons examiné deux alternatives de solution pour l'amélioration de l'intégration des systèmes éoliens dans les réseaux de distribution, c'est-à-dire l'intégration d'un système du contrôle de la puissance réactive et l'intégration d'un système de stockage inertiel. La solution du stockage inertiel malgré un avantage lié au service système semble être plus coûteuse que le contrôle de la puissance réactive pour cette application. Nous avons montré l'intérêt de l'intégration des spécificités du site d'implantation dans le processus de prise de décision au travers d'une application sur trois sites différents (un site méditerranéen, et deux du nord de l'Europe). Les gains obtenus sur le coût du kWh sont importants pour les sites méditerranéens et la plupart des variables de conception influencent fortement ce coût. L'étude a également montré la possibilité d'adapter les choix technologiques au contexte du réseau dans le site. Le taux de pénétration peut être augmenté considérablement pour les sites dont le rapport X/R est grand en utilisant des systèmes à vitesse variable.

Les processeurs à jeu d'instructions spécifiques (ASIP) constituent un compromis entre les performances d'un circuit matériel dédié et la flexibilité d'un processeur programmable. Ces processeurs spécialisés peuvent être composés d'un processeur généraliste dont le jeu d'instructions est étendu par des instructions spécifiques à une ou plusieurs applications et qui sont exécutées sur une extension matérielle. On parle alors de processeurs extensibles. Si le coût de conception et de vérification de telles architectures est considérablement réduit en comparaison à une conception complète, la complexité est en partie reportée sur l'étape de compilation. En effet, le jeu d'instructions d'un processeur extensible est à la fois une entrée et une sortie du processus de compilation. Cette thèse propose plusieurs contributions pour guider le processus de conception de telles architectures à travers des techniques d'optimisations adaptées aux processeurs extensibles. La première de ces contributions consiste à sélectionner et à ordonnancer les instructions spécialisées VLIW en résolvant un unique problème d'optimisation de programmation par contraintes (CP). D'autre part, nous proposons une technique originale qui traite de l'interaction entre l'optimisation de code et l'extension de jeu d'instructions. Le principe est de transformer automatiquement le code original des nids de boucles d'un programme (à l'aide du modèle polyédrique) afin de sélectionner des instructions spécialisées vectorisables et dont les données temporaires, produites lors d'une itération de boucle, sont mémorisées sur l'extension matérielle du processeur.

La matérialisation de vues est une technique très utilisée dans les systèmes de gestion de bases de données ainsi que dans les entrepôts de données pour améliorer les performances des requêtes. Elle permet de réduire de manière considérable le temps de réponse des requêtes en pré-calculant des requêtes coûteuses et en stockant leurs résultats. De ce fait, l'exécution de certaines requêtes nécessite seulement un accès aux vues matérialisées au lieu des données sources. En contrepartie, la matérialisation entraîne un surcoût de maintenance des vues. En effet, les vues matérialisées doivent être mises à jour lorsque les données sources changent a fin de conserver la cohérence et l'intégrité des données. De plus, chaque vue matérialisée nécessite également un espace de stockage supplémentaire qui doit être pris en compte au moment de la sélection. Le problème de choisir quelles sont les vues à matérialiser de manière à réduire les coûts de traitement des requêtes étant donné certaines contraintes tel que l'espace de stockage et le coût de maintenance, est connu dans la littérature sous le nom du problème de la sélection de vues. Trouver la solution optimale satisfaisant toutes les contraintes est un problème NP-complet. Dans un contexte distribué constitué d'un ensemble de nœuds ayant des contraintes de ressources différentes (CPU, IO, capacité de l'espace de stockage, bande passante réseau, etc.), le problème de la sélection de vues est celui de choisir un ensemble de vues à matérialiser ainsi que les nœuds du réseau sur lesquels celles-ci doivent être matérialisées de manière à optimiser les coût de maintenance et de traitement des requêtes. Notre étude traite le problème de la sélection de vues dans un environnement centralisé ainsi que dans un contexte distribué. Notre objectif est de fournir une approche efficace dans ces contextes. Ainsi, nous proposons une solution basée sur la programmation par contraintes, connue pour être efficace dans la résolution des problèmes NP-complets et une méthode puissante pour la modélisation et la résolution des problèmes d'optimisation combinatoire. L'originalité de notre approche est qu'elle permet une séparation claire entre la formulation et la résolution du problème. A cet effet , le problème de la sélection de vues est modélisé comme un problème de satisfaction de contraintes de manière simple et déclarative. Puis, sa résolution est effectuée automatiquement par le solveur de contraintes. De plus, notre approche est flexible et extensible, en ce sens que nous pouvons facilement modéliser et gérer de nouvelles contraintes et mettre au point des heuristiques pour un objectif d'optimisation. Les principales contributions de cette thèse sont les suivantes. Tout d'abord, nous dé finissons un cadre qui permet d'avoir une meilleure compréhension des problèmes que nous abordons dans cette thèse. Nous analysons également l'état de l'art des méthodes de sélection des vues à matérialiser en en identifiant leurs points forts ainsi que leurs limites. Ensuite, nous proposons une solution utilisant la programmation par contraintes pour résoudre le problème de la sélection de vues dans un contexte centralisé. Nos résultats expérimentaux montrent notre approche fournit de bonnes performances. Elle permet en effet d'avoir le meilleur compromis entre le temps de calcul nécessaire pour la sélection des vues à matérialiser et le gain de temps de traitement des requêtes à réaliser en matérialisant ces vues. Enfin, nous étendons notre approche pour résoudre le problème de la sélection de vues à matérialiser lorsque celui-ci est étudié sous contraintes de ressources multiples dans un contexte distribué. A l'aide d'une évaluation de performances extensive, nous montrons que notre approche fournit des résultats de qualité et fi ables.

En adoptant un point de vue utilitariste du consommateur sur certains produits orientés service, nous avons d'abord contribué à la proposition d'un modèle de contextes d'usage que se doit de couvrir au mieux un produit. Le modèle conduit à une meilleure intégration des analyses de marketing et d'ingénierie de la conception amenant à une optimisation d'un produit paramétré plus orientée vers les besoins du marché ou à un meilleur étagement d'une famille de produits. Nous proposons une série d'indices qui révèlent l'adéquation entre les usages couverts par un produit de dimensions données ou une famille de produits donnée avec un espace d'usages cible qu'il s'agit de couvrir dans sa totalité ou en partie mais d'une manière suffisamment dominante par rapport à la concurrence. En premier lieu, l'indice de couverture d'usage (UCI) pour un produit unique est introduit par la cartographie du produit relativement à un ensemble d'utilisateurs représentatifs définis par des usages attendus. Sur cette base, l'UCI pour une famille de produits est construite pour évaluer la composition de la famille et la redondance des produits qui la composent. Les avantages par rapport à la traditionnelle estimation de la demande en marketing sont de réduire la complexité de l'enquête et de l'analyse des données et de pouvoir estimer le niveau de compétitivité d'une offre innovante sans nécessiter de retour d'expérience du marché. Nous expérimentons nos propositions sur un problème de reconception d'une famille de scies sauteuses. L'approche proposée permet d'évaluer l'adaptabilité, pour une famille de produits de tailles croissantes, à divers scénarios dans le contexte d'usage d'un marché cible. Les concepteurs peuvent s'appuyer sur les résultats pour éliminer les produits redondants au sein d'une famille. Des configurations de produits de tailles croissantes peuvent aussi être rapidement simulées et comparées de manière à aboutir à une famille minimale de produits idéalement étagée.

Cette thèse s’inscrit dans le cadre de la programmation par contraintes quantifiées, un formalisme étendantla programmation par contraintes classique en ajoutant aux variables des quantificateurs existentiels ouuniversels, ce qui apporte en théorie une expressivité suffisante pour modéliser des problèmes avec adversaireou incertitude sur certains paramètres sous forme de problèmes appelés QCSP (Quantified Constraintsatisfaction Problem).Nous commençons par apporter une réponse aux difficultés de modélisation de problèmes réels dont estfrappée la programmation par contraintes quantifiées en introduisant une extension aux QCSP permettantd’expliciter les actions possibles de l’agent principal et de son adversaire. Puis, nous décrivons différentproblèmes grâce à ce formalisme, et discutons de la place de cette extension parmi les formalismes voisins créésen réponse à cette même difficulté de modélisation. Enfin, nous nous intéressons à la notion d’optimisationdans le cas des contraintes quantifiées, et apportons un formalisme d’optimisation de contraintes quantifiéespermettant d’exprimer des problèmes multi-niveaux non linéaires. / This thesis presents works in the research area of quantified constraint programming, which extends theconstraint programming framework by setting (existential and universal) quantifiers to the problem’s variables.This framework is theoretically expressive enough to model problems where an opponent or uncertainparameters are involved, under the form of Quantified Constraint Safisfaction Problems (QCSP).QCSPs suffer from a modeling difficulty that we solve by presenting an extension to this framework, in whichpossible moves for the principal agent and its opponent may be explicitely declared. Then, we describe realproblems using this extention, and discuss of its pros and cons against neighbour framework thar were createdto solve the same difficulty. Finally, we focus on quantifies optimization problems, and present a quantifiedoptimization framework thet allows the modeling of nonlinear multi-level problems.

La classification non supervisée, souvent appelée par le terme anglais de clustering, est une tâche importante en Fouille de Données. Depuis une dizaine d'années, la classification non supervisée a été étendue pour intégrer des contraintes utilisateur permettant de modéliser des connaissances préalables dans le processus de clustering. Différents types de contraintes utilisateur peuvent être considérés, des contraintes pouvant porter soit sur les clusters, soit sur les instances. Dans cette thèse, nous étudions le cadre de la Programmation par Contraintes (PPC) pour modéliser les tâches de clustering sous contraintes utilisateur. Utiliser la PPC a deux avantages principaux : la déclarativité, qui permet d'intégrer aisément des contraintes utilisateur et la capacité de trouver une solution optimale qui satisfait toutes les contraintes (s'il en existe). Nous proposons deux modèles basés sur la PPC pour le clustering sous contraintes utilisateur. Les modèles sont généraux et flexibles, ils permettent d'intégrer des contraintes d'instances must-link et cannot-link et différents types de contraintes sur les clusters. Ils offrent également à l'utilisateur le choix entre différents critères d'optimisation. Afin d'améliorer l'efficacité, divers aspects sont étudiés. Les expérimentations sur des bases de données classiques et variées montrent qu'ils sont compétitifs par rapport aux approches exactes existantes. Nous montrons que nos modèles peuvent être intégrés dans une procédure plus générale et nous l'illustrons par la recherche de la frontière de Pareto dans un problème de clustering bi-critère sous contraintes utilisateur. / Cluster analysis is an important task in Data Mining with hundreds of different approaches in the literature. Since the last decade, the cluster analysis has been extended to constrained clustering, also called semi-supervised clustering, so as to integrate previous knowledge on data to clustering algorithms. In this dissertation, we explore Constraint Programming (CP) for solving the task of constrained clustering. The main principles in CP are: (1) users specify declaratively the problem in a Constraint Satisfaction Problem; (2) solvers search for solutions by constraint propagation and search. Relying on CP has two main advantages: the declarativity, which enables to easily add new constraints and the ability to find an optimal solution satisfying all the constraints (when there exists one). We propose two models based on CP to address constrained clustering tasks. The models are flexible and general and supports instance-level constraints and different cluster-level constraints. It also allows the users to choose among different optimization criteria. In order to improve the efficiency, different aspects have been studied in the dissertation. Experiments on various classical datasets show that our models are competitive with other exact approaches. We show that our models can easily be embedded in a more general process and we illustrate this on the problem of finding the Pareto front of a bi-criterion optimization process.

La validation des charges utiles des satellites de télécommunication nécessite des opérations coûteuses en temps et en personnel. Ce coût augmente régulièrement du fait de la complexité croissante des charges utiles. Il est donc crucial pour Astrium d'optimiser la réalisation des opérations de test. L'objectif de cette thèse CIFRE menée en collaboration entre Astrium et l'Onera est de développer une suite logicielle d'aide à la génération de plans de test. Le problème de génération de plan de test a été modélisé sous forme de graphe orienté à états. La NP-complétude de ce problème a été établie. Des modèles mathématiques ont été construits en programmation linéaire en nombres entiers et en programmation par contraintes en vue d'une résolution par des solveurs génériques. Cependant, ces solveurs génériques se sont heurtés à des problèmes d'insuffisance de mémoire liés à la très grande taille des instances à traiter. Ceci nous a conduits à développer un solveur spécialisé à base de recherche arborescente faisant appel à des mécanismes spécifiques de choix de variables et de valeurs, de propagation de contraintes, de calcul de borne, de retour-arrière, d'apprentissage et de redémarrage. Un solveur spécialisé à base de recherche locale a été développé en parallèle. Les résultats obtenus par ces différents solveurs avec différents paramétrages ont pu être comparés. / Telecommunication satellite payload validation requires operations which are expensive in terms of time and manpower. This cost is constantly increasing as the payloads become more and more complex. It is crucial for Astrium to optimise the testing phase to keep these costs under control. The objective of this CIFRE thesis, conducted in collaboration with Astrium and Onera, is to develop a software suite to help generate test plans for the payloads.The problem of generating test plans was modeled using the form of a directed graph with states. The NP-completeness of this problem was proven. Mathematical models were built using integer linear programming and constraint programming with a view to solving the problems using generic solvers. However, these generic solvers had problems due to insufficient memory on account of the large size of instances to be handled. These problems led us to develop a specialised solver using a tree search, with special mechanisms for choosing variables and values, propagating constraints, computing bounds, backjumping,learning, and restarting. A specialised solver based on local search was developed in parallel.The results obtained by these different solvers with different settings were compared.

En adoptant un point de vue utilitariste du consommateur sur certains produits orientés service, nous avons d'abord contribué à la proposition d’un modèle de contextes d’usage que se doit de couvrir au mieux un produit. Le modèle conduit à une meilleure intégration des analyses de marketing et d’ingénierie de la conception amenant à une optimisation d'un produit paramétré plus orientée vers les besoins du marché ou à un meilleur étagement d'une famille de produits. Nous proposons une série d'indices qui révèlent l'adéquation entre les usages couverts par un produit de dimensions données ou une famille de produits donnée avec un espace d'usages cible qu’il s’agit de couvrir dans sa totalité ou en partie mais d'une manière suffisamment dominante par rapport à la concurrence. En premier lieu, l'indice de couverture d’usage (UCI) pour un produit unique est introduit par la cartographie du produit relativement à un ensemble d’utilisateurs représentatifs définis par des usages attendus. Sur cette base, l'UCI pour une famille de produits est construite pour évaluer la composition de la famille et la redondance des produits qui la composent. Les avantages par rapport à la traditionnelle estimation de la demande en marketing sont de réduire la complexité de l'enquête et de l'analyse des données et de pouvoir estimer le niveau de compétitivité d’une offre innovante sans nécessiter de retour d’expérience du marché. Nous expérimentons nos propositions sur un problème de reconception d’une famille de scies sauteuses. L'approche proposée permet d'évaluer l'adaptabilité, pour une famille de produits de tailles croissantes, à divers scénarios dans le contexte d'usage d'un marché cible. Les concepteurs peuvent s'appuyer sur les résultats pour éliminer les produits redondants au sein d'une famille. Des configurations de produits de tailles croissantes peuvent aussi être rapidement simulées et comparées de manière à aboutir à une famille minimale de produits idéalement étagée. / Adopting a utilitarian viewpoint of consumers on some service-oriented goods, we have first contributed to the proposal of a usage contexts model that a product should cover at most. The model leads to a higher integration of design engineering and marketing analyses which results in a more market-oriented optimization of a parameterized product or a better sampling of a product family. We propose a series of usage coverage indices that reveal the adequacy of a dimensioned product or a given product family to a targeted usage space to cover in its whole or for a part but sufficiently in a dominant way compared to competing products. First, the Usage Coverage Index (UCI) for single product is introduced by mapping the given product with a set of representative users defined by expected usages. On that basis, the UCI for a product family is constructed to evaluate the composition and redundancy of the family. The advantage compared to traditional demand estimation in marketing research is to reduce the complexity of survey and data analysis and to assess the competitiveness level of an innovative service offer without needing any return of experience from the market. We experiment our proposals on a jigsaw product family redesign problem. The proposed analysis approach helps to evaluate the adaptability, for a given scale-based product family, to diverse usage context scenarios in a target market. Designers can rely on the results to filter out redundant products within a family. Scale-based configurations of the products can also be rapidly simulated and compared to find out an appropriate sampled series of products.