Dans les régions semi-arides, les systèmes de production agricole dépendent fortement de l'irrigation et font face à des difficultés croissantes (épuisement des ressources naturelles, forte volatilité des prix du marché, hausse des coûts de l'énergie, incertitude sur les changements climatiques). Modéliser ces systèmes agricoles et la façon dont ils s'adaptent est important pour les décideurs politiques afin de mieux évaluer leur flexibilité et leur résilience. Pour comprendre la capacité des systèmes agricoles à s'adapter, il est essentiel de considérer l'ensemble du processus de décision : des décisions sur le long-terme à l'échelle de l'exploitation aux décisions de court-terme à l'échelle de la parcelle. Pour ce faire, cette thèse conçoit un système de production agricole adaptable dans un contexte de diminution de l'eau et de changement climatique. Elle fournit une méthodologie guidant l'acquisition de données, leur analyse et la conception de modèle. Elle présente le modèle de simulation NAMASTE représentant les décisions des agriculteurs, les interactions entre agriculteurs pour l'utilisation des ressources communes et met l'accent sur la rétroaction entre pratiques agricoles et évolution de la nappe phréatique. Le modèle a été initialement développé pour résoudre les problèmes critiques de baisse des eaux souterraines liés aux pratiques agricoles dans un bassin versant du sud-ouest de l'Inde. Sa structure, ses cadres conceptuels et ses formalismes peuvent être utilisés dans d'autres contextes agricoles. / In semi-arid regions, agricultural production systems depend greatly on irrigation and encounter increasing challenges (depletion of natural resources, high volatility in market prices, rise in energy costs, growing uncertainty about climate change). Modeling farming systems and how these systems change and adapt to these challenges is particularly interesting for policy makers to better assess their flexibility and resiliency. To understand the ability of farming systems to adapt, it is essential to consider the entire decision-making process: from long-term decisions at the farm scale to short-term decisions at the plot level. To this end, the thesis conceives a flexible and resilient agricultural production system under a context of water scarcity and climate change. It provides a step-by-step methodology that guides data acquisition and analysis and model design. It proposes a simulation model NAMASTE that simulates the farmers' decisions in different time and space scales, represents the interactions between farmers for resource uses and emphasizes the feedback and retroaction between farming practices and changes in the water table. The model was initially developed to address critical issues of groundwater depletion and farming practices in a watershed in southwestern India. Its structure, frameworks and formalisms can be used in other agricultural contexts.

Le problème de dimensionnement et planification d'agents en centre d'appels consiste à déterminer sur une période le nombre d'interlocuteurs requis afin d'atteindre la qualité de service exigée et minimiser les coûts induits. Ce sujet fait l'objet d'un intérêt croissant pour son intérêt théorique mais aussi pour l'impact applicatif qu'il peut avoir. Le but de cette thèse est d'établir des approches en contraintes en probabilités en considérant l'incertitude de la demande.Tout d'abord, la thèse présente un modèle en problème d'optimisation stochastique avec contrainte en probabilité jointe traitant la problématique complète en une étape afin d'obtenir un programme facile à résoudre. Une approche basée sur l'idée de continuité est proposée grâce à des lois de probabilité continues, une nouvelle relation entre les taux d'arrivées et les besoins théoriques et la linéarisation de contraintes. La répartition du risque global est faite pendant le processus d'optimisation, permettant une solution au coût réduit. Ces solutions résultantes respectent le niveau de risque tout en diminuant le coût par rapport à d'autres approches.De plus, le modèle en une étape est étendu pour améliorer sa représentation de la réalité. D'une part, le modèle de file d'attente est amélioré et inclus la patience limitée des clients. D'autre part, une nouvelle expression de l'incertitude est proposée pour prendre la dépendance des périodes en compte.Enfin, une nouvelle représentation de l'incertitude est considérée. L'approche distributionally robust permet de modéliser le problème sous l'hypothèse que la loi de probabilité adéquate est inconnue et fait partie d'un ensemble de lois, défini par une moyenne et une variance données. Le problème est modélisé par une contrainte en probabilité jointe. Le risque à chaque période est définie par une variable à optimiser.Un problème déterministe équivalent est proposé et des approximations linéaires permettent d'obtenir une formulation d'optimisation linéaire. / The staffing and shift-scheduling problems in call centers consist in deciding how many agents handling the calls should be assigned to work during a given period in order to reach the required Quality of Service and minimize the costs. These problems are subject to a growing interest, both for their interesting theoritical formulation and their possible applicative effects. This thesis aims at proposing chance-constrained approaches considering uncertainty on demand forecasts.First, this thesis proposes a model solving the problems in one step through a joint chance-constrained stochastic program, providing a cost-reducing solution. A continuous-based approach leading to an easily-tractable optimization program is formulated with random variables following continuous distributions, a new continuous relation between arrival rates and theoritical real agent numbers and constraint linearizations. The global risk level is dynamically shared among the periods during the optimization process, providing reduced-cost solution. The resulting solutions respect the targeted risk level while reducing the cost compared to other approaches.Moreover, this model is extended so that it provides a better representation of real situations. First, the queuing system model is improved and consider the limited patience of customers. Second, another formulation of uncertainty is proposed so that the period correlation is considered.Finally, another uncertainty representation is proposed. The distributionally robust approach provides a formulation while assuming that the correct probability distribution is unknown and belongs to a set of possible distributions defined by given mean and variance. The problem is formulated with a joint chance constraint. The risk at each period is a decision variable to be optimized. A deterministic equivalent problem is proposed. An easily-tractable mixed-integer linear formulation is obtained through piecewise linearizations.

