Le secteur des semi-conducteurs a connu un développement considérable ces dernières décennies, du fait des nouvelles applications de la microélectronique dans l'industrie. Le processus de fabrication est réputé pour sa complexité. L'un des ateliers les plus critiques de la production, l'atelier de photolithographie, est régi par un ensemble conséquent de contraintes de production. La multiplicité des ressources utilisées, le nombre important de produits traités, en font une zone importante à optimiser. Les objectifs de la thèse ont été de modéliser cet atelier sous la forme d'un problème d'ordonnancement sur machines parallèles et d'optimiser plusieurs critères jugés pertinents pour évaluer la qualité des solutions. Des résultats en termes de complexité, et d'algorithmes de résolution, ont permis une application industrielle, dans la mesure où un logiciel d'optimisation destiné à l'ordonnancement des lots en photolithographie a été développé. / Semiconductor manufacturing has grown considerably in recent decades, due to new industrial applications of microelectronic devices. The related manufacturing process is known to be complex. A bottleneck process step, the photolithography workshop, gathers various types of constraints, related to the number of auxiliary resources and the tools characteristics. The aims of the thesis were to model this workstation as a parallel machine scheduling problem and to optimize various criteria, determined by industrial needs. Some complexity results are provided and optimization algorithms led to an industrial application, i.e. a software providing optimized schedules in a specific fab.

Campylobacter est responsable de la zoonose bactérienne d’origine alimentaire la plus fréquemment reportée en Europe. Cette bactérie étant ubiquitaire, les sources et voies d’infection de l’Homme sont nombreuses. Cependant, afin de diminuer l’incidence de la maladie, il est nécessaire d’identifier les principaux réservoirs impliqués dans les infections humaines. Pour cela, nous avons dans un premier temps investigué la présence de Campylobacter dans trois réservoirs animaux (volaille, bovin, animaux de compagnie), ainsi que la diversité génétique des isolats de C. jejuni, en comparaison à celle d’isolats cliniques, à l’aide des techniques MLST (Multilocus sequence typing) et CGF (Comparative Genomic Fingerprinting). Afin d’identifier l’origine des campylobactérioses avec précision et de compenser notamment les limites techniques de la MLST, 15 marqueurs génétiques ont été sélectionnés comme marqueurs potentiellement indicateurs de l’hôte, après analyse de plus de 800 génomes de C. jejuni. Par la suite, la capacité de la MLST, la CGF40 et des 15 marqueurs à identifier l’origine des campylobactérioses a été étudiée. Ainsi, les 15 marqueurs se sont révélés être particulièrement performants pour l’attribution de sources des campylobactérioses, suivis ensuite par la MLST, tandis que la CGF40 est apparue comme étant peu adaptée. A partir des données MLST et des 15 marqueurs génétiques, une implication majoritaire des volailles et des bovins a été mis en évidence en France, tandis que les animaux de compagnie et l’environnement (comprenant eau et oiseaux sauvages) étaient faiblement impliqués. Ceci permet ainsi de renforcer les efforts de recherche relatifs aux moyens de lutte contre Campylobacter menés dans ces réservoirs. Ce travail a également permis de mettre en évidence de potentielles spécificités nationales dans la dynamique de transmission de C. jejuni à l’Homme. / Campylobacter is the causal agent of the main bacterial foodborne gastroenteritis in Europe. Since Campylobacter is frequently found in animal reservoirs, sources of human infection and transmission routes are various. However, to decrease the human burden of campylobacteriosis, it is essential to quantify the relative importance of the several reservoirs in human infections. For this purpose, we assessed the contamination of chicken, cattle and pets by Campylobacter spp., and further characterized C. jejuni isolates using MLST (Multilocus Sequence Typing) and CGF (Comparative Genomic Fingerprinting) in comparison with French clinical isolates. Then, in order to identify the most likely origin of campylobacteriosis cases in France and overcome MLST limitations in source attribution, about 800 C. jejuni genomes were analyzed which resulted in the identification of 15 genes as promising host segregating markers for source attribution. Subsequently, we assessed the ability of MLST, CGF40 and the 15 host-segregating markers to identify the most likely origin of campylobacteriosis. The 15 host-segregating markers were the most powerful in source attribution, followed by MLST, while CGF40 appeared to be not suitable for source attribution in our study. Based on MLST and the 15 markers, assignments of clinical cases emphasize the significant implication of chicken and ruminant in human infection by Campylobacter, while pets and the environment (including water and wild birds) were slightly involved, reinforcing the interest to focus control strategies on livestock. Finally this work highlights potential national variations in the transmission dynamics of C. jejuni to human.

