Étant donné que les minéraux apparaissent fréquemment dans des associations complexes dans la nature, la libération minérale est un aspect clé du traitement de minerais et celle-ci est accomplie par comminution. Cette opération est certainement l’une des plus importantes, mais aussi des plus coûteuses dans l’industrie. La réussite globale d’une usine dépend souvent de la performance du circuit de broyage car il existe un compromis pour atteindre la taille des particules libérant les minéraux ciblés afin d’obtenir des concentrés de haute pureté tout en ayant de faibles coûts d’opération, lesquels sont largement influencés par la consommation énergétique. Dans les années récentes, les entreprises ont été confrontées à des objectifs de performance plus exigeants, une concurrence accrue sur les marchés, et des réglementations environnementales et de sécurité plus strictes. D’autres défis supplémentaires sont inhérents aux circuits de broyage, par exemple les réponses non linéaires, le niveau élevé d’intercorrélation entre les variables et les recirculations de matière. Les problèmes ci-dessus soulignent la pertinence d’avoir des systèmes de contrôle et d’optimisation adéquats pour lesquels les praticiens profitent de plus en plus des approches basées sur des modèles pour y faire face de façon systématique. La modélisation et la simulation sont des outils puissants ayant des avantages significatifs tels que les faibles coûts, les temps requis pour réaliser des expériences relativement courts et la possibilité de tester des conditions opérationnelles extrêmes ainsi que différentes configurations des circuits sans interrompre la production. De toute évidence, la qualité des résultats sera aussi bonne que la capacité du modèle à représenter la réalité, ce qui souligne l’importance d’avoir des modèles précis et des procédures de calibrage appropriées, un sujet fréquemment omis dans la littérature. Un autre aspect essentiel qui n’a pas été rapporté est l’intégration efficace de la libération minérale aux systèmes de contrôle et d’optimisation de procédés. Bien qu’il s’agisse d’une information clé directement liée aux performances de l’étape de concentration, la plupart des stratégies se concentrent exclusivement sur la taille de particule du produit. Ceci est compréhensible étant donné qu’il est impossible de mesurer la distribution de libération présentement. Basée sur une librairie de simulation d’usines de traitement des minerais déjà existante, cette recherche aborde lesdits problèmes en (1) développant un modèle de libération minérale visant à coupler les étapes de broyage et de concentration ; (2) programmant et validant par calibrage un modèle phénoménologique de broyeur autogène/semi-autogène (BA/BSA), nécessaire pour compléter la librairie de simulation ; (3) couplant un simulateur de circuit de broyage à un procédé de concentration avec le modèle de libération, et (4) développant un système de contrôle et d’optimisation qui considère explicitement des données de libération minérale pour évaluer les avantages économiques. Les principaux résultats confirment que le modèle de libération est capable de reproduire avec précision des distributions de libération minérale couramment observées dans l’industrie. Cependant, si les données de calibrage correspondent à un point d’opération unique, la validité pourrait être limitée aux régions voisines proches. Le problème de caractériser l’évolution de la libération minérale aux diverses conditions d’opération ainsi qu’aux régimes transitoires reste à être abordé. Le modèle de libération s’est aussi révélé utile pour coupler des circuits de broyage avec des procédés de concentration, en particulier pour une unité de flottation. Quant au modèle de BA/BSA, celui-ci peut capturer le régime statique ainsi que la dynamique d’un broyeur réel et conjointement avec le reste des équipements dans la librairie de simulation, des circuits de broyage industriels. Ceci a été confirmé par le calibrage à partir des données d’opération d’une usine et des tests en laboratoire, tout en suivant une procédure systématique, contribuant aussi au sujet de l’établissement de méthodologies de calibrage standardisées. Pour terminer, les expériences concernant la stratégie de contrôle et d’optimisation basée sur la libération minérale suggèrent que l’utilisation de cette information peut améliorer la performance globale des circuits de broyage-séparation en réagissant aux variations des caractéristiques de libération, qui à leur tour influencent l’efficacité de séparation. L’étude de cas réalisé révèle que cela peut entraîner une augmentation du débit massique et de la teneur du concentré, de la récupération des métaux et des revenus de l’ordre de +0.5%, +1%, +1% et +5%, respectivement, par rapport au cas où ces informations sont omises. / As minerals frequently appear in complex associations in nature, mineral liberation is one of the most relevant aspects in ore processing and is achieved through comminution. This operation is one of the most important, but also one of the most expensive ones in industry. The global efficiency of a plant often depends on the performance of the grinding circuit, since there is a compromise to achieve the particle size liberating the targetted minerals in order to obtain high purity concentrates while maintaining low operating costs, which are largely influenced by the energy consumption. In recent years, companies have been facing more demanding performance targets, stronger competition, and more stringent environmental and safety regulations. Additional challenges are inherent to the grinding circuits themselves, e.g. the nonlinear responses, high degree of intercorrelation of the different variables, and material recirculations. The abovementioned issues highlight the relevance of adequate process control and optimisation, and practitioners rely more often on model-based approaches in order to face them systematically. Modeling and simulation are powerful tools with significant advantages such as low costs, required times for conducting experiments are relatively short, and the possibility of testing extreme operational conditions as well as different circuit configurations without disrupting production. Evidently, the quality of the results will only be as good as the model capacity to represent the reality, which emphasises the relevance of having precise models and proper calibration procedures, the latter being a topic frequently omitted in the literature. Another crucial aspect that has not been reported yet is the effective integration of mineral liberation in control and optimisation schemes. Although it is a key piece of information directly related to the performance of the concentration stage, most strategies focus exclusively on the particle size. This is understandable given that it is currently impossible to measure the liberation distribution online. Based on an existing mineral processing plant simulation library, this research addresses these problems by (1) developing a mineral liberation model aiming at linking the grinding and concentration stages; (2) programming a phenomenological autogenous/semiautogenous (AG/SAG) mill model, required to complement the simulation toolbox, and validating it through calibration; (3) coupling a grinding circuit simulator to a concentration process by means of the liberation model, and (4) developing a plantwide control and optimisation scheme considering mineral liberation data explicitly to evaluate the economic benefits. The main results confirm that the liberation model is capable of reproducing accurately mineral distributions observed in industry. If calibration data correspond to a single operating point, its validity may however be limited to the close neighbourhood. Characterising the evolution of mineral liberation in different operating conditions and transient states remains to be addressed. The liberation model proved to be equally useful in coupling grinding circuits with concentration processes, specifically for flotation. As for the AG/SAG mill model, it can capture the steady state and dynamic behaviour of an actual device and, along with the rest of pieces of equipment in the simulation toolbox, of industrial grinding circuits. This was confirmed through calibration from plant data and laboratory testwork following a systematic procedure, contributing to the endeavour of establishing standard calibration methodologies. Lastly, the results of the designed control and optimisation scheme suggest that using liberation data for control and real-time optimisation can improve the overall performance of grinding-separation circuits by reacting to variations in the liberation characteristics, which in turn influence the concentration performance. The case study reveals that doing so can lead to increases in the concentrate mass flow rate and grade, metal recovery, and global profits in the order of +0.5%, +1%, +1%, and +5%, respectively, compared to the case omitting this information.

