Les centres d’appels sont des éléments clés de presque n’importe quelle grande organisation. Le problème de gestion du travail a reçu beaucoup d’attention dans la littérature. Une formulation typique se base sur des mesures de performance sur un horizon infini, et le problème d’affectation d’agents est habituellement résolu en combinant des méthodes d’optimisation et de simulation. Dans cette thèse, nous considérons un problème d’affection d’agents pour des centres d’appels soumis a des contraintes en probabilité. Nous introduisons une formulation qui exige que les contraintes de qualité de service (QoS) soient satisfaites avec une forte probabilité, et définissons une approximation de ce problème par moyenne échantillonnale dans un cadre de compétences multiples. Nous établissons la convergence de la solution du problème approximatif vers celle du problème initial quand la taille de l’échantillon croit. Pour le cas particulier où tous les agents ont toutes les compétences (un seul groupe d’agents), nous concevons trois méthodes d’optimisation basées sur la simulation pour le problème de moyenne échantillonnale. Étant donné un niveau initial de personnel, nous augmentons le nombre d’agents pour les périodes où les contraintes sont violées, et nous diminuons le nombre d’agents pour les périodes telles que les contraintes soient toujours satisfaites après cette réduction. Des expériences numériques sont menées sur plusieurs modèles de centre d’appels à faible occupation, au cours desquelles les algorithmes donnent de bonnes solutions, i.e. la plupart des contraintes en probabilité sont satisfaites, et nous ne pouvons pas réduire le personnel dans une période donnée sont introduire de violation de contraintes. Un avantage de ces algorithmes, par rapport à d’autres méthodes, est la facilité d’implémentation. / Call centers are key components of almost any large organization. The problem of labor management has received a great deal of attention in the literature. A typical formulation of the staffing problem is in terms of infinite-horizon performance measures. The method of combining simulation and optimization is used to solve this staffing problem. In this thesis, we consider a problem of staffing call centers with respect to chance constraints. We introduce chance-constrained formulations of the scheduling problem which requires that the quality of service (QoS) constraints are met with high probability. We define a sample average approximation of this problem in a multiskill setting. We prove the convergence of the optimal solution of the sample-average problem to that of the original problem when the sample size increases. For the special case where we consider the staffing problem and all agents have all skills (a single group of agents), we design three simulation-based optimization methods for the sample problem. Given a starting solution, we increase the staffings in periods where the constraints are violated, and decrease the number of agents in several periods where decrease is acceptable, as much as possible, provided that the constraints are still satisfied. For the call center models in our numerical experiment, these algorithms give good solutions, i.e., most constraints are satisfied, and we cannot decrease any agent in any period to obtain better results. One advantage of these algorithms, compared with other methods, that they are very easy to implement.

[pt] Este trabalho propõe a inclusão de restrições probabilísticas como alternativa para inclusão de aversão ao risco no problema de planejamento de longo prazo da geração em sistemas hidrotérmicos, resolvido por programação dinâmica dual estocástica (PDDE). Propõe-se uma abordagem menos restritiva em comparação com métodos alternativos de aversão a risco já avaliados no sistema brasileiro, como a curva de aversão ao risco (CAR) ou a superfície de aversão a risco (SAR). Considera-se uma decomposição de Benders de dois estágios para o subproblema de cada nó da árvore de cenários da PDDE, onde o subproblema de segundo estágio é denominado CCP-SAR. O objetivo é obter uma política operativa que considere explicitamente o risco de não atendimento à demanda vários meses à frente, no subproblema CCP-SAR, com uma modelagem contínua das variáveis aleatórias associadas à energia natural afluente aos reservatórios, segundo uma distribuição normal multivariada. A região viável para a restrição probabilística é aproximada por planos cortantes, construídos a partir da técnica de bisseção e calculando-se os gradientes dessas restrições, usando o código de Genz. Na primeira parte deste trabalho resolve-se de forma iterativa o subproblema CCP-SAR, para um determinado vetor de armazenamentos iniciais para o sistema. Na segunda parte do trabalho constrói-se uma superfície de aversão a risco probabilística, varrendo-se um espectro de valores para o armazenamento inicial. / [en] This paper proposes the inclusion of chance constrained programming as an alternative to include risk aversion in the long-term power generation planning problem of hydrothermal systems, solved by stochastic dual dynamic programming (SDDP). It is proposed a less restrictive approach as compared to traditional methods of risk aversion that have been used in the Brazilian system, such as risk aversion curve (CAR) or risk aversion surface (SAR). A two-stage Benders decomposition subproblem is considered for each SDDP scenario, where the second stage subproblem is labeled CCP-SAR. The objective is to yield an operational policy that explicitly considers the risk of load curtailment several months ahead, while considering in the CCP-SAR subproblem a continuous multivariate normal distribution for the random variables related to energy inflows to the reservoirs. The feasible region for this chance constrained subproblem is outer approximated by linear cuts, using the bisection method which gradients were calculated using Genz s code. The first part of this dissertation solves the multi-stage deterministic CCP-SAR problem by an iterative procedure, for a given initial vector storage for the system. The second part presents the probabilistic risk aversion surface, for a range of values of initial storage.