La structure de projet se retrouve dans de nombreux contextes de l'industrie et des services. Il s'agit de réaliser un ensemble d'activités pouvant être connectées par des liens logiques de séquence (antériorité), en faisant appel à des ressources disponibles en quantité limitée. L'objectif est la minimisation d'un critère généralement lié à la durée ou au coût du projet. La plupart des problèmes d'ordonnancement de projet dans la littérature considèrent une unité de temps commune pour la détermination des dates d'exécution des activités et pour l'évaluation instantanée du respect des capacités des ressources qu'elles utilisent. Or, s'il est souvent nécessaire en pratique d'obtenir un calendrier détaillé des plages d'exécution des activités, l'utilisation des ressources peut être évaluée sur un horizon plus agrégé, comme par exemple les quarts de travail des employés. Dans cette thèse, un nouveau modèle intégrant ces deux échelles de temps est présenté afin de définir le problème d'ordonnancement de projet avec agrégation périodique des contraintes de ressources (PARCPSP). Ce problème est étudié du point de vue de la théorie de la complexité et des propriétés structurelles sont établies, mettant notamment en évidence des différences majeures avec le problème classique d'ordonnancement de projet sous contraintes de ressources (RCPSP). De ces propriétés sont dérivées des formulations exactes basées sur la programmation linéaire en nombres entiers, comparées en termes de qualité de la relaxation linéaire. Par ailleurs, plusieurs heuristiques, telles que des algorithmes de liste, ou une méthode approchée basée sur une résolution itérative qui exploite différentes échelles de temps, sont proposées. Les résultats expérimentaux montrent l'intérêt de ces différentes méthodes et illustrent la difficulté du problème. / The project structure arises in many fields of industry and services. It consists in performing a set of activities that may be linked by precedence relations, and use resources whose capacity is limited. The objective is to minimize a criterion usually linked to the duration or the cost of the project. Most of project scheduling problems in the literature assume that the same time scale should be used to determine activity start and completion dates and check resource constraints at each time. However, although it is often required in practice to build a precise schedule specifying the execution range of each activity, the resource usage can be evaluated on an aggregated basis, like worker shifts. In this thesis, a new model that enables the integration of these two time scales is presented in order to define the periodically aggregated resource-constrained project scheduling problem (PARCPSP). This problem is studied within the framework of complexity theory and several structural properties are established, highlighting major differences with the standard resource-constrained project scheduling problem (RCPSP). These properties allow deriving exact formulations based on integer linear programming, whose linear relaxations are compared. Moreover, several heuristics, such as schedule generations schemes, or an approached method based on a multi time scale iterative process, are proposed. Experimental results show the interest of these different methods and point out the intractability of the problem.