Les travaux présentés dans ce manuscrit portent sur la conception des lignes de désassemblageen contexte incertain. Une ligne de désassemblage consiste en unesuccession de postes de travail où les tâches sont exécutées séquentiellement au niveau de chaque poste. La conception d'un tel système, de revalorisationdes produits en fin de vie, peut être ramenée à un problème d'optimisation combinatoire.Ce dernier cherche à obtenir une configuration permettant d'optimiser certains objectifs enrespectant des contraintes techniques, économiques et écologiques.Dans un premier temps, nous décrivons les activités principales de la revalorisation des produitsen fin de vie, en particulier le désassemblage. Puis, après présentation des travaux de la littératureportant sur la prise en compte des incertitudes des durées opératoires lors de la conception des lignesde production, nous nous focalisons sur l'étude des incertitudes des durées opératoires des tâches de désassemblage.Ainsi, nous présentons trois modélisations principales avec leurs approches de résolution.La première s'intéresse à la minimisation des arrêts de la ligne causés par les incertitudes des durées des opérationsde désassemblage. La deuxième cherche à garantir un niveau opérationnel de la ligne lié à sa cadence de fonctionnement.Le but de la troisième modélisation est l'intégration des problématiques de conception des ligneset de séquencement des tâches de désassemblage. Enfin, les performances des méthodes de résolutionproposées sont présentées en analysant les résultats d'optimisation sur un ensemble d'instances de taille industrielle. / This thesis is dedicated to the problem of disassembly line design in uncertain context. A disassembly linecan be represented as a succession of workstations where tasks are performed sequentially at each workstation.The design of such a product recovery system can be reduced to a combinatorial optimization problem which seeksa line configuration that optimizes certain objectives under technical, economical and environmental constraints.We begin by describing the principal product recovery activities especially disassembly. Then, after a literaturereview on the design of production lines under uncertainty of task processing times, we focus our study on the consideration of the disassembly task time uncertainties. Hence, we present three main models as well as the associatedsolution approaches. The first one is interested in minimizing the line stoppages caused by the task processing timeuncertainties. The second one seeks to guarantee an operational level closely related with the line speed. The goal of thethird model is to integrate the line design and sequencing problems. At last, the performances of the proposed solutionapproaches are presented by analyzing the optimization results on a set of instances of industrial size.

