L’optimisation combinatoire concerne la résolution de problèmes pour lesquels les variables prennent des valeurs discrètes et sur lesquelles s’appliquent des contraintes. L’ensemble des variables et des contraintes définissent un modèle représentant le problème. Un très grand nombre de problèmes industriels peuvent être représentés sous cette forme. Un logiciel qui prend un modèle en entrée et produit une solution est appelé solveur. La programmation par contraintes (PPC) est l’une des techniques algorithmiques pouvant être utilisée par ces solveurs. Dans ce mémoire, nous développons un nouveau solveur. L’objectif premier est de compter sur un solveur facilement modifiable dans le but d’y ajouter de nouvelles approches de résolution développées par les chercheurs. De plus, dans le but de démontrer l’utilité du solveur, nous développons une approche exploitant ce solveur dans le but de générer des patrons de chargement alternatifs pour un séchoir à bois utilisé par l’industrie des produits forestiers. Finalement, nous présentons dans ce mémoire une nouvelle technique pour résoudre avec plus d’efficience certains problèmes de PPC. Les algorithmes de filtrage associés aux contraintes sont typiquement déclenchés en fonction d’événements qui se produisent lors de la résolution du problème. Nous proposons un nouvel événement qui permet d’effectuer du filtrage tardif des variables. Nous montrons que, pour un problème classique d’optimisation combinatoire (Balanced Incomplete Block Design), il donne une meilleure performance tout en maintenant le même niveau de filtrage par rapport à l’utilisation des événements classiques. / Combinatorial optimization concerns the solving of problems for which the variables take discrete values and on which constraints apply. The set of variables and constraints form the model of the problem. A lot of industrial problems can be represented in this form. A solver is a software that takes as input a model and produces a solution. Constraint programming (CP) is one of the algorithmic techniques that can be used within a solver. In this master’s thesis, we develop a new solver. The primary objective is to rely on an easily modifiable solver in order to add new resolution approaches developed by researchers. Moreover, in order to demonstrate the utility of the solver, we develop an approach using that solver in order to generate alternative loading patterns for a kiln in the forest industry. Finally, in this master’s thesis, we present a new technique for solving some CP problems. The filtering algorithms are triggered according to events that occur when solving the problem. We propose a new event that allows to perform a lazy filtering of the variables. We demonstrate, on a classical combinatorial optimization problem (Balanced Incomplete Block Design), that it gives a better performance while maintaining the same level of filtering when compared with classical events.

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.

