La programmation par contraintes est un sujet de recherche qui tire profit de nombreuses autres disciplines : mathématiques discrètes, analyse numérique, intelligence artificielle, recherche opérationnelle et calcul formel. Elle a prouvé son intérêt et son efficacité dans de nombreux domaines : optimisation combinatoire, ordonnancement, finance, simulation et synthèse de composants, diagnostic de panne, biologie moléculaire, ou encore problèmes géométriques. Néanmoins, un certain nombre de limitations et de difficultés ont été identifiées dans le domaine : conception d'algorithmes génériques et stables, traitement des problèmes dynamiques, accessibilité des concepts et des outils, ...<br /><br />Dans ce document, nous plaidons pour l'utilisation de la notion d'explication au sein de la programmation par contraintes. Notre but est double : non seulement présenter un tableau général des explications (définition, génération et utilisations) mais aussi montrer comment leur utilisation permet de contribuer à lever certains des problèmes ouverts en programmation par contraintes. Nous présentons aussi une démarche générale de résolution de problème dans un environnement expliqué. Enfin, nous montrons comment ce nouveau sujet semble promis à un bel avenir.

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.

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.

Th. doct.--Informatique--Grenoble 1, 1995. / Bibliogr. p. 285-295. Résumé en anglais et en français. 1996 d'après la déclaration de dépôt légal.

Les problèmes de tournées de véhicules sont des problèmes d’optimisation combinatoire épineux avec des enjeux économiques et environnementaux importants au sein de la chaîne logistique. Le problème fondamental est de desservir des clients avec un ensemble de véhicules de façon à minimiser la distance totale parcourue. En pratique, il y a une grande variété d’objectifs et de contraintes additionnelles, liées à la législation et à la diversité des domaines d’applications. Ces problèmes de tournées sont très fréquents pour de nombreuses industries et la conception d’approches de résolution génériques est devenue une question de recherche importante.Cette thèse porte sur la conception et le développement d’un nouveau moteur de résolution pour les logiciels de tournées de véhicules proposés par l’entreprise GEOCONCEPT. Le solveur mis au point s’appuie sur la programmation par contraintes (PPC) pour améliorer la flexibilité (prise en compte de contraintes additionnelles), la déclarativité et la maintenance qui sont les limites des solveurs actuels de GEOCONCEPT fondés sur la recherche locale.Dans un premier temps, un modèle de graphe est établi pour la représentation unifiée des données et de nombreuses contraintes métiers. La résolution s’effectue par des approches à base de voisinage large disponibles dans les solveurs de PPC modernes. On peut ainsi traiter des instances de très grandes tailles efficacement tout en conservant une approche déclarative pour exprimer une classe très large de problèmes de tournées de véhicules. Dans un second temps, des modèles PPC s’appuyant sur des représentations redondantes du problème sont proposés afin de renforcer le filtrage. Nous nous intéressons en détails aux mécanismes de filtrage c’est-à-dire aux processus d’élimination des valeurs infaisables ou sous-optimales dans les domaines des variables. Ces algorithmes permettent de simplifier rapidement le problème et de fournir des bornes inférieures afin d’évaluer la qualité des solutions obtenues. Les bornes inférieures sont obtenues en résolvant des relaxations du plus célèbre des problèmes de la Recherche Opérationnelle : le problème du voyageur de commerce (TSP). Ce problème est le cœur de la contrainte globale weightedcircuit permettant de modéliser les problèmes de tournées en PPC. Nous proposons de nouveaux mécanismes de filtrage pour cette contrainte s’appuyant sur trois relaxations du TSP. Ces relaxations sont comparées sur les plans théorique et expérimental. L’originalité de ce travail est de proposer un nouvel algorithme de filtrage permettant de raisonner à la fois sur les successeurs directs d’un client et sur sa position dans la tournée. Ces raisonnements sont particulièrement utiles en présence de contraintes de fenêtres de temps, très communes dans les problèmes industriels.Le nouveau moteur de résolution offre d’excellentes performances sur des problèmes académiques et industriels tout en proposant des bornes inférieures informatives à des problèmes industriels réels. / Vehicle routing problems are very hard combinatorial optimization problems with significant economic and environmental challenges. The fundamental problem is to visit a set of customers with a given fleet of vehicles in order to minimize the total distance travelled. Moreover, these problems arise with a wide variety of objectives and additional constraints, related to the legislation and the diversity of industrial sectors. They are very common for many industries and the design of generic solvers has become an important research issue.This thesis focuses on the design and implementation of a new solver for the vehicle routing services offered by the company GEOCONCEPT. The proposed solver is based on constraint programming (CP) to improve flexibility (ability to take additional constraints into account), declarative modelling and maintenance, which are the limits of current GEOCONCEPT solvers based on local search.Firstly, a graph model is established to provide a common representation of the input-data and the numerous business constraints. The resolution is performed using large neighbourhood search methods available in modern CP solvers. It is thus possible to deal with large instances efficiently with a declarative approach where a broad class of vehicle routing problems can be modelled. Secondly, several CP models based on redundant views of the problem are proposed to strengthen the filtering. We focus on the filtering mechanisms for removing infeasible or suboptimal values in the domains of the variables. These algorithms can quickly simplify the problem and derive lower bounds to assert the quality of the solutions found. The lower bounds are obtained by solving relaxations of the most famous problem in Operations Research: the Traveling Salesman Problem (TSP). This problem is the core of the global constraint WEIGTEHDCIRCUIT for modelling routing problems in CP. We propose new filtering algorithms for this constraint based on three relaxations of the TSP. These relaxations are compared theoretically and experimentally. The originality of this work is to propose a new filtering algorithm for reasoning on the direct successors of a customer as well as his position in the tour. It is particularly useful in the presence of time window constraints, which are very common in industrial problems.The new solver shows excellent performance on academic and industrial problems and can compute informative lower bounds for real-life problems.