Cotutelle avec l'Université de Toulouse 3 - Paul Sabatier, France. Laboratoire d'accueil: Laboratoire de recherche de l'École Nationale de l'Aviation Civile (ENAC), équipe OPTIM, Toulouse, France. / Dans le contexte d'une augmentation soutenue du trafic aérien et d'une faible marge d'expansion des capacités aéroportuaires, la pression s'accroît sur les aéroports les plus fréquentés pour une utilisation optimale de leur infrastructure, telle que les pistes, reconnues comme le goulot d'étranglement des opérations aériennes. De ce besoin opérationnel est né le problème d'ordonnancement des atterrissages d'avions, consistant à trouver pour les avions se présentant à un aéroport la séquence et les heures d'atterrissage optimales par rapport à certains critères (utilisation des pistes, coût total des retards, etc) tout en respectant des contraintes opérationnelles et de sécurité. En réponse à ce besoin également, depuis les années 1990 aux États-Unis et en Europe, des outils d'aide à la décision ont été mis à la disposition des contrôleurs aériens, afin de les assister dans leur tâche d'assurer la sécurité et surtout la performance des flux d'arrivée. Un certain nombre de travaux de recherche se sont focalisés sur le cas déterministe et statique du problème d'atterrissage d'avions. Cependant, le problème plus réaliste, de nature stochastique et dynamique, a reçu une attention moindre dans la littérature. De plus, dans le cadre du projet européen de modernisation des systèmes de gestion de trafic aérien, il a été proposé d’étendre l’horizon opérationnel des outils d’aide à la décision de manière à prendre en compte les avions plus loin de l'aéroport de destination. Cette extension de l'horizon opérationnel promet une meilleure gestion des flux d'arrivées via un ordonnancement précoce plus efficient. Néanmoins, elle est inévitablement accompagnée d'une détérioration de la qualité des données d'entrée, rendant indispensable la prise en compte de leur stochasticité. L’objectif de cette thèse est l’ordonnancement des arrivées d’avions, dans le cadre d'un horizon opérationnel étendu, où les heures effectives d'arrivée des avions sont incertaines. Plus précisément, nous proposons une approche basée sur la programmation stochastique à deux étapes. En première étape, les avions sont pris en considération à 2-3 heures de leur atterrissage prévu à l'aéroport de destination. Il s'agit de les ordonnancer à un point de l'espace aérien aéroportuaire, appelé IAF (Initial Approach Fix). Les heures effectives de passage à ce point sont supposées suivre des distributions de probabilité connues. En pratique, cette incertitude peut engendrer un risque à la bonne séparation des avions nécessitant l'intervention des contrôleurs. Afin de limiter la charge de contrôle conséquente, nous introduisons des contraintes en probabilité traduisant le niveau de tolérance aux risques de sécurité à l'IAF après révélation de l'incertitude. La deuxième étape correspond au passage effectif des avions considérés à l'IAF. Comme l'incertitude est révélée, une décision de recours est prise afin d'ordonnancer les avions au seuil de piste en minimisant un critère de deuxième étape (charge de travail des contrôleurs, coût du retard, etc). La démonstration de faisabilité et une étude numérique de ce problème d'ordonnancement des arrivées d'avions en présence d'incertitude constituent la première contribution de la thèse. La modélisation de ce problème sous la forme d’un problème de programmation stochastique à deux étapes et sa résolution par décomposition de Benders constituent la deuxième contribution. Finalement, la troisième contribution étend le modèle proposé au cas opérationnel, plus réaliste où nous considérons plusieurs points d’approche initiale. / Airport operations are well known to be a bottleneck in the air traffic system, which puts more and more pressure on the world busiest airports to optimally schedule landings, in particular, and also – but to a smaller extent – departures. The Aircraft Landing Problem (ALP) has arisen from this operational need. ALP consists in finding for aircraft heading to a given airport a landing sequence and landing times so as to optimize some given criteria (optimizing runway utilization, minimizing delays, etc) while satisfying operational constraints (safety constraints mainly). As a reply to this operational need, decision support tools have been designed and put on service for air traffic controllers since the early nineties in the US as well as in Europe. A considerable number of publications dealing with ALP focus on the deterministic and static case. However, the aircraft landing problem arising in practice has a dynamic nature riddled with uncertainties. In addition, operational horizon of current decision support tools are to be extended so that aircraft are captured at larger distances from the airport to hopefully start the scheduling process earlier. Such a horizon extension affects the quality of input data which enlarges the uncertainty effect. In this thesis, we aim at scheduling aircraft arrivals under uncertainty. For that purpose, we propose an approach based on two-stage stochastic programming. In the first stage, aircraft are captured at a large distance from the destination airport. They are to be scheduled on the same initial approach fix (IAF), a reference point in the near-to-airport area where aircraft start their approach phase preparing for landing. Actual IAF arrival times are assumed to be random variables with known probability distributions. In practice, such an uncertainty may cause loss of safety separations between aircraft. In such situations, air traffic controllers are expected to intervene to ensure air traffic safety. In order to alleviate the consequent air traffic control workload, chance constraints are introduced so that the safety risks around the IAF are limited to an acceptable level once the uncertainty is revealed. The second stage corresponds to the situation where aircraft are actually close to the IAF. In this stage, the uncertainty is revealed and a recourse decision is made in order to schedule aircraft on the runway threshold so that a second-stage cost function is minimized (e.g., air traffic control workload, delay cost, etc). Our first contribution is a proof of concept of the extended aircraft arrival management under uncertainty and a computational study on optimization parameters and problem characteristics. Modeling this problem as a two-stage stochastic programming model and solving it by a Benders decomposition is our second contribution. Finally, our third contribution focuses on extending our model to the more realistic case, where aircraft in the first stage are scheduled on several IAFs.