Nous étudions dans cette thèse deux approches réduisant le temps de traitement nécessaire pour résoudre des problèmes de planification et d'ordonnancement dans un contexte de programmation par contraintes. Nous avons expérimenté avec plusieurs milliers de processeurs afin de résoudre le problème de planification et d'ordonnancement des opérations de rabotage du bois d'oeuvre. Ces problèmes sont d'une grande importance pour les entreprises, car ils permettent de mieux gérer leur production et d'économiser des coûts reliés à leurs opérations. La première approche consiste à effectuer une parallélisation de l'algorithme de résolution du problème. Nous proposons une nouvelle technique de parallélisation (nommée PDS) des stratégies de recherche atteignant quatre buts : le respect de l'ordre de visite des noeuds de l'arbre de recherche tel que défini par l'algorithme séquentiel, l'équilibre de la charge de travail entre les processeurs, la robustesse aux défaillances matérielles et l'absence de communications entre les processeurs durant le traitement. Nous appliquons cette technique pour paralléliser la stratégie de recherche Limited Discrepancy-based Search (LDS) pour ainsi obtenir Parallel Limited Discrepancy-Based Search (PLDS). Par la suite, nous démontrons qu'il est possible de généraliser cette technique en l'appliquant à deux autres stratégies de recherche : Depth-Bounded discrepancy Search (DDS) et Depth-First Search (DFS). Nous obtenons, respectivement, les stratégies Parallel Discrepancy-based Search (PDDS) et Parallel Depth-First Search (PDFS). Les algorithmes parallèles ainsi obtenus créent un partage intrinsèque de la charge de travail : la différence de charge de travail entre les processeurs est bornée lorsqu'une branche de l'arbre de recherche est coupée. En utilisant des jeux de données de partenaires industriels, nous avons pu améliorer les meilleures solutions connues. Avec la deuxième approche, nous avons élaboré une méthode pour minimiser les changements effectués à un plan de production existant lorsque de nouvelles informations, telles que des commandes additionnelles, sont prises en compte. Replanifier entièrement les activités de production peut mener à l'obtention d'un plan de production très différent qui mène à des coûts additionnels et des pertes de temps pour les entreprises. Nous étudions les perturbations causéees par la replanification à l'aide de trois métriques de distances entre deux plans de production : la distance de Hamming, la distance d'édition et la distance de Damerau-Levenshtein. Nous proposons trois modèles mathématiques permettant de minimiser ces perturbations en incluant chacune de ces métriques comme fonction objectif au moment de la replanification. Nous appliquons cette approche au problème de planification et ordonnancement des opérations de finition du bois d'oeuvre et nous démontrons que cette approche est plus rapide qu'une replanification à l'aide du modèle d'origine. / We study in this thesis two approaches that reduce the processing time needed to solve planning and ordering problems in a constraint programming context. We experiment with multiple thousands of processors on the planning and scheduling problem of wood-finish operations. These issues are of a great importance for businesses, because they can better manage their production and save costs related to their operations. The first approach consists in a parallelization of the problem solving algorithm. We propose a new parallelization technique (named PDS) of the search strategies, that reaches four goals: conservation of the nodes visit order in the search tree as defined by the sequential algorithm, balancing of the workload between the processors, robustness against hardware failures, and absence of communication between processors during the treatment. We apply this technique to parallelize the Limited Discrepancy-based (LDS) search strategy to obtain Parallel Limited Discrepancy-Based Search (PLDS). We then show that this technique can be generalized by parallelizing two other search strategies: Depth-Bounded discrepancy Search (DDS) and Depth-First Search (DFS). We obtain, respectively, Parallel Discrepancy-based Search (PDDS) and Parallel Depth-First Search (PDFS). The algorithms obtained this way create an intrinsic workload balance: the imbalance of the workload among the processors is bounded when a branch of the search tree is pruned. By using datasets coming from industrial partners, we are able to improve the best known solutions. With the second approach, we elaborated a method to minimize the changes done to an existing production plan when new information, such as additional orders, are taken into account. Completely re-planning the production activities can lead to a very different production plan which create additional costs and loss of time for businesses. We study the perturbations caused by the re-planification with three distance metrics: Hamming distance, Edit distance, and Damerau-Levenshtein Distance. We propose three mathematical models that allow to minimize these perturbations by including these metrics in the objective function when replanning. We apply this approach to the planning and scheduling problem of wood-finish operations and we demonstrate that this approach outperforms the use of the original model.

Dans le cadre de cette thèse, nous nous sommes intéressés à la mise en œuvre d'algorithmes auto-adaptatifs d'Intelligence Collective pour la résolution de problèmes d'optimisation modélisés dans un langage de Programmation par contraintes (PPC). Nous avons porté une attention particulière à la famille d'algorithmes de type " Ant Colony Optimization " (ACO). Nous avons développé trois contributions, à savoir : (1) Intégration des algorithmes de type ACO dans un langage de programmation par contraintes pour la résolution de problèmes de satisfaction de contraintes; (2) Proposition d'un algorithme hybride et générique où ACO est couplé à une approche complète pour résoudre des problèmes d'optimisation combinatoires (3) Proposition d'une stratégie capable d'adapter dynamiquement les paramètres de ACO.

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.