Le problème de tournées de véhicules (Vehicle routing problem - VRP), introduit il y a plus de 60 ans, demeure au cœur des systèmes de transport. Après des décennies de développement, le VRP, par son ensemble très riche de variantes, représente l'un des problèmes les plus étudiés dans la littérature. Pourtant, en raison du manque de données, deux hypothèses importantes font que le VRP ne s'adapte pas efficacement au trafic et à la congestion, deux éléments importants pour modéliser de façon réelle des problèmes pratiques. Une première hypothèse considère que la vitesse de déplacement est constante dans le temps. La seconde, considère que chaque paire de nœuds (clients) n'est reliée que par un arc, ignorant le réseau routier implicite (sous-jacent). La congestion de la circulation est l'un des plus grands défis des systèmes de transport. Ces systèmes étant directement affectés par la congestion, l'ensemble de la chaîne d'approvisionnement doit s'adapter à ce facteur, ce qui n'est pas simple. La croissance continue du fret au cours des dernières années aggrave encore la situation et une attention renouvelée à la mobilité, à l'environnement et à la logistique urbaine a mis en lumière ces questions. Récemment, les avancées technologiques en communication et en acquisition de données en temps réel ont permis de collecter plusieurs informations sur les véhicules telles que leur localisation, leur accélération, leur vitesse, leur décélération, etc. Ainsi, nous pouvons remettre en question la façon dont nous définissons, modélisons et résolvons les problèmes de transport. Ceci nous permet de surmonter les deux hypothèses mentionnées en intégrant non seulement les informations relatives à la congestion, mais aussi en considérant l'ensemble du réseau routier. Dans cette thèse nous considérons l'ensemble du réseau routier sous-jacent, ce qui signifie que nous avons les nœuds clients mais également tous les nœuds intermédiaires qui constituent ce réseau. Ensuite, nous modélisons le temps de trajet de chaque route individuellement au cours de la journée. En divisant une journée en petits intervalles, jusqu'à une précision de l'ordre de la seconde, nous prenons en considération des informations précises sur le trafic. Il en résulte un nouveau problème appelé le problème de tournées de véhicules à plus court chemin avec dépendance du temps (Time-dependant shortest path vehicle routing problem - TD-SPVRP), dans lequel nous combinons le problème du plus court chemin avec dépendance du temps et le VRP avec dépendance du temps, créant ainsi un problème plus général et très complexe. Le TD-SPVRP est plus proche des conditions réelles et il constitue le sujet du chapitre 2 où nous le formulons comme un modèle de programmation linéaire en nombres entiers mixtes et concevons une heuristique rapide et efficace pour le résoudre. Nous testons le modèle ainsi que l'heuristique sur des instances générées à partir de données réelles de circulation sur le réseau routier de la ville de Québec, Canada. Les résultats montrent que l'heuristique fournit des solutions de haute qualité avec un écart moyen de 5,66% par rapport aux bornes inférieures déterminées par le modèle. Cependant, le modèle mathématique ne parvient pas à trouver aucune solution pour les instances de données réelles. Pour pouvoir résoudre ce problème complexe, une grande attention a été portée à la performance de l'implantation des algorithmes proposés afin d'améliorer leur rapidité en termes de temps d'exécution. Le problème reste très compliqué, surtout lorsque nous considérons une grande partie du réseau routier sous-jacent avec des données de trafic très précises. Pour cela, nous avons utilisé différentes techniques pour optimiser l'effort de calcul afin de résoudre le problème en évaluant l'impact engendré sur la précision tout en évitant la perte de précieuses informations. Nous avons développé deux types d'agrégation de données couvrant deux niveaux d'information différents. Premièrement, nous avons manipulé la structure du réseau en réduisant sa taille, et deuxièmement en contrôlant le niveau d'agrégation temporel pour générer les données de trafic et pour déterminer la vitesse d'un véhicule à tout moment. Pour la structure du réseau, nous avons utilisé différentes techniques de réduction de graphe pour en réduire la taille. Nous avons étudié la valeur et le compromis de l'information spatiale. Les solutions générées en utilisant le graphe réduit sont analysées dans le Chapitre 3 pour évaluer la qualité et la perte d'information dû à la réduction. Cette analyse démontre également que la transformation classique du TD-SPVRP en un problème de tournées dépendant du temps (Time-dependant VRP - TD-VRP) équivalent résulte en un graphe plus grand qui nécessite un temps de traitement important ce qui a un impact sur la qualité de la solution. Notre développement montre que la résolution du TD-SPVRP nécessite en moyenne 1445 secondes tandis que la résolution du TD-VRP associé nécessite 41 181 secondes. Garder un haut niveau de précision et réussir à réduire la taille du graphe est possible. En particulier, deux procédures de réduction ont été développées, la réduction des nœuds et la réduction des arcs parallèles. Les deux techniques réduisent la taille du graphe. La réduction des nœuds conduit à une amélioration de 1,11%, la réduction des arcs parallèles donne un écart de 2,57% signifiant la présence d'une distorsion dans le graphe réduit. En ce qui concerne les informations sur le trafic, nous avons analysé les compromis entre une grande quantité de données très précises et un plus petit volume de données agrégées avec une perte potentielle d'information. Ceci est fait en analysant la précision des données agrégées sous différents modèles de détermination des temps de parcours. Ces approches sont présentées dans le Chapitre 4. Au niveau de la prévision des temps de parcours, il est important que chaque segment routier ait des observations de vitesse pour chaque intervalle de temps considéré, ce que nous appelons le niveau de couverture du réseau. Notre analyse indique qu'une couverture complète du réseau routier à tout moment de la journée est nécessaire pour atteindre un niveau de précision élevé. Le recours à une agrégation élevée (de grands intervalles de temps) permet de réduire la taille du problème et d'obtenir une meilleure couverture des données, mais au prix d'une perte d'information. Les modèles analysés, LTM (link travel mode) et FSM (flow speed model), partagent les mêmes performances lorsqu'on utilise un grand intervalle de temps (120, 300 et 600 secondes), donc un niveau d'agrégation plus élevé, avec un écart moyen absolu de 5,5% par rapport aux temps de parcours observés. Cependant, avec une courte période (1, 10, 30 et 60 secondes), FSM fonctionne mieux que LTM. Pour un intervalle d'une seconde, FSM donne un écart absolu moyen de 6,70%, tandis que LTM fournit un écart de 11,17%. Ce chapitre détermine ainsi sous quelles conditions les modèles d'estimation de temps de parcours fonctionnent bien et procurent des estimations fidèles des temps de parcours réalisés. Cette thèse est structurée de la manière suivante. À la suite d'une introduction générale dans laquelle nous présentons le cadre conceptuel de la thèse et son organisation, le Chapitre 1 présente une revue de la littérature pour les deux problèmes fondamentaux étudiés, le problème de plus court chemin (Shortest path problem - SPP) et le VRP et leurs variantes développées au cours des années. Le Chapitre 2 introduit une nouvelle variante du VRP, le TD-SPVRP. Le Chapitre 3 présente les différentes techniques développées pour réduire la taille du réseau en manipulant les informations spatiales du réseau routier. L'impact de ces réductions est évalué et analysé sur des instances réelles en utilisant plusieurs heuristiques. Le Chapitre 4 traite l'impact de l'agrégation des données temporelle et des modèles d'évaluation des temps de parcours. Le dernier chapitre constitue une conclusion et ouvre des perspectives de recherche relatives à nos travaux. / The vehicle routing problem (VRP), introduced more than 60 years ago, is at the core of transportation systems. With decades of development, the VRP is one of the most studied problems in the literature, with a very rich set of variants. Yet, primarily due to the lack of data, two critical assumptions make the VRP fail to adapt effectively to traffic and congestion. The first assumption considers that the travel speed is constant over time ; the second, that each pair of customers is connected by an arc, ignoring the underlying street network. Traffic congestion is one of the biggest challenges in transportation systems. As traffic directly affects transportation activities, the whole supply chain needs to adjust to this factor. The continuous growth of freight in recent years worsens the situation, and a renewed focus on mobility, environment, and city logistics has shed light on these issues. Recently, advances in communications and real-time data acquisition technologies have made it possible to collect vehicle data such as their location, acceleration, driving speed, deceleration, etc. With the availability of this data, one can question the way we define, model, and solve transportation problems. This allows us to overcome the two issues indicated before and integrate congestion information and the whole underlying street network. We start by considering the whole underlying street network, which means we have customer nodes and intermediate nodes that constitute the street network. Then, we model the travel time of each street during the day. By dividing the day into small intervals, up to a precision of a second, we consider precise traffic information. This results in a new problem called the time-dependent shortest path vehicle routing problem (TD-SPVRP), in which we combine the time-dependent shortest path problem (TD-SPP) and the time-dependent VRP (TD-VRP), creating a more general and very challenging problem. The TD-SPVRP is closer to what can be found in real-world conditions, and it constitutes the topic of Chapter 2, where we formulate it as a mixed-integer linear programming model and design a fast and efficient heuristic algorithm to solve this problem. We test it on instances generated from actual traffic data from the road network in Québec City, Canada. Results show that the heuristic provides high-quality solutions with an average gap of only 5.66%, while the mathematical model fails to find a solution for any real instance. To solve the challenging problem, we emphasize the importance of a high-performance implementation to improve the speed and the execution time of the algorithms. Still, the problem is huge especially when we work on a large area of the underlying street network alongside very precise traffic data. To this end, we use different techniques to optimize the computational effort to solve the problem while assessing the impact on the precision to avoid the loss of valuable information. Two types of data aggregation are developed, covering two different levels of information. First, we manipulated the structure of the network by reducing its size, and second by controlling the time aggregation level to generate the traffic data, thus the data used to determine the speed of a vehicle at any time. For the network structure, we used different reduction techniques of the road graph to reduce its size. We studied the value and the trade-off of spatial information. Solutions generated using the reduced graph are analyzed in Chapter 3 to evaluate the quality and the loss of information from the reduction. We show that the transformation of the TD-SPVRP into an equivalent TD-VRP results in a large graph that requires significant preprocessing time, which impacts the solution quality. Our development shows that solving the TD-SPVRP is about 40 times faster than solving the related TD-VRP. Keeping a high level of precision and successfully reducing the size of the graph is possible. In particular, we develop two reduction procedures, node reduction and parallel arc reduction. Both techniques reduce the size of the graph, with different results. While the node reduction leads to improved reduction in the gap of 1.11%, the parallel arc reduction gives a gap of 2.57% indicating a distortion in the reduced graph. We analyzed the compromises regarding the traffic information, between a massive amount of very precise data or a smaller volume of aggregated data with some potential information loss. This is done while analyzing the precision of the aggregated data under different travel time models, and these developments appear in Chapter 4. Our analysis indicates that a full coverage of the street network at any time of the day is required to achieve a high level of coverage. Using high aggregation will result in a smaller problem with better data coverage but at the cost of a loss of information. We analyzed two travel time estimation models, the link travel model (LTM) and the flow speed model (FSM). They both shared the same performance when working with large intervals of time (120, 300, and 600 seconds), thus a higher level of aggregation, with an absolute average gap of 5.5% to the observed route travel time. With short periods (1, 10, 30, and 60 seconds), FSM performs better than LTM. For 1 second interval, FSM gives an average absolute gap of 6.70%, while LTM provides a gap of 11.17%. This thesis is structured as follows. After a general introduction in which we present the conceptual framework of the thesis and its organization, Chapter 1 presents the literature review for the two main problems of our development, the shortest path problem (SPP) and the VRP, and their time-dependent variants developed over the years. Chapter 2 introduces a new VRP variant, the TD-SPVRP. Chapter 3 presents the different techniques developed to reduce the size of the network by manipulating spatial information of the road network. The impact of these reductions is evaluated and analyzed on real data instances using multiple heuristics. Chapter 4 covers the impact of time aggregation data and travel time models when computing travel times on the precision of their estimations against observed travel times. The conclusion follows in the last chapter and presents some research perspectives for our works.