This thesis gives a comprehensive view of the scope of formulations and<br />related solution approaches for the cutting stock problem (CSP) and its<br />variants. The focus is on branch-and-price approaches. Specialized<br />algorithms are developed for knapsack subproblems that arise in the<br />course of the algorithm. Thorough numerical tests are used to identify good strategies<br />for initialization, stabilization, branching, and producing<br />primal solutions. Industrial variants of the <br />problem are shown to be tractable for a branch-and-price approach.<br /><br /><br />The models studied are the following: the standard cutting stock and<br />bin packing problems, a variant in which the production levels lie in<br />a prescribed interval of tolerance, the multiple width cutting stock<br />problem in which stock pieces are of different size, a variant with<br />additional technical constraints that arise typically in industrial<br />applications, and a variant where the number of distinct cutting<br />patterns used is minimized given a waste threshold. <br /><br /><br />First, we consider various formulation of the Cutting Stock Problem<br />(CSP): different models of the knapsack subproblem can be exploited to<br />reformulate the CSP. Moreover, we introduce different ways of<br />modeling local exchanges in the solution (primal exchanges imply dual<br />constraints that stabilize the column generation procedure). Some<br />models are shown to be valid integer programming (IP) reformulations while others define<br />relaxations. The dual bounds defined by their LP solution are compared<br />theoretically.<br /><br />Then, we study the variants of the knapsack subproblem that arise<br />in a column generation approach to the CSP. The branching constraints<br />used in the branch-and-price algorithm can result in class bound and<br />setup cost or the need for a binary decomposition in the subproblem. <br />We show how standard knapsack solvers (dynamic programming approach and specialized<br />branch-and-bound algorithm) can be extended to these variants of the<br />knapsack problem.<br /><br />Next, we discuss some branch-and-price implementation strategies. We compare <br />different modes of initialization of the column generation procedure, we present our numerical study of various stabilization<br />strategies to accelerate convergence of the procedure. We compare in particular the impact of the various ways of introducing<br />local exchanges in our primal model and other stabilization techniques<br />such as dual solution smoothing techniques or penalization from a<br />stability center that prevent the fluctuation of the dual variables. <br />To generate the columns we study different strategies based on the use of heuristic columns or on a multiple generation of columns.<br />We also consider the use of heuristics based on column generation to find a primal bound. These are compared to a classic constructive heuristic. Then, we compare the different branching rules that are used in the branch-and-price procedure. <br /><br />Finally, we present numerical results on two industrial applications that<br />correspond to the variant with technical restrictions for which we<br />minimize first the waste and then the number of setups.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

