Abordagens de otimização linear estocástica para problemas com restrições probabilísticas conjuntas com variáveis aleatórias inteiras
A área de Programação Estocástica combina otimização e teoria das probabilidades. O foco desta área é lidar com problemas de otimização com incerteza, em parte ou em todos os dados, que surge naturalmente em problemas reais. Há diversas maneiras de modelar estas incertezas e descrevemos brevemente algumas delas nesta dissertação. Dentre estas possibilidades, focamos em problemas de otimização linear estocástica com restrições probabilísticas conjuntas em que podemos separar a parte estocástica da parte determinística. Considerando este tipo de restrição, abordamos o caso em que as funções de distribuição de probabilidade são inteiras. Apresentamos o conceito de p-Level Efficient Points (p-LEPs) e mostramos exemplos em que a envoltória convexa dos p-LEPs pode conter pontos indesejados. Mais adiante, fornecemos propriedades e aspectos geométricos do conjunto de p-LEPs e a noção de α-concavidade para funções de distribuição de probabilidade inteiras. Incluímos um algoritmo para enumeração dos p-LEPs e
exemplificamos sua aplicação no problema de cobertura de conjuntos estocástico (do inglês,
stochastic set cover problem). Posteriormente, reformulamos problemas estocásticos com restrições probabilísticas conjuntas transformando-os em problemas determinísticos utilizando os p-LEPs. Apresentamos cinco abordagens para resolver estas reformulações, sendo elas: programação disjuntiva, relaxação convexa, algoritmo de plano de cortes, algoritmo de geração de colunas e a combinação das últimas duas técnicas. Utilizamos cada uma dessas abordagens para resolver diversas instâncias do problema de cobertura de conjuntos estocástico, onde variamos as dimensões do problema e também as funções de distribuição de probabilidade.