Ce mémoire traite un problème de transport de personnes dans un contexte hospitalier, connu sous le nom du problème de brancardier. L'objectif est de construire des itinéraires qui répondent aux demandes de transports émergentes entre les différents services d'un grand centre hospitalier en temps réel, en minimisant le temps total de retard pondéré. Ce problème est traité comme un problème de cueillettes et de livraisons multitrajets qui considère des fenêtres de temps souples, une flotte hétérogène de véhicules et des contraintes liées à la capacité. Les requêtes de transport de patients sont imprévisibles et dynamiques. Elles sont révélées lorsqu'un patient nécessite un service de transport pour des raisons médicales. Ce travail présente trois approches de résolution du problème de transport de patients, à noter une première approche statique, une deuxième dynamique et une troisième stochastique. De plus, une stratégie d'attente et deux stratégies de relocalisation de véhicules ont été développées. Les approches sont évaluées sur des données réelles d'un grand hôpital, le Policlinico Sant'Orsola-Malpighi de la mairie de Bologne en Italie. / The following study presents the problem of transportation of patients in the medical field. Demand in this context is unpredictable and revealed dynamically. The objective is to develop an algorithm capable of constructing efficient and effective routes in real time while minimizing the total weighted lateness. This problem is considered as a multitrip pickup and delivery problem with soft time windows, heterogeneous fleet, and capacity constraints. This work presents a detailed description of the discussed problem and proposes three approaches to solve it: a static approach, a dynamic approach and a stochastic one. Moreover, it presents a waiting and two relocalisation strategies. These approaches have all been tested and evaluated using real data collected from the medical campus of Policlinico Sant'Orsola-Malpighi of the town Hall of Bologne in Italy.