La programmation mathématique est une technique qui peut être utilisée pour résoudre des problèmes concrets où l'on veut maximiser, ou minimiser, une fonction objectif soumise à des contraintes sur les variables décisionnelles. Les caractéristiques les plus importantes de la programmation mathématique sont la création d'un modèle pour décrire le problème (aussi appelé formulation), et la mise en œuvre d'algorithmes efficaces pour le résoudre (aussi appelés solveurs). Dans cette thèse, on s'occupe du premier point. Plus précisemment, on étudie certains problèmes qui proviennent de domaines diffèrents, et en commençant par les modèles les plus naturels pour les décrire, on présente des formulations alternatives, qui partagent certaines propriétés avec le modèle original mais qui sont en quelque sorte meilleures (par exemple au niveau du temps d'exécution nécessaire pour obtenir la solution par le solveur). Ces nouveaux modèles sont appelés reformulations. On suit la classification des reformulations proposée par Liberti dans [Reformulations in Mathematical Programming: Definitions and Systematics, RAIRO-OR, 43(1):55-86, 2009]: exact reformulations (aussi appellées opt-reformulations), narrowings, relaxations. Cette thèse concerne trois applications de la programmation mathématique où les reformulations ont été fondamentales pour obtenir une bonne solution. Le premier problème étudié est le partitionnement de graphes sur la base de la maximisation de la modularité. Comme ce problème est NP-difficile, plusieurs heuristiques sont proposées. On s'occupe d'un algorithme séparatif hiérarchique qui fonctionne en divisant récursivement une classe en deux nouvelles classes de façon optimale. Cet étape de division est accomplie en résolvant un programme binaire quadratique et convexe. Il est reformulé de manière exacte pour obtenir une forme plus compacte sans modifier l'ensemble des solutions optimales (exact reformulation). On considère aussi l'impact donné par la réduction du nombre des solutions symétriques globalement optimales. Les temps d'exécution sont considérablement réduits par rapport à la formulation originelle. Le deuxième problème étudié dans cette thèse est le placement de cercles égaux dans un carré (Packing Equal Circles in a Square, ou PECS), où l'on veut placer des cercles égaux dans un carré de côté 1 sans avoir de superposition et en maximisant le rayon commun. L'une des raisons pour laquelle le problème est difficile à résoudre vient de la présence de plusieurs solutions symétriques optimales, et par conséquent un arbre de séparation-et-évaluation (ou Branch-and-Bound) très large. Certaines solutions symétriques optimales sont rendues irréalisables en ajoutant des contraintes pour briser les symétries (Symmetry Breaking Constraints, ou SBCs) à la formulation, en obtenant ainsi un narrowing. Le temps d'exécution et la dimension de l'arbre de Branch-and-Bound sont tous les deux meilleurs par rapport à la formulation originelle. La troisième application considérée dans cette thèse est le calcul de la relaxation convexe pour des problèmes multilinéaires, et la comparaison de la formulation ''primale'' avec celle obtenue par une représentation ''duale''. Bien que ces deux relaxations soient déjà connues, il est intéressant de voir que la relaxation duale conduit à des meilleures performances de calcul.

Ce mémoire d'habilitation à diriger des recherches traite de problèmes d'optimisation dans les réseaux, dont la modélisation et la résolution reposent sur les outils de la recherche opérationnelle. Le premier chapitre retrace brièvement mon parcours de formation, ainsi que mes activités d'enseignement et de recherche. Le second chapitre est consacré aux réseaux de capteurs sans fil. La minimisation du défaut de couverture, la maximisation de la durée de vie et l'exploration de compromis entre ces deux objectifs sont abordés à l'aide d'un algorithme de génération de colonnes combiné à un algorithme génétique. Le troisième chapitre traite de la configuration robuste d'un réseau de distribution d'électricité visant à le prémunir des effets néfastes d'une augmentation de la demande. Un algorithme basé sur la génération de plans coupants associé à des inégalités valides est notamment proposé, puis comparé avec une formulation basée sur la programmation linéaire en nombres entiers et une heuristique. Le quatrième chapitre aborde le problème du déploiement (ou la mise à niveau) d'un réseau de fibre optique permettant la communication multicast, avec pour but de minimiser le coût des équipements opto-électroniques à installer. Deux versions du problème, qui se distinguent par l'expression du coût des équipements en question, sont abordés à l'aide d'un algorithme de plans coupants enrichi par une fonction de réparation et une recherche tabou, illustrant l'efficacité d'une étroite collaboration entre méthodes exactes et approchées. Enfin, ce mémoire est clos par un chapitre consacré à la présentation de perspectives ouvertes par ces travaux, ainsi qu'une réflexion plus personnelle sur l'exercice de la direction de recherche au niveau individuel, dans l'encadrement doctoral, et dans la direction d'équipe.

Le soin à domicile est un secteur en plein essor ces dernières années. Cela est dû au vieillissement de la population, à la volonté de réduire les coûts hospitaliers et d’assurer le bien-être du patient en le gardant dans son cadre familial tout en maintenant la qualité des soins. L’organisation de ces soins nécessite une prise de décisions aux niveaux stratégique, tactique et opérationnel. Cette thèse s’articule autour de l’étude de problèmes apparaissant uniquement au niveau opérationnel. Ces problèmes traitent de la planification des tournées du personnel de soins à domicile. La première étape de cette étude a consisté à faire une revue de la littérature. De nombreux modèles mathématiques ont été formulés dans la littérature. Cependant, ces modèles étaient dédiés à une structure de soins à domicile spécifique et pouvaient être difficilement transposés. Nous proposons ici une approche générique tant du point de vue de la modélisation que des méthodes de résolutions. À cet effet, nous avons identifié les caractéristiques fréquemment rencontrées dans la littérature à travers cette revue de la littérature. Un modèle générique a été proposé prenant en compte la plupart des caractéristiques. Ce modèle générique constitue un socle pour la construction de méthodes de résolution. Deux méthodes de résolution ont été conçues. La première méthode est une méthode par décomposition et la deuxième méthode est un algorithme hybride génétique avec gestion de la population. Ces deux méthodes utilisent des représentations d’une solution issues de la littérature et adaptées aux caractéristiques du problème. Des expérimentations numériques ont été réalisées dans le but d’évaluer les méthodes proposées et de se comparer à la littérature. / The home care is a growing sector. Many questions research problems exist. We can identify at strategic level the districting problem ; at tactical level, the resource dimensioning problem ; and operational level, the operation assignment and the home care routing and scheduling problem. This thesis focuses on the last one. For this purpose, we propose a state of the art, a generic model and two solutions methods hybrid genetic algorithm and a decomposition.

Étant donnés un planning aérien et des prévisions de demande, le problème d'affectation de flotte aérienne consiste à déterminer la meilleure façon de répartir les types d'appareils sur les vols. Cette répartition a un impact majeur sur le profit d'une compagnie aérienne, puisqu'elle détermine les quantités de places disponibles sur les itinéraires du réseau aérien, ainsi que le coût de fonctionnement de celui-ci. Des décennies de recherche ont rendues les modélisations de ce problème de plus en plus réalistes. Cette thèse s'inscrit dans la continuité de ces recherches en considérant le problème d'affectation de flotte dans un contexte où les demandes des passagers sont incertaines. Nous proposons dans un premier temps une étude autour des deux modèles de la littérature les plus utilisés dans l'industrie, FAM et IFAM. Nous montrons que FAM peut être vu comme une Relaxation Lagrangienne de IFAM, avec des multiplicateurs Lagrangiens particuliers. Nous implémentons cette relaxation, et nous appliquons des résultats connus pour l'étendre en une génération de colonnes basée sur une décomposition de Dantzig-Wolfe de IFAM. Nous étudions ensuite les effets que l'imprécision des prévisions peut avoir sur la performance d'IFAM, et nous présentons au terme de cette étude une nouvelle approche pour modéliser le problème d'affectation de flotte. Notre modèle, Market Driven Fleet Assignment Model (MDFAM), intègre les demandes par itinéraires comme variables de décision, et contraint ces demandes plutôt que de les considérer comme une entrée fixe. Nous appelons les contraintes résultantes des contraintes de Marché. Nous illustrons la flexibilité de cette approche à travers divers exemples, et nous proposons une série d'expériences visant à déterminer quelles sont les contraintes de marché donnant les meilleurs résultats. Nous comparons les différents modèles, et nous montrons que MDFAM peut atteindre des niveaux de performance similaires à ceux offert par IFAM, tout en étant plus facile à utiliser et à implémenter. / Given an airline schedule and demand forecasts, the Fleet Assignment Problem consists in determining how to assign aircraft types to flight legs in the best possible way. This assignment has a major impact on the profit of an airline, since it determines the quantities of seats available over the itineraries of the flight network, along with the associated operating cost. Decades of research on this problem have improved the formulations to be more and more realistic. This thesis extends the ongoing work, considering the problem of doing Fleet Assignment taking demand volatility into account. We first propose a study involving the two models of the literature that are the most widely used by the industry, FAM and IFAM. We show that FAM can be seen as a Lagrangian Relaxation of IFAM, with particular Lagrangian multipliers. We implement this relaxation, and we apply known results to extend it in a column generation based on a Dantzig-Wolfe decomposition of IFAM. We then study the effects of forecasts inaccuracy over the performance of IFAM, and we present a novel approach for modeling the Fleet Assignment Problem. Our model, Market Driven Fleet Assignment Model (MDFAM), makes the itinerary demands part of the decision variables. We propose to constraint these variables rather than consider them as a fixed input of the problem, and we call the resulting constraints Market Constraints. We illustrate the flexibility of this approach through various examples, and we provide a series of experiments in order to determine which Market Constraints give the best results. We compare the different models, and we show that MDFAM can reach a performance which is similar to IFAM's, while being easier to use and to implement.

Étant donné un processus physique linéaire dont nous connaissons les équations d'évolution nous pouvons décrire son évolution par un certain nombre d'équations différentielles linéaires. Cette forme mathématique est souvent inexploitable, c'est pourquoi l'on préfère mettre le système sous forme d'équations d'états ou de fonction de transfert ; si le système est à commande échantillonnée on adopte une formulation matricielle dans l'espace d'état. L'une ou l'autre de ces formulations sont équivalentes et le choix ne dépend que des conclusions qui doivent être tirées sur l'évolution du système soumis à une certaine commande. Tout système, quelles que soient ses performances, est inutilisable s'il est instable ou s'il ne peut pas être stabilisé par adjonction d'un correcteur d'où l'importance primordiale d'une étude de stabilité. 11 existe un très grand nombre de méthodes d'étude de la stabilité des systèmes linéaires ; citons pour mémoire la méthode de Routh-hurwitz, les critères de Bode et de Nyquist ... Ces méthodes conviennent parfaitement pour des systèmes d'ordre peu élevé mais deviennent inexploitables, sans calculateur, pour des systèmes plus complexes. Le but de l'étude qui va suivre est de choisir un critère de stabilité s'adaptant au calcul numérique à partir duquel nous élaborerons divers programmes permettant de conclure sur la stabilité des systèmes (jusqu'à l'ordre 14) quelle que soit leur formulation ; rappelons qu'un système peut se mettre sous forme d'équations d'état, de fonction de transfert, d'équations différentielles.

General Stackelberg games (GSG) confront two contenders, each wanting to optimize their rewards. One of the players, referred to as the leader, can commit to a given action or strategy first, and the other player, referred to as the follower, then responds by selecting an action or strategy of his own. The objective of the game is for the leader to commit to a reward-maximizing strategy, anticipating that the follower will best respond.Finding an optimal mixed strategy for the leader in a GSG is NP-hard when the leader faces one out of a group of several followers and polynomial when there exists a single follower. Additionally, GSGs in which the strategies of the leader consist in covering a subset of at most $m$ targets and the strategies of the followers consist in attacking some target, are called Stackelberg security games (SSG) and involve an exponential number of pure strategies for the leader.The goal of this thesis is to provide efficient algorithms to solve GSGs and SSGs. These algorithms must not only be able to produce optimal solutions quickly, but also be able to solve real life, and thus large scale, problems efficiently. To that end, the main contributions of this thesis are divided into three parts:First, a comparative study of existing mixed integer linear programming (MILP) formulations is carried out for GSGs, where the formulations are ranked according to the tightness of their linear programming (LP) relaxations. A formal theoretical link is established between GSG and SSG formulations through projections of variables and this link is exploited to extend the comparative study to SSG formulations. A new strong SSG MILP formulation is developed whose LP relaxation is shown to be the tightest among SSG formulations. When restricted to a single attacker type, the new SSG formulation is ideal, i.e. the constraints of its LP relaxation coincide with its convex hull of feasible solutions. Computational experiments show that the tightest formulations in each setting are the fastest. Notably, the new SSG formulation proposed is competitive with respect to solution time, and due to the tightness of its LP relaxation, it is better suited to tackle large instances than competing formulations.Second, the bottleneck encountered when solving the formulations studied in the first part of the thesis is addressed: The tightest formulations in each setting have heavy LP relaxations which can be time-consuming to solve and thus limit the effectiveness of the formulations to tackle instances. To address this issue, in both the general and the security case, Benders cuts from the LP relaxation of the tightest MILP formulations are embedded into a Cut and Branch scheme on a sparse equivalent formulation in each setting. By combining the tightness of the bound provided by the strong formulations with the resolution speed of the formulations, the proposed algorithm efficiently solves large GSG and SSG instances which were out of the scope of previous methods.Third, a special type of SSG, defined on a network, is studied, where the leader has to commit to two coverage distributions, one over the edges of the network and one over the targets, which are contained inside the nodes. A particular case of this SSG is used to tackle a real life border patrol problem proposed by the Carabineros de Chile in which the use of their limited security resources is optimized while taking into account both global and local planning considerations. A methodology is provided to adequately generate the game's parameters. Computational experiments show the good performance of the approach and a software application developed for Carabineros to schedule their border resources is described. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Les jeux de policiers et voleurs sont étudiés depuis une trentaine d’années en informatique et en mathématiques. Comme dans les jeux de poursuite en général, des poursuivants (les policiers) cherchent à capturer des évadés (les voleurs), cependant ici les joueurs agissent tour à tour et sont contraints de se déplacer sur une structure discrète. On suppose toujours que les joueurs connaissent les positions exactes de leurs opposants, autrement dit le jeu se déroule à information parfaite. La première définition d’un jeu de policiers-voleurs remonte à celle de Nowakowski et Winkler [39] et, indépendamment, Quilliot [46]. Cette première définition présente un jeu opposant un seul policier et un seul voleur avec des contraintes sur leurs vitesses de déplacement. Des extensions furent graduellement proposées telles que l’ajout de policiers et l’augmentation des vitesses de mouvement. En 2014, Bonato et MacGillivray [6] proposèrent une généralisation des jeux de policiers-voleurs pour permettre l’étude de ceux-ci dans leur globalité. Cependant, leur modèle ne couvre aucunement les jeux possédant des composantes stochastiques tels que ceux dans lesquels les voleurs peuvent bouger de manière aléatoire. Dans ce mémoire est donc présenté un nouveau modèle incluant des aspects stochastiques. En second lieu, on présente dans ce mémoire une application concrète de l’utilisation de ces jeux sous la forme d’une méthode de résolution d’un problème provenant de la théorie de la recherche. Alors que les jeux de policiers et voleurs utilisent l’hypothèse de l’information parfaite, les problèmes de recherches ne peuvent faire cette supposition. Il appert cependant que le jeu de policiers et voleurs peut être analysé comme une relaxation de contraintes d’un problème de recherche. Ce nouvel angle de vue est exploité pour la conception d’une borne supérieure sur la fonction objectif d’un problème de recherche pouvant être mise à contribution dans une méthode dite de branch and bound. / Cops and robbers games have been studied for the last thirty years in computer science and mathematics. As in general pursuit evasion games, pursuers (cops) seek to capture evaders (robbers), however here the players move in turn and are constrained to move on a discrete structure. It is always assumed that players know the exact location of their adversary, in other words the game is played with perfect information. The first definition of a cops and robbers game dates back to Nowakowski and Winkler [39] and, independantly, Quilliot [46]. This first definition presents a game opposing a single cop against a lone robber, both with constraints on their speed. Extensions were gradually formulated such as increasing the number of cops and the speed of the players. In 2014, Bonato and MacGillivray [6] presented a general characterization of cops and robbers games in order for them to be globally studied. However, their model does not take into account stochastic events that may occur such as the robbers moving in a random fashion. In this thesis, a novel model that includes stochastic elements is presented. Furthermore, we present in this thesis a concrete application of cops and robbers games in the form of a method of resolution of a problem from search theory. Although cops and robbers games assume perfect information, this hypothesis cannot be maintained in search problems. It appears however that cops and robbers games can be viewed as constraint relaxations of search problems. This point of view is made use of in the conception of an upper bound on the objective function of a search problem that is a applied in a branch and bound method.