[ES] La gran mayoría de procesos del mundo real tienen incertidumbres inherentes, las cuales, al ser consideradas en el proceso de modelado, se puede obtener una representación que describa con la mayor precisión posible el comportamiento del proceso real. En la mayoría de casos prácticos, se considera que éstas tienen un comportamiento estocástico y sus descripciones como distribuciones de probabilidades son conocidas. Las estrategias de MPC estocástico están desarrolladas para el control de procesos con incertidumbres de naturaleza estocástica, donde el conocimiento de las propiedades estadísticas de las incertidumbres es aprovechado al incluirlo en el planteamiento de un problema de control óptimo (OCP). En éste, y contrario a otros esquemas de MPC, las restricciones duras son relajadas al reformularlas como restricciones de tipo probabilísticas con el fin de reducir el conservadurismo. Esto es, se permiten las violaciones de las restricciones duras originales, pero tales violaciones no deben exceder un nivel de riesgo permitido. La no-convexidad de tales restricciones probabilísticas hacen que el problema de optimización sea prohibitivo, por lo que la mayoría de las estrategias de MPC estocástico en la literatura se diferencian en la forma en que abordan tales restricciones y las incertidumbres, para volver el problema computacionalmente manejable. Por un lado, están las estrategias deterministas que, fuera de línea, convierten las restricciones probabilísticas en unas nuevas de tipo deterministas, usando la propagación de las incertidumbres a lo largo del horizonte de predicción para ajustar las restricciones duras originales. Por otra parte, las estrategias basadas en escenarios usan la información de las incertidumbres para, en cada instante de muestreo, generar de forma aleatoria un conjunto de posibles evoluciones de éstas a lo largo del horizonte de predicción. De esta manera, convierten las restricciones probabilísticas en un conjunto de restricciones deterministas que deben cumplirse para todos los escenarios generados. Estas estrategias se destacan por su capacidad de incluir en tiempo real información actualizada de las incertidumbres. No obstante, esta ventaja genera inconvenientes como su gasto computacional, el cual aumenta conforme lo hace el número de escenarios y; por otra parte, el efecto no deseado en el problema de optimización, causado por los escenarios con baja probabilidad de ocurrencia, cuando se usa un conjunto de escenarios pequeño. Los retos mencionados anteriormente orientaron esta tesis hacia los enfoques de MPC estocástico basado en escenarios, produciendo tres contribuciones principales. La primera consiste en un estudio comparativo de un algoritmo del grupo determinista con otro del grupo basado en escenarios; se hace un especial énfasis en cómo cada uno de estos aborda las incertidumbres, transforma las restricciones probabilísticas y en la estructura de su OCP, además de señalar sus aspectos más destacados y desafíos. La segunda contribución es una nueva propuesta de algoritmo MPC, el cual se basa en escenarios condicionales, diseñado para sistemas lineales con incertidumbres correlacionadas. Este esquema aprovecha la existencia de tal correlación para convertir un conjunto de escenarios inicial de gran tamaño en un conjunto de escenarios más pequeño con sus probabilidades de ocurrencia, el cual conserva las características del conjunto inicial. El conjunto reducido es usado en un OCP en el que las predicciones de los estados y entradas del sistema son penalizadas de acuerdo con las probabilidades de los escenarios que las componen, dando menor importancia a los escenarios con menores probabilidades de ocurrencia. La tercera contribución consiste en un procedimiento para la implementación del nuevo algoritmo MPC como gestor de la energía en una microrred en la que las previsiones de las energías renovables y las cargas están correlacionadas. / [CA] La gran majoria de processos del món real tenen incerteses inherents, les quals, en ser considerades en el procés de modelatge, es pot obtenir una representació que descriga amb la major precisió possible el comportament del procés real. En la majoria de casos pràctics, es considera que aquestes tenen un comportament estocàstic i les seues descripcions com a distribucions de probabilitats són conegudes. Les estratègies de MPC estocàstic estan desenvolupades per al control de processos amb incerteses de naturalesa estocàstica, on el coneixement de les propietats estadístiques de les incerteses és aprofitat en incloure'l en el plantejament d'un problema de control òptim (OCP). En aquest, i contrari a altres esquemes de MPC, les restriccions dures són relaxades en reformulades com a restriccions de tipus probabilístiques amb la finalitat de reduir el conservadorisme. Això és, es permeten les violacions de les restriccions dures originals, però tals violacions no han d'excedir un nivell de risc permès. La no-convexitat de tals restriccions probabilístiques fan que el problema d'optimització siga computacionalment immanejable, per la qual cosa la majoria de les estratègies de MPC estocàstic en la literatura es diferencien en la forma en què aborden tals restriccions i les incerteses, per a tornar el problema computacionalment manejable. D'una banda, estan les estratègies deterministes que, fora de línia, converteixen les restriccions probabilístiques en unes noves de tipus deterministes, usant la propagació de les incerteses al llarg de l'horitzó de predicció per a ajustar les restriccions dures originals. D'altra banda, les estratègies basades en escenaris usen la informació de les incerteses per a, en cada instant de mostreig, generar de manera aleatòria un conjunt de possibles evolucions d'aquestes al llarg de l'horitzó de predicció. D'aquesta manera, converteixen les restriccions probabilístiques en un conjunt de restriccions deterministes que s'han de complir per a tots els escenaris generats. Aquestes estratègies es destaquen per la seua capacitat d'incloure en temps real informació actualitzada de les incerteses. No obstant això, aquest avantatge genera inconvenients com la seua despesa computacional, el qual augmenta conforme ho fa el nombre d'escenaris i; d'altra banda, l'efecte no desitjat en el problema d'optimització, causat pels escenaris amb baixa probabilitat d'ocurrència, quan s'usa un conjunt d'escenaris xicotet. Els reptes esmentats anteriorment van orientar aquesta tesi cap als enfocaments de MPC estocàstic basat en escenaris, produint tres contribucions principals. La primera consisteix en un estudi comparatiu d'un algorisme del grup determinista amb un altre del grup basat en escenaris; on es fa un especial èmfasi en com cadascun d'aquests aborda les incerteses, transforma les restriccions probabilístiques i en l'estructura del seu problema d'optimització, a més d'assenyalar els seus aspectes més destacats i desafiaments. La segona contribució és una nova proposta d'algorisme MPC, el qual es basa en escenaris condicionals, dissenyat per a sistemes lineals amb incerteses correlacionades. Aquest esquema aprofita l'existència de tal correlació per a convertir un conjunt d'escenaris inicial de gran grandària en un conjunt d'escenaris més xicotet amb les seues probabilitats d'ocurrència, el qual conserva les característiques del conjunt inicial. El conjunt reduït és usat en un OCP en el qual les prediccions dels estats i entrades del sistema són penalitzades d'acord amb les probabilitats dels escenaris que les componen, donant menor importància als escenaris amb menors probabilitats d'ocurrència. La tercera contribució consisteix en un procediment per a la implementació del nou algorisme MPC com a gestor de l'energia en una microxarxa en la qual les previsions de les energies renovables i les càrregues estan correlacionades. / [EN] The vast majority of real-world processes have inherent uncertainties, which, when considered in the modelling process, can provide a representation that most accurately describes the behaviour of the real process. In most practical cases, these are considered to have stochastic behaviour and their descriptions as probability distributions are known. Stochastic model predictive control algorithms are developed to control processes with uncertainties of a stochastic nature, where the knowledge of the statistical properties of the uncertainties is exploited by including it in the optimal control problem (OCP) statement. Contrary to other model predictive control (MPC) schemes, hard constraints are relaxed by reformulating them as probabilistic constraints to reduce conservatism. That is, violations of the original hard constraints are allowed, but such violations must not exceed a permitted level of risk. The non-convexity of such probabilistic constraints renders the optimisation problem computationally unmanageable, thus most stochastic MPC strategies in the literature differ in how they deal with such constraints and uncertainties to turn the problem computationally tractable. On the one hand, there are deterministic strategies that, offline, convert probabilistic constraints into new deterministic ones, using the propagation of uncertainties along the prediction horizon to tighten the original hard constraints. Scenario-based approaches, on the other hand, use the uncertainty information to randomly generate, at each sampling instant, a set of possible evolutions of uncertainties over the prediction horizon. In this fashion, they convert the probabilistic constraints into a set of deterministic constraints that must be fulfilled for all the scenarios generated. These strategies stand out for their ability to include real-time updated uncertainty information. However, this advantage comes with inconveniences such as computational effort, which grows as the number of scenarios does, and the undesired effect on the optimisation problem caused by scenarios with a low probability of occurrence when a small set of scenarios is used. The aforementioned challenges steered this thesis toward stochastic scenario-based MPC approaches, and yielded three main contributions. The first one consists of a comparative study of an algorithm from the deterministic group with another one from the scenario-based group, where a special emphasis is made on how each of them deals with uncertainties, transforms the probabilistic constraints and on the structure of the optimisation problem, as well as pointing out their most outstanding aspects and challenges. The second contribution is a new proposal for a MPC algorithm, which is based on conditional scenarios, developed for linear systems with correlated uncertainties. This scheme exploits the existence of such correlation to convert a large initial set of scenarios into a smaller one with their probabilities of occurrence, which preserves the characteristics of the initial set. The reduced set is used in an OCP in which the predictions of the system states and inputs are penalised according to the probabilities of the scenarios that compose them, giving less importance to the scenarios with lower probabilities of occurrence. The third contribution consists of a procedure for the implementation of the new MPC algorithm as an energy manager in a microgrid in which the forecasts of renewables and loads are correlated. / González Querubín, EA. (2024). Scenario-Based Model Predictive Control for Systems with Correlated Uncertainties [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/203887

The aim of this thesis is to present new results concerning duality in scalar optimization. We show how the theory can be applied to optimization problems arising in the theory of risk measures, portfolio optimization and machine learning. First we give some notations and preliminaries we need within the thesis. After that we recall how the well-known Lagrange dual problem can be derived by using the general perturbation theory and give some generalized interior point regularity conditions used in the literature. Using these facts we consider some special scalar optimization problems having a composed objective function and geometric (and cone) constraints. We derive their duals, give strong duality results and optimality condition using some regularity conditions. Thus we complete and/or extend some results in the literature especially by using the mentioned regularity conditions, which are weaker than the classical ones. We further consider a scalar optimization problem having single chance constraints and a convex objective function. We also derive its dual, give a strong duality result and further consider a special case of this problem. Thus we show how the conjugate duality theory can be used for stochastic programming problems and extend some results given in the literature. In the third chapter of this thesis we consider convex risk and deviation measures. We present some more general measures than the ones given in the literature and derive formulas for their conjugate functions. Using these we calculate some dual representation formulas for the risk and deviation measures and correct some formulas in the literature. Finally we proof some subdifferential formulas for measures and risk functions by using the facts above. The generalized deviation measures we introduced in the previous chapter can be used to formulate some portfolio optimization problems we consider in the fourth chapter. Their duals, strong duality results and optimality conditions are derived by using the general theory and the conjugate functions, respectively, given in the second and third chapter. Analogous calculations are done for a portfolio optimization problem having single chance constraints using the general theory given in the second chapter. Thus we give an application of the duality theory in the well-developed field of portfolio optimization. We close this thesis by considering a general Support Vector Machines problem and derive its dual using the conjugate duality theory. We give a strong duality result and necessary as well as sufficient optimality conditions. By considering different cost functions we get problems for Support Vector Regression and Support Vector Classification. We extend the results given in the literature by dropping the assumption of invertibility of the kernel matrix. We use a cost function that generalizes the well-known Vapnik's ε-insensitive loss and consider the optimization problems that arise by using this. We show how the general theory can be applied for a real data set, especially we predict the concrete compressive strength by using a special Support Vector Regression problem.

The aim of this thesis is to present new results concerning duality in scalar optimization. We show how the theory can be applied to optimization problems arising in the theory of risk measures, portfolio optimization and machine learning. First we give some notations and preliminaries we need within the thesis. After that we recall how the well-known Lagrange dual problem can be derived by using the general perturbation theory and give some generalized interior point regularity conditions used in the literature. Using these facts we consider some special scalar optimization problems having a composed objective function and geometric (and cone) constraints. We derive their duals, give strong duality results and optimality condition using some regularity conditions. Thus we complete and/or extend some results in the literature especially by using the mentioned regularity conditions, which are weaker than the classical ones. We further consider a scalar optimization problem having single chance constraints and a convex objective function. We also derive its dual, give a strong duality result and further consider a special case of this problem. Thus we show how the conjugate duality theory can be used for stochastic programming problems and extend some results given in the literature. In the third chapter of this thesis we consider convex risk and deviation measures. We present some more general measures than the ones given in the literature and derive formulas for their conjugate functions. Using these we calculate some dual representation formulas for the risk and deviation measures and correct some formulas in the literature. Finally we proof some subdifferential formulas for measures and risk functions by using the facts above. The generalized deviation measures we introduced in the previous chapter can be used to formulate some portfolio optimization problems we consider in the fourth chapter. Their duals, strong duality results and optimality conditions are derived by using the general theory and the conjugate functions, respectively, given in the second and third chapter. Analogous calculations are done for a portfolio optimization problem having single chance constraints using the general theory given in the second chapter. Thus we give an application of the duality theory in the well-developed field of portfolio optimization. We close this thesis by considering a general Support Vector Machines problem and derive its dual using the conjugate duality theory. We give a strong duality result and necessary as well as sufficient optimality conditions. By considering different cost functions we get problems for Support Vector Regression and Support Vector Classification. We extend the results given in the literature by dropping the assumption of invertibility of the kernel matrix. We use a cost function that generalizes the well-known Vapnik's ε-insensitive loss and consider the optimization problems that arise by using this. We show how the general theory can be applied for a real data set, especially we predict the concrete compressive strength by using a special Support Vector Regression problem.