La thèse étudie la prise en compte du principe décimal de la numération lors de l'introduction des nombres supérieurs à mille, en troisième année d'école primaire. En nous appuyant sur les cadres de la théorie anthropologique du didactique (TAD) et de la théorie des situations didactiques (TSD), nous avons d'abord construit une organisation mathématique de référence et une situation fondamentale de la numération, pour étudier les différentes étapes de la transposition didactique. Un premier résultat est le constat d'un manque de prise en compte du principe décimal de la numération de position dans les manuels et programmes actuels ainsi que dans les pratiques. Notre étude se poursuit par la détermination de conditions que devrait vérifier une ressource qui aiderait les enseignants à améliorer la prise en compte de ce principe. Pour cela nous utilisons la méthodologie d'ingénierie didactique pour le développement d'une ressource : élaborer une première version, analyser son utilisation par des enseignants, l'adapter en une seconde version, etc. (cycles conception-usage). Les résultats de l'étude concernent la pertinence des situations (mises en scène de la situation fondamentale) et de leur description aux enseignants. Ils permettent d'envisager des modifications possibles pour une ressource plus efficace. L'étude permet aussi de préciser les difficultés des élèves et de recueillir des informations sur les pratiques ordinaires des enseignants.

Les travaux de cette thèse concernent la conception et l’optimisation de lignes de transfert reconfigurables. L’objectif principal est de concevoir une ligne d’usinage à moindre coût tout en respectant les contraintes techniques, technologiques et économiques du problème. Le problème d’optimisation correspondant est un problème d’équilibrage de lignes d’usinage sujet à des contraintes spécifiques. Il consiste à affecter les opérations aux stations de travail en minimisant les coûts d’installation. En plus des contraintes habituelles de ce type de problème, à savoir, les contraintes de précédence, d’inclusion et d’exclusion, nous avons dû considérer des contraintes d’accessibilité. De plus, la spécificité principale des lignes reconfigurables par rapport aux lignes de transfert dédiées, vient de la réalisation en série des opérations. Celle-ci rend souvent nécessaire la mise en place de stations équipées de plusieurs centres d’usinage travaillant en parallèle pour obtenir les volumes de production souhaités. Enfin, l’utilisation d’une tête d’usinage mono-broche induit la prise en compte de temps inter-opératoire de déplacements et de changement d’outils qui dépendent de la séquence d’opérations. Dans un premier temps, nous avons proposé une modélisation mathématique du problème à l’aide d’un programme linéaire en nombres mixtes. Nous avons aussi développé des méthodes de calcul de bornes inférieures ainsi qu’une procédure de prétraitement. Cependant, les contraintes additionnelles rendent la résolution du problème d’équilibrage plus difficile que dans le cas des lignes dédiées, et l’approche proposée ne permet généralement pas de résoudre des instances de taille industrielle. Pour répondre à ce besoin, nous avons donc développé plusieurs méthodes de résolution approchées du problème en nous inspirant de métaheuristiques efficaces sur des problèmes d’optimisation combinatoire. / This work concerns the design and the optimization of reconfigurable transfer lines. The principle objective is to design a machining line with less cost while respecting the technological and economic constraints of the problem. The corresponding optimization problem is a transfer lines balancing problem subject to specific constraints. It consists to affect operations to workstations minimizing the installations cost. In addition to the habitual constraints of the transfer balancing problem, i.e. precedence, inclusion and exclusion constraints, we consider accessibility constraints. In addition, the principal specificity of reconfigurable lines compared to the dedicated transfer lines, comes from the sequential execution of operations. This often makes it necessary to set up stations with several machining centers working in parallel to achieve desired production volumes. Finally, the utilization of mono-spindle head machining center induces the inclusion of setup times between operations. This setup time is due to the time of displacement and change of tools which it depends of the operational sequence. We proposed firstly a mathematical formalization of the problem using a mixed integer program. We developed also several methods to calculate lower bounds and a pretreatment procedure. However, the additional constraints make the resolution of the considered balancing problem very difficult and the proposed approach generally does not solve instances of industrial size. To meet this need, we have developed several approximate resolution methods of the problem taking inspiration from effective Metaheuristics on combinatorial optimization problems.