De nos jours, atteindre un niveau élevé de satisfaction des employés à l’intérieur d’horaires efficients est une tâche importante et ardue à laquelle les compagnies font face. Dans ce travail, nous abordons une nouvelle variante du problème de création d’horaire de personnel face à une demande inconnue, en tenant compte de la satisfaction des employés via l’incertitude endogène qui découle de la combinaison des préférences des employés envers les horaires, et de ceux qu’ils reçoivent. Nous abordons ce problème dans le contexte de la création d’horaire d’employés remplaçants, un problème opérationnel de l’industrie du transport en commun qui n’a pas encore été étudié, bien qu’assez présent dans les compagnies nord-américaines. Pour faire face aux défis qu’amènent les deux sources d’incertitude, les absences des employés réguliers et des employés remplaçants, nous modélisons ce problème en un programme stochastique en nombres entiers à deux étapes avec recours mixte en nombres entiers. Les décisions de première étape consistent à trouver les journées de congé des employés remplaçants. Une fois que les absences inconnues des employés réguliers sont révélées, les décisions de deuxième étape consistent à planifier les tâches des employés remplaçants. Nous incorporons les préférences des employés remplaçants envers les journées de congé dans notre modèle pour observer à quel point la satisfaction de ces employés peut affecter leurs propres taux d’absence. Nous validons notre approche sur un an de données de la ville de Los Angeles. Notre travail est présentement en cours d’implémentation chez un fournisseur mondial de solutions logicielles pour les opérations de transport en commun. / Nowadays, reaching a high level of employee satisfaction in efficient schedules is an important and difficult task faced by companies. In this work, we tackle a new variant of the personnel scheduling problem under unknown demand by considering employee satisfaction via endogenous uncertainty depending on the combination of their preferred and received schedules. We address this problem in the context of reserve staff scheduling, an operational problem from the transit industry that has not yet been studied, although rather present in North American transit companies. To handle the challenges brought by the two uncertainty sources, regular employee and reserve employee absences, we formulate this problem as a two-stage stochastic integer program with mixed-integer recourse. The first-stage decisions consist in finding the days off of the reserve employees. After the unknown regular employee absences are revealed, the second-stage decisions are to schedule the reserve staff duties. We incorporate reserve employees’ preferences for days off into the model to examine how employee satisfaction may affect their own absence rates. We validate our approach on one year of data from the city of Los Angeles. Our work is currently being implemented in a world-leader software solutions provider for public transit operations.

Une approche classique pour traiter les problèmes d’optimisation avec incertitude à deux- et multi-étapes est d’utiliser l’analyse par scénario. Pour ce faire, l’incertitude de certaines données du problème est modélisée par vecteurs aléatoires avec des supports finis spécifiques aux étapes. Chacune de ces réalisations représente un scénario. En utilisant des scénarios, il est possible d’étudier des versions plus simples (sous-problèmes) du problème original. Comme technique de décomposition par scénario, l’algorithme de recouvrement progressif est une des méthodes les plus populaires pour résoudre les problèmes de programmation stochastique multi-étapes. Malgré la décomposition complète par scénario, l’efficacité de la méthode du recouvrement progressif est très sensible à certains aspects pratiques, tels que le choix du paramètre de pénalisation et la manipulation du terme quadratique dans la fonction objectif du lagrangien augmenté. Pour le choix du paramètre de pénalisation, nous examinons quelques-unes des méthodes populaires, et nous proposons une nouvelle stratégie adaptive qui vise à mieux suivre le processus de l’algorithme. Des expériences numériques sur des exemples de problèmes stochastiques linéaires multi-étapes suggèrent que la plupart des techniques existantes peuvent présenter une convergence prématurée à une solution sous-optimale ou converger vers la solution optimale, mais avec un taux très lent. En revanche, la nouvelle stratégie paraît robuste et efficace. Elle a convergé vers l’optimalité dans toutes nos expériences et a été la plus rapide dans la plupart des cas. Pour la question de la manipulation du terme quadratique, nous faisons une revue des techniques existantes et nous proposons l’idée de remplacer le terme quadratique par un terme linéaire. Bien que qu’il nous reste encore à tester notre méthode, nous avons l’intuition qu’elle réduira certaines difficultés numériques et théoriques de la méthode de recouvrement progressif. / In the literature of optimization problems under uncertainty a common approach of dealing with two- and multi-stage problems is to use scenario analysis. To do so, the uncertainty of some data in the problem is modeled by stage specific random vectors with finite supports. Each realization is called a scenario. By using scenarios, it is possible to study smaller versions (subproblems) of the underlying problem. As a scenario decomposition technique, the progressive hedging algorithm is one of the most popular methods in multi-stage stochastic programming problems. In spite of full decomposition over scenarios, progressive hedging efficiency is greatly sensitive to some practical aspects, such as the choice of the penalty parameter and handling the quadratic term in the augmented Lagrangian objective function. For the choice of the penalty parameter, we review some of the popular methods, and design a novel adaptive strategy that aims to better follow the algorithm process. Numerical experiments on linear multistage stochastic test problems suggest that most of the existing techniques may exhibit premature convergence to a sub-optimal solution or converge to the optimal solution, but at a very slow rate. In contrast, the new strategy appears to be robust and efficient, converging to optimality in all our experiments and being the fastest in most of them. For the question of handling the quadratic term, we review some existing techniques and we suggest to replace the quadratic term with a linear one. Although this method has yet to be tested, we have the intuition that it will reduce some numerical and theoretical difficulties of progressive hedging in linear problems.