SPARQL est le langage de requête standard pour les graphes de données du Web Sémantique. L’évaluation de requêtes est étroitement liée aux problèmes d’appariement de graphes. Il a été démontré que l’évaluation est NP-difficile. Les moteurs SPARQLde l’état-de-l’art résolvent les requêtes SPARQL en utilisant des techniques de bases de données traditionnelles. Cette approche est efficace pour les requêtes simples qui fournissent un point de départ précis dans le graphe. Par contre, les requêtes couvrant tout le graphe et impliquant des conditions de filtrage complexes ne passent pas bien à l’échelle. Dans cette thèse, nous proposons de résoudre les requêtes SPARQL en utilisant la Programmation par Contraintes (CP). La CP résout un problème combinatoire enexploitant les contraintes du problème pour élaguer l’arbre de recherche quand elle cherche des solutions. Cette technique s’est montrée efficace pour les problèmes d’appariement de graphes. Nous reformulons la sémantique de SPARQL en termes deproblèmes de satisfaction de contraintes (CSPs). Nous appuyant sur cette sémantique dénotationnelle, nous proposons une sémantique opérationnelle qui peut être utilisée pour résoudre des requêtes SPARQL avec des solveurs CP génériques.Les solveurs CP génériques ne sont cependant pas conçus pour traiter les domaines immenses qui proviennent des base de données du Web Sémantique. Afin de mieux traiter ces masses de données, nous introduisons Castor, un nouveau moteurSPARQL incorporant un solveur CP léger et spécialisé. Nous avons apporté une attention particulière à éviter tant que possible les structures de données et algorithmes dont la complexité temporelle ou spatiale est proportionnelle à la taille de la base dedonnées. Des évaluations expérimentales sur des jeux d’essai connus ont montré la faisabilité et l’efficacité de l’approche. Castor est compétitif avec des moteurs SPARQL de l’état-de-l’art sur des requêtes simples, et les surpasse sur des requête. / SPARQL is the standard query language for graphs of data in the SemanticWeb. Evaluating queries is closely related to graph matching problems, and has been shown to be NP-hard. State-of-the-art SPARQL engines solve queries with traditional relational database technology. Such an approach works well for simple queries that provide a clearly defined starting point in the graph. However, queries encompassing the whole graph and involving complex filtering conditions do not scale well. In this thesis we propose to solve SPARQL queries with Constraint Programming (CP). CP solves a combinatorial problem by exploiting the constraints of the problem to prune the search tree when looking for solutions. Such technique has been shown to work well for graph matching problems. We reformulate the SPARQL semantics by means of constraint satisfaction problems (CSPs). Based on this denotational semantics, we propose an operational semantics that can be used by off-theshelf CP solvers. Off-the-shelf CP solvers are not designed to handle the huge domains that come with SemanticWeb databases though. To handle large databases, we introduce Castor, a new SPARQL engine embedding a specialized lightweight CP solver. Special care has been taken to avoid as much as possible data structures and algorithms whosetime or space complexity are proportional to the database size. Experimental evaluations on well-known benchmarks show the feasibility and efficiency of the approach. Castor is competitive with state-of-the-art SPARQL engines on simple queries, and outperforms them on complex queries where filters can be actively exploited during the search.