Le sujet de cette thèse est l'étude des progressions arithmétiques dans les nombres entiers. Plus précisément, nous nous intéressons à borner inférieurement v(N), la taille du plus grand sous-ensemble des nombres entiers de 1 à N qui ne contient pas de progressions arithmétiques de 3 termes. Nous allons donc construire de grands sous-ensembles de nombres entiers qui ne contiennent pas de telles progressions, ce qui nous donne une borne inférieure sur v(N). Nous allons d'abord étudier les preuves de toutes les bornes inférieures obtenues jusqu'à présent, pour ensuite donner une autre preuve de la meilleure borne. Nous allons considérer les points à coordonnés entières dans un anneau à d dimensions, et compter le nombre de progressions arithmétiques qu'il contient. Pour obtenir des bornes sur ces quantités, nous allons étudier les méthodes pour compter le nombre de points de réseau dans des sphères à plusieurs dimensions, ce qui est le sujet de la dernière section. / The subject of this thesis is the study of arithmetic progressions in the integers. Precisely, we are interested in the size v(N) of the largest subset of the integers from 1 to N that contains no 3 term arithmetic progressions. Therefore, we will construct a large subset of integers with no such progressions, thus giving us a lower bound on v(N). We will begin by looking at the proofs of all the significant lower bounds obtained on v(N), then we will show another proof of the best lower bound known today. For the proof, we will consider points on a large d-dimensional annulus, and count the number of integer points inside that annulus and the number of arithmetic progressions it contains. To obtain bounds on those quantities, it will be interesting to look at the theory behind counting lattice points in high dimensional spheres, which is the subject of the last section.

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques. / Integer linear programming is a robust and efficient approach to solve large-scale instances of combinatorial problems. However, problems constantly gain in complexity and sometimes impose strong constraints on computation times. We must then develop specialised methods to compute heuristic primal solutions to the problem and derive lower bounds on the optimal value, and thus prove the quality of our primal solutions. We propose to guide a reformulation approach for mixed integer programs with Lagrangian relaxations. After the identification of a strong relaxation, a mechanical process leads to a second integer formulation. This reformulation is equivalent to the initial one, but its linear relaxation is equivalent to the strong Lagrangian dual. We will show that the reformulation approach unifies and generalises prior formulations and lower bounding approaches, and that it exposes a simple mechanism to reduce the size of reformulations in return for weaker bounds. Nevertheless, our reformulations are large. We address this issue by solving their linear relaxations with specialised methods. Finally, we apply the reformulation approach to two location problems. This yields novel formulations for both problems; some are very large but, thanks to the aforementioned specialised methods, still practical.