L'objectif de cette recherche est de développer des modèles aussi bien conceptuels, analytiques et managériaux en analysant un maillon de la supply chain, à savoir la relation entre un distributeur et deux fournisseurs opérant dans un environnement incertain. Dans la première partie de la thèse, nous considérons un seul produit, plutôt haut de gamme et/ou périssable, et nous faisons l’analyse sur un horizon d’une période. Dans ce cas précis, les caractéristiques unitaires du produit sont toutes non linéaires, à savoir : le prix, le coût de production, le coût de rupture, le coût de reprise. La demande est supposée être une variable aléatoire. Dans la deuxième partie de la thèse, nous nous inspirons des pratiques de firmes internationales qui s’approvisionnent, pour une partie de leur offre, dans des pays à bas coûts. Nous développons plusieurs modèles mais dont la structure de base est similaire, à savoir : deux produits (un haut gamme acheté localement et l’autre bas de gamme acheté dans les pays à bas coûts), un horizon de trois périodes, deux fournisseurs à capacité de production limitée et un distributeur ayant des capacités de stockage limitées. Une panoplie de résultats théoriques, numériques ainsi que des insights sont présentés.Les modèles développés peuvent être utilisés comme des outils d’aide { la prise de décision dans les environnements décrits dans cette thèse / The objective of this research is to develop conceptual, analytical, and managerial models and insights by analyzing a portion of the supply chain made up of a retailer dealing with two suppliers in an uncertain environment. In the first part of this thesis, we consider a single high-end (or perishable) product, single period, variable unit price, variable unit production cost, variable unit shortage cost, variable unit salvagevalue, stochastic demand problem. In a second part of the thesis, we consider settings inspired by the case of large international companies sourcing some of their products from low cost countries. This structure is as follows: two products (one sourced locally and the other sourced abroad), a three-period, two-stages, two capacitated suppliers, and a single capacitated retailer. Both analytical and numerical results are provided. Important theoretical results and insights are developed for these types of settings. These models can be used as decision-making aid tools in such environments