Nous étudions la parallélisation de la procédure de recherche de solution d’un problème en Programmation Par Contraintes (PPC). Après une étude de l’état de l’art, nous présentons une nouvelle méthode, nommée Embarrassingly Parallel Search (EPS). Cette méthode est basée sur la décomposition d’un problème en un très grand nombre de sous-problèmes disjoints qui sont ensuite résolus en parallèle par des unités de calcul avec très peu, voire aucune communication. Le principe d’EPS est d’arriver statistiquement à un équilibrage des temps de résolution de chaque unité de calcul afin d’obtenir une bonne répartition de la charge de travail. EPS s’appuie sur la propriété suivante : la somme des temps de résolution de chacun des sous-problèmes est comparable au temps de résolution du problème en entier. Cette propriété est vérifiée en PPC, ce qui nous permet de disposer d’une méthode simple et efficace en pratique. Dans nos expérimentations, nous nous intéressons à la recherche de toutes les solutions d’un problème en PPC, à prouver qu’un problème n’a pas de solution et à la recherche d’une solution optimale d’un problème d’optimisation. Les résultats montrent que la décomposition doit générer au moins 30 sous-problèmes par unité de calcul pour obtenir des charges de travail par unité de calcul équivalentes. Nous évaluons notre approche sur différentes architectures (machine multi-coeurs, centre de calcul et cloud computing) et montrons qu’elle obtient un gain pratiquement linéaire en fonction du nombre d’unités de calcul. Une comparaison avec les méthodes actuelles telles que le work stealing ou le portfolio montre qu’EPS obtient de meilleurs résultats. / We study the search procedure parallelization in Constraint Programming (CP). After giving an overview on various existing methods of the state-of-the-art, we present a new method, named Embarrassinqly Parallel Search (EPS). This method is based on the decomposition of a problem into many disjoint subproblems which are then solved in parallel by computing units with little or without communication. The principle of EPS is to have a resolution times balancing for each computing unit in a statistical sense to obtain a goodDépôt de thèse – Données complémentaireswell-balanced workload. We assume that the amount of resolution times of all subproblems is comparable to the resolution time of the entire problem. This property is checked with CP and allows us to have a simple and efficient method in practice. In our experiments, we are interested in enumerating all solutions of a problem, and proving that a problem has no solution and finding an optimal solution of an optimization problem. We observe that the decomposition has to generate at least 30 subproblems per computing unit to get equivalent workloads per computing unit. Then, we evaluate our approach on different architectures (multicore machine, cluster and cloud computing) and we observe a substantially linear speedup. A comparison with current methods such as work stealing or portfolio shows that EPS gets better results.

La programmation par contraintes est une approche régulièrement utilisée pour traiter des problèmes d’ordonnancement variés. Les problèmes d’ordonnancement cumulatifs représentent une classe de problèmes dans laquelle des tâches non morcelable peuvent être effectuées en parallèle. Ces problèmes apparaissent dans de nombreux contextes réels, tels que par exemple l’allocation de machines virtuelles ou l’ordonnancement de processus dans le "cloud", la gestion de personnel ou encore d’un port. De nombreux mécanismes ont été adaptés et proposés en programmation par contraintes pour résoudre les problèmes d’ordonnancement. Les différentes adaptations ont abouti à des raisonnements qui semblent à priori significativement distincts. Dans cette thèse nous avons effectué une analyse détaillée des différents raisonnements, proposant à la fois une notation unifiée purement théorique mais aussi des règles de dominance, permettant une amélioration significative du temps d’exécution d’algorithmes issus de l’état de l’art, pouvant aller jusqu’à un facteur sept. Nous proposons aussi un nouveau cadre de travail pour l’ordonnancement cumulatif robuste, permettant de trouver des solutions supportant qu’à tout moment une ou plusieurs tâches soit retardées, sans remise en cause de l’ordonnancement généré et en gardant une date de fin de projet satisfaisante. Dans ce cadre, nous proposons une adaptation d’un algorithme de l’état de l’art, Dynamic Sweep. / Constraint programming is an approach regularly used to treat a variety of scheduling problems. Cumulative scheduling problems represent a class of problems in which non-preemptive tasks can be performed in parallel. These problems appear in many contexts, such as for example the allocation of virtual machines, the ordering process in the "cloud", personnel management or a port. Many mechanisms have been adapted and offered in constraint programming to solve scheduling problems. The various adaptations have resulted in reasoning that appear a priori significantly different. In this thesis we performed a detailed analysis of the various arguments, offering both a theoretical unified caracterization but also dominance rules, allowing a significant improvement in execution time of algorithms from the state of the art, up to a factor of seven. we also propose a new framework for robust cumulative scheduling, to find solutions that support at any time one or more tasks to be delayed while keeping a satisfactory end date of the project and without calling into question the generated scheduling. In this context, we propose an adaptation of an algorithm of the state of the art, Dynamic Sweep.

