This dissertation addresses the modeling and solution of mixed-integer linear multistage stochastic programming problems involving both endogenous and exogenous uncertain parameters. We propose a composite scenario tree that captures both types of uncertainty, and we exploit its unique structure to derive new theoretical properties that can drastically reduce the number of non-anticipativity constraints (NACs). Since the reduced model is often still intractable, we discuss two special solution approaches. The first is a sequential scenario decomposition heuristic in which we sequentially solve endogenous MILP subproblems to determine the binary investment decisions, fix these decisions to satisfy the first-period and exogenous NACs, and then solve the resulting model to obtain a feasible solution. The second approach is Lagrangean decomposition. We present numerical results for a process network planning problem and an oilfield development planning problem. The results clearly demonstrate the efficiency of the special solution methods over solving the reduced model directly. To further generalize this work, we also propose a graph-theory algorithm for non-anticipativity constraint reduction in problems with arbitrary scenario sets. Finally, in a break from the rest of the thesis, we present the basics of stochastic programming for non-expert users.

[pt] Neste trabalho estudamos uma classe de problemas de otimização estocástica com incertezas endógenas que é formulado como um problema de programação não-linear inteira (MINLP). Esta classe de problemas difere dos problemas de otimização estocástica geralmente estudados na literatura pelo fato de que que a distribuição de probabilidade dos parâmetros aleatórios depende das decisões tomadas. Apesar de discutido dentro do contexto do problema de logística humanitária, a metodologia proposta e os resutados obtidos são válidos para uma classe geral de problemas que agrega uma variedade de aplicações. Em particular, propõe-se (i) uma técnica de convexificação de polinômios de variáveis binárias, (ii) um algoritmo de geração de cortes e (iii) a incorporação dos conceitos de importance sampling dentro do contexto de otimização estocástica de modo a permitir a solução de grandes instâncias do problema. Os resultados computacionais apresentados demonstram as vantagens da metodologia proposta ao permitir a solução de instâncias significativamente maiores que aquelas atualmente apresentadas em trabalhos relacionados. / [en] In this work we study a class of stochastic programming problems with endogenous uncertainty – i.e., those in which the probability distribution of the random parameters is decision-dependent – which is formulated as a mixed integer non-linear programming (MINLP) problem. Although discussed in the context of the humanitarian logistics problem, the proposed methodology and obtained results are also valid for a more general class of problems which comprehends a variety of applications. In particular, we propose (i) a convexification technique for polynomials of binary variables, (ii) an efficient cutgeneration algorithm and (iii) the incorporation of importance sampling concepts into the stochastic programming framework so as to allow the solution of large instances of the problem. Computational results demonstrate the effectiveness of the proposed methodology by solving instances significantly larger than those reported in related works.

We consider two classes of stochastic programming models which are motivated by two applications related to the field of aviation. The first problem we consider is the network capacity planning problem, which arises in capacity planning of systems with network structures, such as transportation terminals, roadways and telecommunication networks. We study this problem in the context of airport terminal capacity planning. In this problem, the objective is to determine the optimal design and expansion capacities for different areas of the terminal in the presence of uncertainty in future demand levels and expansion costs, such that overall passenger delay is minimized. We model this problem as a nonlinear multistage stochastic integer program with a multicommodity network flow structure. The formulation requires the use of time functions for maximum delays in passageways and processing stations, for which we derive approximations that account for the transient behavior of flow. The deterministic equivalent of the developed model is solved via a branch and bound procedure, in which a bounding heuristic is used at the nodes of the branch and bound tree to obtain integer solutions. In the second study, we consider the project portfolio optimization problem. This problem falls in the class of stochastic programs in which times of uncertainty realizations are dependent on the decisions made. The project portfolio optimization problem deals with the selection of research and development (R&D) projects and determination of optimal resource allocations for the current planning period such that the expected total discounted return or a function of this expectation for all projects over an infinite time horizon is maximized, given the uncertainties and resource limitations over a planning horizon. Accounting for endogeneity in some parameters, we propose efficient modeling and solution approaches for the resulting multistage stochastic integer programming model. We first develop a formulation that is amenable to scenario decomposition, and is applicable to the general class of stochastic problems with endogenous uncertainty. We then demonstrate the use of the sample average approximation method in solving large scale problems of this class, where the sample problems are solved through Lagrangian relaxation and lower bounding heuristics.

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.

[pt] Os incêndios florestais podem ser uma fonte de vulnerabilidade para sistemas de potência. Esses eventos podem afetar especialmente a operação de sistemas de distribuição, interrompendo o fornecimento de energia, aumentando os custos, e diminuindo a confiabilidade. Nesta dissertação, é considerada a relação entre as decisões operativas e a probabilidade de falha nas linhas sob o contexto de queimadas. Este tipo de estudo ainda não foi devidamente avaliado pelo meio acadêmico. Ao não reconhecer este aspecto, o funcionamento dos sistemas de potência pode estar sendo prejudicado. A modelagem adequada dessa dependência poderia reduzir a incidência de queimadas e perda de carga. Considerando este aspecto, um problema de otimização distributivamente robusto de dois estágios com incerteza endógena foi desenvolvido para considerar a operação multiperíodo de sistemas de distribuição. O primeiro estágio determina a topologia da rede e os investimentos nas linhas, e o segundo estágio avalia o custo operacional esperado no pior caso. Nessa estrutura, a incerteza é modelada de forma dependente das decisões do modelo, onde as probabilidades de falha da linha são em função do fluxo de potência das próprias linhas. Um método iterativo é proposto para resolver este modelo e uma análise fora da amostra é desenvolvida para validação através de diferentes estudos. Os resultados mostraram que, ao negligenciar a dependência da incerteza, uma maior perda de carga e um maior custo operacional são esperados. Ao considerar esta nova abordagem, a confiabilidade da rede pode ser melhorada e as consequências dos incêndios podem ser mitigadas com ações mais econômicas. / [en] Wildfires can be a source of vulnerability for power systems operations. These events can especially affect the operation of distribution systems. They can interrupt energy supply, increase costs, and decrease grid resilience. Numerous approaches can be executed to prevent them. In this dissertation, it is considered the relationship between operative actions and the probability of wildfire disruption. This type of study has not been properly evaluated in technical and scientific literature. By not recognizing this aspect, the operation of power systems may be impaired. Properly modeling this dependency could lower wildfire disruption and loss of load. Considering this, a two-stage distributionally robust optimization problem with decision-dependent uncertainty is developed to consider distribution system multiperiod operation. The first stage determines the optimal switching actions and line investments, and the second stage evaluates the worst-case expected operation cost. It is designed a decision-dependent uncertainty framework where the line failure probabilities are a function (dependent) of its power flow levels. An iterative method is proposed to solve this model and an out-of-sample analysis is developed to validate it through different case studies. Results showed that, by neglecting the uncertainty dependency on operative decisions, there could be a higher expected loss of load and a higher operational cost. By considering this new approach when operating power lines, the grid s resilience could be improved and wildfire consequences can be mitigated with less costly actions.