Dans cette thèse, nous étudions trois types de problèmes stochastiques : les problèmes avec contraintes probabilistes, les problèmes distributionnellement robustes et les problèmes avec recours. Les difficultés des problèmes stochastiques sont essentiellement liées aux problèmes de convexité du domaine des solutions, et du calcul de l’espérance mathématique ou des probabilités qui nécessitent le calcul complexe d’intégrales multiples. A cause de ces difficultés majeures, nous avons résolu les problèmes étudiées à l’aide d’approximations efficaces.Nous avons étudié deux types de problèmes stochastiques avec des contraintes en probabilités, i.e., les problèmes linéaires avec contraintes en probabilité jointes (LLPC) et les problèmes de maximisation de probabilités (MPP). Dans les deux cas, nous avons supposé que les variables aléatoires sont normalement distribués et les vecteurs lignes des matrices aléatoires sont indépendants. Nous avons résolu LLPC, qui est un problème généralement non convexe, à l’aide de deux approximations basée sur les problèmes coniques de second ordre (SOCP). Sous certaines hypothèses faibles, les solutions optimales des deux SOCP sont respectivement les bornes inférieures et supérieures du problème du départ. En ce qui concerne MPP, nous avons étudié une variante du problème du plus court chemin stochastique contraint (SRCSP) qui consiste à maximiser la probabilité de la contrainte de ressources. Pour résoudre ce problème, nous avons proposé un algorithme de Branch and Bound pour calculer la solution optimale. Comme la relaxation linéaire n’est pas convexe, nous avons proposé une approximation convexe efficace. Nous avons par la suite testé nos algorithmes pour tous les problèmes étudiés sur des instances aléatoires. Pour LLPC, notre approche est plus performante que celles de Bonferroni et de Jaganathan. Pour MPP, nos résultats numériques montrent que notre approche est là encore plus performante que l’approximation des contraintes probabilistes individuellement.La deuxième famille de problèmes étudiés est celle relative aux problèmes distributionnellement robustes où une partie seulement de l’information sur les variables aléatoires est connue à savoir les deux premiers moments. Nous avons montré que le problème de sac à dos stochastique (SKP) est un problème semi-défini positif (SDP) après relaxation SDP des contraintes binaires. Bien que ce résultat ne puisse être étendu au cas du problème multi-sac-à-dos (MKP), nous avons proposé deux approximations qui permettent d’obtenir des bornes de bonne qualité pour la plupart des instances testées. Nos résultats numériques montrent que nos approximations sont là encore plus performantes que celles basées sur les inégalités de Bonferroni et celles plus récentes de Zymler. Ces résultats ont aussi montré la robustesse des solutions obtenues face aux fluctuations des distributions de probabilités. Nous avons aussi étudié une variante du problème du plus court chemin stochastique. Nous avons prouvé que ce problème peut se ramener au problème de plus court chemin déterministe sous certaine hypothèses. Pour résoudre ce problème, nous avons proposé une méthode de B&B où les bornes inférieures sont calculées à l’aide de la méthode du gradient projeté stochastique. Des résultats numériques ont montré l’efficacité de notre approche. Enfin, l’ensemble des méthodes que nous avons proposées dans cette thèse peuvent s’appliquer à une large famille de problèmes d’optimisation stochastique avec variables entières. / In this thesis, we studied three types of stochastic problems: chance constrained problems, distributionally robust problems as well as the simple recourse problems. For the stochastic programming problems, there are two main difficulties. One is that feasible sets of stochastic problems is not convex in general. The other main challenge arises from the need to calculate conditional expectation or probability both of which are involving multi-dimensional integrations. Due to the two major difficulties, for all three studied problems, we solved them with approximation approaches.We first study two types of chance constrained problems: linear program with joint chance constraints problem (LPPC) as well as maximum probability problem (MPP). For both problems, we assume that the random matrix is normally distributed and its vector rows are independent. We first dealt with LPPC which is generally not convex. We approximate it with two second-order cone programming (SOCP) problems. Furthermore under mild conditions, the optimal values of the two SOCP problems are a lower and upper bounds of the original problem respectively. For the second problem, we studied a variant of stochastic resource constrained shortest path problem (called SRCSP for short), which is to maximize probability of resource constraints. To solve the problem, we proposed to use a branch-and-bound framework to come up with the optimal solution. As its corresponding linear relaxation is generally not convex, we give a convex approximation. Finally, numerical tests on the random instances were conducted for both problems. With respect to LPPC, the numerical results showed that the approach we proposed outperforms Bonferroni and Jagannathan approximations. While for the MPP, the numerical results on generated instances substantiated that the convex approximation outperforms the individual approximation method.Then we study a distributionally robust stochastic quadratic knapsack problems, where we only know part of information about the random variables, such as its first and second moments. We proved that the single knapsack problem (SKP) is a semedefinite problem (SDP) after applying the SDP relaxation scheme to the binary constraints. Despite the fact that it is not the case for the multidimensional knapsack problem (MKP), two good approximations of the relaxed version of the problem are provided which obtain upper and lower bounds that appear numerically close to each other for a range of problem instances. Our numerical experiments also indicated that our proposed lower bounding approximation outperforms the approximations that are based on Bonferroni's inequality and the work by Zymler et al.. Besides, an extensive set of experiments were conducted to illustrate how the conservativeness of the robust solutions does pay off in terms of ensuring the chance constraint is satisfied (or nearly satisfied) under a wide range of distribution fluctuations. Moreover, our approach can be applied to a large number of stochastic optimization problems with binary variables.Finally, a stochastic version of the shortest path problem is studied. We proved that in some cases the stochastic shortest path problem can be greatly simplified by reformulating it as the classic shortest path problem, which can be solved in polynomial time. To solve the general problem, we proposed to use a branch-and-bound framework to search the set of feasible paths. Lower bounds are obtained by solving the corresponding linear relaxation which in turn is done using a Stochastic Projected Gradient algorithm involving an active set method. Meanwhile, numerical examples were conducted to illustrate the effectiveness of the obtained algorithm. Concerning the resolution of the continuous relaxation, our Stochastic Projected Gradient algorithm clearly outperforms Matlab optimization toolbox on large graphs.