L'optimisation des tournées de livraison est souvent modélisée par un problème de voyageur de commerce (Traveling Salesman Problem / TSP). Pour ce problème, il est fréquent d’avoir des contraintes additionnelles telles que, par exemple, des fenêtres horaires limitant les heures de livraison chez le client ou des pauses obligatoires pour les conducteurs des camions. Le temps est une dimension importante à prendre en compte pour respecter ces contraintes. Cependant, les durées des trajets ne sont généralement pas constantes mais varient en fonction des congestions, et cette variabilité doit être intégrée au moment de l’optimisation des tournées. Ainsi, le problème du voyageur de commerce dépendant du temps (Time Dependent TSP / TD-TSP) est la version étendue du TSP où le coût d'un arc dépend de l'heure à laquelle cet arc est emprunté. Dans cet thèse nous proposons un nouveau benchmark pour le TD-TSP basé sur des données réelles de trafic (fournies par la Métropole de Lyon) et nous montrons l'intérêt de prendre en compte la variabilité des durées dans ce problème. Nous étudions comment mieux modéliser les fonctions de durée de trajet dépendantes du temps. Nous introduisons et comparons différents modèles pour résoudre le TD-TSP avec la programmation par contraintes (Constraint Programming / CP). Un premier modèle est directement dérivé du modèle CP classique pour le TSP. Nous montrons que ce modèle ne permet pas de raisonner avec des relations de précédence indirectes, ce qui pénalise sa performance sur notre benchmark. Nous introduisons une nouvelle contrainte globale qui est capable d'exploiter des relations de précédence indirectes sur des données dépendantes du temps et nous introduisons un nouveau modèle CP basé sur notre nouvelle contrainte. Nous comparons expérimentalement les deux modèles sur notre benchmark, et nous montrons que notre nouvelle contrainte permet de résoudre le TD-TSP plus efficacement. / In the context of urban deliveries, the optimization of delivery tours is usually modeled as a Traveling Salesman Problem (TSP). Side constraints like time-windows constraining the delivery times at the client or breaks for the drivers are also common in this kind of problem and time is an important dimension to take into account to respect these constraints. With travel times' variability in big cities time also tends to have a greater influence in costs and therefore it should be included in the optimization of delivery routes. The Time-Dependent Traveling Salesman Problem (TDTSP) is the extended version of the Traveling Salesman Problem (TSP) where arc costs depend on the time when the arc is traveled. In this thesis we propose a set of benchmarks for the TDTSP based on real traffic data (obtained from the city of Lyon) and show the interest of handling time dependency in the problem. A study of how to better model time-dependent travel functions in general and specifically for our approach is performed. We introduce and compare different models to solve the TDTSP with Constraint Programming (CP). A first model is derived in a straightforward way from the classical CP model for the TSP. We show that this model is not able to reason on indirect precedence relations, so that it has poor performance on our benchmark. We introduce a new global constraint which is able to exploit indirect precedence relations on time-dependent data, and we introduce a second model which is based on our new constraint. We experimentally compare the two models on our benchmark.

Cette thèse traite de l'adaptation du niveau de cohérence locale au cours de la résolution d'un problème de satisfaction de contraintes (CSP). En particulier, nous nous intéressons à l'utilisation des propriétés de cohérence locale plus fortes que la cohérence d'arc (AC) pour gagner en efficacité de résolution d'un CSP. Les cohérences plus fortes que AC sont généralement coûteuses à maintenir dans un réseau de contraintes. Par conséquent, elles sont rarement utilisées en pratique. Cette thèse apporte plusieurs contributions qui permettent de bénéficier de la puissance de filtrage de ces cohérences fortes tout en évitant le coût élevé de les maintenir dans tout le réseau de contraintes. Premièrement, nous introduisons la cohérence locale paramétrée (p-LC), une approche originale qui permet de définir des niveaux de cohérence intermédiaires entre AC et une de cohérence locale LC, plus forte que AC. Puis, nous présentons l'instanciation de cette approche à maxRPC et SAC, deux cohérences plus fortes que AC. Il en découle deux cohérences paramétrées, à savoir p-maxRPC et p-SAC. Ensuite, nous présentons l'algorithme p-maxRPC3, qui réalise p-maxRPC et l'algorithme p-SAC1, pour réaliser p-SAC dans un réseau de contraintes. Deuxièmement, nous montrons expérimentalement que maintenir un niveau de cohérence intermédiaire p-LC, peut donner un bon compromis entre puissance de filtrage et coût de calcul nécessaire pour maintenir ce niveau de cohérence. En outre, nous montrons que pour chaque instance de CSP il est possible de trouver un paramètre adéquat qui donne ce bon compromis. L'approche de cohérence paramétrée ne précise pas comment le paramètre peut être choisi a priori. Nous proposons donc deux techniques qui permettent d'ajuster automatiquement le niveau de cohérence paramétrée p-LC. Ces deux techniques utilisent plusieurs paramètres à la fois. Chaque paramètre est associé à une partie du problème et s'adapte automatiquement et localement au cours de la résolution. Finalement, nous proposons POAC1, le premier algorithme pour établir partition-one-AC (POAC) dans un réseau de contraintes. Puis, en comparant POAC à SAC nous constatons que POAC converge au point fixe plus rapidement que SAC. Sur la base de ce constat, nous proposons APOAC, une version adaptative de POAC qui contrôle le nombre de variables sur lesquelles POAC est appliqué. / This thesis deals with adapting the level of consistency during solving a constraint satisfaction problem (CSP). It focuses on the use of local consistency properties stronger than arc consistency (AC) to improve the CSP solving efficiency. Local consistency properties stronger than arc consistency are generally expensive to maintain in a constraint network. Therefore, these local consistencies are seldom used in practice. This thesis gives several contributions to benefit from the filtering power of local consistencies stronger than AC while avoiding the high cost of maintaining them in the whole constraint network and throughout the search. First, we introduce the parameterized local consistency (p-LC), an original approach that allows us to define intermediate levels of consistency between AC and a local consistency LC stronger than AC. Then, we present the instantiation of the parameterized local consistency approach to maxRPC and SAC, two consistencies stronger than AC. This leads to two parameterized consistencies, namely p-maxRPC and p-SAC. After giving the definitions of p-maxRPC and p-SAC, we present the algorithm p-maxRPC3, that achieves p-maxRPC and the algorithm p-SAC1, for achieving p-SAC in a constraint network. We show experimentally that maintaining an intermediate level of consistency p-LC, can give a good compromise between filtering power and the computational cost of maintaining this level of consistency. We also show that for each instance of CSP we can find a parameter that gives this good compromise. The parameterized local consistency approach does not specify how the parameter can be chosen a priori. Hence, we propose two techniques to automatically adjust the parameter p. In fact, both techniques don't use a single parameter, but several parameters. Each parameter is mapped to a part of the problem and it is automatically and locally adjusted during search. Finally, we propose POAC1, the first algorithm achieving partition-one-AC (POAC) in a constraint network. We compare POAC to SAC and we found that POAC converges faster than SAC to the fixed point due to its ability to prune values from all variable domains when being enforced on a given variable. Based on this observation, we proposed APOAC, an adaptive version of POAC, that monitors the number of variables on which to enforce POAC.