Cette thèse concerne quelques problèmes liés à la répartition des entiers sans facteur carré dansles progressions arithmétiques. Ces problèmes s’expriment en termes de majorations du terme d’erreurassocié à cette répartition.Les premier, deuxième et quatrième chapitres sont concentrés sur l’étude statistique des termesd’erreur quand on fait varier la progression arithmétique modulo q. En particulier on obtient une formuleasymptotique pour la variance et des majorations non triviales pour les moments d’ordre supérieur. Onfait appel à plusieurs techniques de théorie analytique des nombres comme les méthodes de crible et lessommes d’exponentielles, notamment une majoration récente pour les sommes d’exponentielles courtesdue à Bourgain dans le deuxième chapitre.Dans le troisième chapitre on s’intéresse à estimer le terme d’erreur pour une progression fixée. Onaméliore un résultat de Hooley de 1975 dans deux directions différentes. On utilise ici des majorationsrécentes de sommes d’exponentielles courtes de Bourgain-Garaev et de sommes d’exponentielles torduespar la fonction de Möbius dues à Bourgain et Fouvry-Kowalski-Michel. / This thesis concerns a few problems linked with the distribution of squarefree integers in arithmeticprogressions. Such problems are usually phrased in terms of upper bounds for the error term relatedto this distribution.The first, second and fourth chapter focus on the satistical study of the error terms as the progres-sions varies modulo q. In particular we obtain an asymptotic formula for the variance and non-trivialupper bounds for the higher moments. We make use of many technics from analytic number theorysuch as sieve methods and exponential sums. In particular, in the second chapter we make use of arecent upper bound for short exponential sums by Bourgain.In the third chapter we give estimates for the error term for a fixed arithmetic progression. Weimprove on a result of Hooley from 1975 in two different directions. Here we use recent upper boundsfor short exponential sums by Bourgain-Garaev and exponential sums twisted by the Möbius functionby Bourgain et Fouvry-Kowalski-Michel.