Cette thèse est composée de deux parties, chacune portant sur un sous-domaine de l'optimisation combinatoire a priori distant de l'autre. Le premier thème de recherche abordé est la programmation biniveau stochastique. Se cachent derrière ce terme deux sujets de recherche relativement peu étudiés conjointement, à savoir d'un côté la programmation stochastique, et de l'autre la programmation biniveau. La programmation mathématique (PM) regroupe un ensemble de méthodes de modélisation et de résolution, pouvant être utilisées pour traiter des problèmes pratiques que se posent des décideurs. La programmation stochastique et la programmation biniveau sont deux sous-domaines de la PM, permettant chacun de modéliser un aspect particulier de ces problèmes pratiques. Nous élaborons un modèle mathématique issu d'un problème appliqué, où les aspects biniveau et stochastique sont tous deux sollicités, puis procédons à une série de transformations du modèle. Une méthode de résolution est proposée pour le PM résultant. Nous démontrons alors théoriquement et vérifions expérimentalement la convergence de cette méthode. Cet algorithme peut être utilisé pour résoudre d'autres programmes biniveaux que celui qui est proposé.Le second thème de recherche de cette thèse s'intitule "problèmes de coupe et de couverture partielles dans les graphes". Les problèmes de coupe et de couverture sont parmi les problèmes de graphe les plus étudiés du point de vue complexité et algorithmique. Nous considérons certains de ces problèmes dans une variante partielle, c'est-à-dire que la propriété de coupe ou de couverture dont il est question doit être vérifiée partiellement, selon un paramètre donné, et non plus complètement comme c'est le cas pour les problèmes originels. Précisément, les problèmes étudiés sont le problème de multicoupe partielle, de coupe multiterminale partielle, et de l'ensemble dominant partiel. Les versions sommets des ces problèmes sont également considérés. Notons que les problèmes en variante partielle généralisent les problèmes non partiels. Nous donnons des algorithmes exacts lorsque cela est possible, prouvons la NP-difficulté de certaines variantes, et fournissons des algorithmes approchés dans des cas assez généraux. / This thesis is composed of two parts, each part belonging to a sub-domain of combinatorial optimization a priori distant from the other. The first research subject is stochastic bilevel programming. This term regroups two research subject rarely studied together, namely stochastic programming on the one hand, and bilevel programming on the other hand. Mathematical Programming (MP) is a set of modelisation and resolution methods, that can be used to tackle practical problems and help take decisions. Stochastic programming and bilevel programming are two sub-domains of MP, each one of them being able to model a specific aspect of these practical problems. Starting from a practical problem, we design a mathematical model where the bilevel and stochastic aspects are used together, then apply a series of transformations to this model. A resolution method is proposed for the resulting MP. We then theoretically prove and numerically verify that this method converges. This algorithm can be used to solve other bilevel programs than the ones we study.The second research subject in this thesis is called "partial cut and cover problems in graphs". Cut and cover problems are among the most studied from the complexity and algorithmical point of view. We consider some of these problems in a partial variant, which means that the cut or cover property that is looked into must be verified partially, according to a given parameter, and not completely, as it was the case with the original problems. More precisely, the problems that we study are the partial multicut, the partial multiterminal cut, and the partial dominating set. Versions of these problems were vertices are