La richesse de la programmation par contraintes repose sur la très large variété des algorithmes qu’elle utilise en puisant dans les grands domaines de l’Intelligence Artificielle, de la Programmation Logique et de la Recherche Opérationnelle. Cependant, cette richesse, qui offre aux spécialistes une palette quasi-illimitée de configurations possibles pour attaquer des problèmes combinatoires, devient une frein à la diffusion plus large du paradigme, car les outils actuels sont très loin d’une boîte noire, et leur utilisation suppose une bonne connaissance du domaine, notamment en ce qui concerne leur paramétrage. Dans cette thèse, nous proposons d’analyser le comportement des contraintes de cardinalité avec des modèles probabilistes et des outils de dénombrement, pour paramétrer automatiquement les solveurs de contraintes : heuristiques de choix de variables et de choix de valeurs et stratégies de recherche. / The main asset of constraint programming is its wide variety of algorithms that comes from the major areas of artificial intelligence, logic programming and operational research. It offers specialists a limitless range of possible configurations to tackle combinatorial problems, but it becomes an obstacle to the wider diffusion of the paradigm. The current tools are very far from being used as a black-box tool, and it assumes a good knowledge of the field, in particular regarding the parametrization of solvers.In this thesis, we propose to analyze the behavior of cardinality constraints with probabilistic models and counting tools, to automatically parameterize constraint solvers: heuristics of choice of variables and choice of values and search strategies.

La programmation par contraintes est une technique accélérant la recherche de solutions pour des problèmes d’optimisation combinatoire. Ce mémoire porte sur l’application de cette technique en ordonnancement. Le but est d’intégrer une fonction de coût convexe à la contrainte Disjunctive qui régit l’ordre d’exécution d’un ensemble de tâches ne pouvant pas se chevaucher dans le temps. Dans ce contexte, le coût est perçu comme un retard déterminé par une échéance préférable indiquée pour chaque tâche. La contribution se traduit en l’introduction de la contrainte DisjunctiveTardiness qui tisse de nouveaux liens entre l’ordre d’exécution des tâches et la somme des retards engendrés. La cohérence de la contrainte est assurée par un algorithme de filtrage. L’algorithme raisonne à partir de la construction d’un réseau de flot pondéré basé sur la fenêtre d’exécution des tâches et leur échéance préférable. Il est implémenté dans un solveur et comparé à une alternative compétitive. Tel qu’observé, le nouvel algorithme amène un filtrage tangible, mais sa complexité trop élevée empêche d’aboutir à un nouvel état de l’art en pratique. En revanche, plusieurs pistes de solution pour réduire le temps d’exécution sont proposées. / Constraint programming is a technology originating from artificial intelligence that explores a search space to solve combinatorial problems. It uses filtering algorithms to filter the search space and speedup the search of a solution. This master thesis covers an application of this method in scheduling. The goal is to integrate a convex cost function to the Disjunctive constraint that governs the execution order of tasks unable to overlap each other on a time line. In this context, the cost is treated as a delay (tardiness) computed from a due date specified for each task. The contribution translates in a new constraint named DisjunctiveTardiness that brings a stronger relation between the order in a schedule and the sum of tardinesses. Consistency of the constraint is achieved by a filtering algorithm. The algorithm builds a weighted network flow from the allowed time window of the tasks and their due date. The solution is implemented in a solver. The experimental results show that the new algorithm applies stronger filtering, but its time complexity is too high to recommend it in practice. To conclude, several potential upgrades are proposed to reduce the execution time.