Il existe plusieurs approches qui modélisent des réseaux de régulation génétiques a

Le but de ce travail est de proposer un système formel pour prouver que l'ensemble des succès d'un programme logique est inclus dans l'ensemble correspondant d'un autre programme. Cela permet de prouver que deux programmes logiques, un qui représente la spécification et un représentant l'implantation sont équivalents. Le langage logique considéré est CLPforall qui est le langage le langage de programmation logique avec contraintes (CLP) auquel est ajouté le quantificateur universel. Nous présentons les sémantiques des succès finis et infinis et montrons qu'elles sont données par le plus petit et le plus grand point fixe du même opérateur. Un système de preuve pour l'inclusion des succès finis est présenté. Le système utilise pour les opérateurs et les quantificateurs logiques les mêmes règles que la logique du premier ordre. Pour raisonner sur les prédicats récursifs le système contient une règle d'induction. Nous prouvons la correction du système sous certains conditions. Un système analogue pour l'inclusion des succès infinis est présenté. La règle d'induction est remplacée par une règle de coinduction. La correction est démontrée sous conditions analogues. Les deux systèmes sont équivalents sous certains conditions. Une implantation a été réalisée sous la forme d'assistant de preuve écrit en Prolog. Le programme a environ 4000 lignes et contient des procédures simples mais efficaces de recherche de preuves. Nous présentons des exemples de preuves réalises avec ce programme parmi lesquels la preuve de correction de quicksort.

La conception architecturale de systèmes mécaniques et énergétiques permet d'étudier la faisabilité de concepts préalablement choisis pendant la phase de recherche de concepts. Elle fait partie de la phase de conception préliminaire et son achèvement vise à définir l'architecture globale qui sera étudiée pendant la phase de conception détaillée d'un produit. Les principales caractéristiques d'un produit (dimensions, choix de composants, de formes, de topologies ou de matériaux) sont alors fondamentales à ce stade de la conception. La conception architecturale nécessite aussi la prise en compte des comportements physiques et des interactions du produit, de ses composants et des milieux extérieurs, de critères économiques, environnementaux, etc. suivant les exigences du cahier des charges fonctionnel. Le concepteur définit un modèle mathématique exprimant cette connaissance liée au produit. Ce modèle peut être traité à l'aide d'un solveur de Problèmes de Satisfaction de Contraintes numériques (CSP). Ce type de solveur traite de manière générique des problèmes formulés à l'aide de contraintes, de variables et de domaines. Nous proposons de nouveaux algorithmes et de nouvelles heuristiques qui prennent en compte des besoins spécifiques au concepteur en conception préliminaire, comme : la classification des variables, les précisions relatives aux valeurs de certaines variables, les contraintes par morceaux. Les études de faisabilité de plusieurs systèmes mécaniques et énergétiques ont été réalisées avec succès. Les nouveaux algorithmes ont permis de diminuer significativement les temps de calculs, mais ils ont aussi permis d'améliorer la qualité des solutions calculées au regard des besoins du concepteur.