Dans cette thèse, nous étudions le problème d’optimisation des effectifs dans les centres d’appels, dans lequel nous visons à minimiser les coûts d’exploitation tout en offrant aux clients une qualité de service (QoS) élevée. Nous introduisons également l'utilisation de contraintes probabilistes qui exigent que la qualité de service soit satisfaite avec une probabilité donnée. Ces contraintes sont adéquates dans le cas où la performance est mesurée sur un court intervalle de temps, car les mesures de QoS sont des variables aléatoires sur une période donnée. Les problèmes de personnel proposés sont difficiles en raison de l'absence de forme analytique pour les contraintes probabilistes et doivent être approximées par simulation. En outre, les fonctions QoS sont généralement non linéaires et non convexes. Nous considérons les problèmes d’affectation personnel dans différents contextes et étudions les modèles proposés tant du point de vue théorique que pratique. Les méthodologies développées sont générales, en ce sens qu'elles peuvent être adaptées et appliquées à d'autres problèmes de décision dans les systèmes de files d'attente. La thèse comprend trois articles traitant de différents défis en matière de modélisation et de résolution de problèmes d'optimisation d’affectation personnel dans les centres d'appels à compétences multiples. Les premier et deuxième article concernent un problème d'optimisation d'affectation de personnel en deux étapes sous l'incertitude. Alors que dans le second, nous étudions un modèle général de programmation stochastique discrète en deux étapes pour fournir une garantie théorique de la consistance de l'approximation par moyenne échantillonnale (SAA) lorsque la taille des échantillons tend vers l'infini, le troisième applique l'approche du SAA pour résoudre le problème d’optimisation d'affectation de personnel en deux étapes avec les taux d’arrivée incertain. Les deux articles indiquent la viabilité de l'approche SAA dans notre contexte, tant du point de vue théorique que pratique. Pour être plus précis, dans le premier article, nous considérons un problème stochastique discret général en deux étapes avec des contraintes en espérance. Nous formulons un problème SAA avec échantillonnage imbriqué et nous montrons que, sous certaines hypothèses satisfaites dans les exemples de centres d'appels, il est possible d'obtenir les solutions optimales du problème initial en résolvant son SAA avec des échantillons suffisamment grands. De plus, nous montrons que la probabilité que la solution optimale du problème de l’échantillon soit une solution optimale du problème initial tend vers un de manière exponentielle au fur et à mesure que nous augmentons la taille des échantillons. Ces résultats théoriques sont importants, non seulement pour les applications de centre d'appels, mais également pour d'autres problèmes de prise de décision avec des variables de décision discrètes. Le deuxième article concerne les méthodes de résolution d'un problème d'affectation en personnel en deux étapes sous incertitude du taux d'arrivée. Le problème SAA étant coûteux à résoudre lorsque le nombre de scénarios est important. En effet, pour chaque scénario, il est nécessaire d'effectuer une simulation pour estimer les contraintes de QoS. Nous développons un algorithme combinant simulation, génération de coupes, renforcement de coupes et décomposition de Benders pour résoudre le problème SAA. Nous montrons l'efficacité de l'approche, en particulier lorsque le nombre de scénarios est grand. Dans le dernier article, nous examinons les problèmes de contraintes en probabilité sur les mesures de niveau de service. Notre méthodologie proposée dans cet article est motivée par le fait que les fonctions de QoS affichent généralement des courbes en S et peuvent être bien approximées par des fonctions sigmoïdes appropriées. Sur la base de cette idée, nous avons développé une nouvelle approche combinant la régression non linéaire, la simulation et la recherche locale par région de confiance pour résoudre efficacement les problèmes de personnel à grande échelle de manière viable. L’avantage principal de cette approche est que la procédure d’optimisation peut être formulée comme une séquence de simulations et de résolutions de problèmes de programmation linéaire. Les résultats numériques basés sur des exemples réels de centres d'appels montrent l'efficacité pratique de notre approche. Les méthodologies développées dans cette thèse peuvent être appliquées dans de nombreux autres contextes, par exemple les problèmes de personnel et de planification dans d'autres systèmes basés sur des files d'attente avec d'autres types de contraintes de QoS. Celles-ci soulèvent également plusieurs axes de recherche qu'il pourrait être intéressant d'étudier. Par exemple, une approche de regroupement de scénarios pour atténuer le coût des modèles d'affectation en deux étapes, ou une version d'optimisation robuste en distribution pour mieux gérer l'incertitude des données. / In this thesis, we study the staffing optimization problem in multiskill call centers, in which we aim at minimizing the operating cost while delivering a high quality of service (QoS) to customers. We also introduce the use of chance constraints which require that the QoSs are met with a given probability. These constraints are adequate in the case when the performance is measured over a short time interval as QoS measures are random variables in a given time period. The proposed staffing problems are challenging in the sense that the stochastic constraints have no-closed forms and need to be approximated by simulation. In addition, the QoS functions are typically non-linear and non-convex. We consider staffing optimization problems in different settings and study the proposed models in both theoretical and practical aspects. The methodologies developed are general, in the sense that they can be adapted and applied to other staffing/scheduling problems in queuing-based systems. The thesis consists of three articles dealing with different challenges in modeling and solving staffing optimization problems in multiskill call centers. The first and second articles concern a two-stage staffing optimization problem under uncertainty. While in the first one, we study a general two-stage discrete stochastic programming model to provide a theoretical guarantee for the consistency of the sample average approximation (SAA) when the sample sizes go to infinity, the second one applies the SAA approach to solve the two-stage staffing optimization problem under arrival rate uncertainty. Both papers indicate the viability of the SAA approach in our context, in both theoretical and practical aspects. To be more precise, in the first article, we consider a general two-stage discrete stochastic problem with expected value constraints. We formulate its SAA with nested sampling. We show that under some assumptions that hold in call center examples, one can obtain the optimal solutions of the original problem by solving its SAA with large enough sample sizes. Moreover, we show that the probability that the optimal solution of the sample problem is an optimal solution of the original problem, approaches one exponentially fast as we increase the sample sizes. These theoretical findings are important, not only for call center applications, but also for other decision-making problems with discrete decision variables. The second article concerns solution methods to solve a two-stage staffing problem under arrival rate uncertainty. It is motivated by the fact that the SAA version of the two-stage staffing problem becomes expensive to solve with a large number of scenarios, as for each scenario, one needs to use simulation to approximate the QoS constraints. We develop an algorithm that combines simulation, cut generation, cut strengthening and Benders decomposition to solve the SAA problem. We show the efficiency of the approach, especially when the number of scenarios is large. In the last article, we consider problems with chance constraints on the service level measures. Our methodology proposed in this article is motivated by the fact that the QoS functions generally display ``S-shape'' curves and might be well approximated by appropriate sigmoid functions. Based on this idea, we develop a novel approach that combines non-linear regression, simulation and trust region local search to efficiently solve large-scale staffing problems in a viable way. The main advantage of the approach is that the optimization procedure can be formulated as a sequence of steps of performing simulation and solving linear programming models. Numerical results based on real-life call center examples show the practical viability of our approach. The methodologies developed in this thesis can be applied in many other settings, e.g., staffing and scheduling problems in other queuing-based systems with other types of QoS constraints. These also raise several research directions that might be interesting to investigate. For examples, a clustering approach to mitigate the expensiveness of the two-stage staffing models, or a distributionally robust optimization version to better deal with data uncertainty.