[en] CONSERVATIVE-SOLUTION METHODOLOGIES FOR STOCHASTIC PROGRAMMING: A DISTRIBUTIONALLY ROBUST OPTIMIZATION APPROACH

[pt] METODOLOGIAS PARA OBTENÇÃO DE SOLUÇÕES CONSERVADORAS PARA PROGRAMAÇÃO ESTOCÁSTICA: UMA ABORDAGEM DE OTIMIZAÇÃO ROBUSTA À DISTRIBUIÇÕES

[pt] CARLOS ANDRES GAMBOA RODRIGUEZ

[pt] PROGRAMACAO ESTOCASTICA DOIS ESTAGIOS

[pt] METODOS EXATOS DE LIMITES BASEADOS NA PARTICAO

[pt] METRICA DE WASSERSTEIN

[pt] OTIMIZACAO ROBUSTA A DISTRIBUICOES

[pt] METODOS DE DECOMPOSICAO

[en] TWO-STAGE STOCHASTIC PROGRAMMING

[en] EXACT BOUND PARTITION METHODS

[en] WASSERSTEIN METRIC

[en] DISTRIBUTIONALLY ROBUST OPTIMIZATION

[en] DECOMPOSITION METHODS

[pt] A programação estocástica dois estágios é uma abordagem matemática amplamente usada em aplicações da vida real, como planejamento da operação de sistemas de energia, cadeias de suprimentos, logística, gerenciamento de inventário e planejamento financeiro. Como a maior parte desses problemas não pode ser resolvida analiticamente, os tomadores de decisão utilizam métodos numéricos para obter uma solução quase ótima. Em algumas aplicações, soluções não convergidas e, portanto, sub-ótimas terminam sendo implementadas devido a limitações de tempo ou esforço computacional. Nesse contexto, os métodos existentes fornecem uma solução otimista sempre que a convergência não é atingida. As soluções otimistas geralmente geram altos níveis de arrependimento porque subestimam os custos reais na função objetivo aproximada. Para resolver esse problema, temos desenvolvido duas metodologias de solução conservadora para problemas de programação linear estocástica dois estágios com incerteza do lado direito e suporte retangular: Quando a verdadeira distribuição de probabilidade da incerteza é conhecida, propomos um problema DRO (Distributionally Robust Optimization) baseado em esperanças condicionais adaptadas à uma partição do suporte cuja complexidade cresce exponencialmente com a dimensionalidade da incerteza; Quando apenas observações históricas da incerteza estão disponíveis, propomos um problema de DRO baseado na métrica de Wasserstein a fim de incorporar ambiguidade sobre a real distribuição de probabilidade da incerteza. Para esta última abordagem, os métodos existentes dependem da enumeração dos vértices duais do problema de segundo estágio, tornando o problema DRO intratável em aplicações práticas. Nesse contexto, propomos esquemas algorítmicos para lidar com a complexidade computacional de ambas abordagens. Experimentos computacionais são apresentados para o problema do fazendeiro, o problema de alocação de aviões, e o problema do planejamento da operação do sistema elétrico (unit ommitmnet problem).

[en] Two-stage stochastic programming is a mathematical framework widely used in real-life applications such as power system operation planning, supply chains, logistics, inventory management, and financial planning. Since most of these problems cannot be solved analytically, decision-makers make use of numerical methods to obtain a near-optimal solution. Some applications rely on the implementation of non-converged and therefore sub-optimal solutions because of computational time or power limitations. In this context, the existing methods provide an optimistic solution whenever convergence is not attained. Optimistic solutions often generate high disappointment levels because they consistently underestimate the actual costs in the approximate objective function. To address this issue, we have developed two conservative-solution methodologies for two-stage stochastic linear programming problems with right-hand-side uncertainty and rectangular support: When the actual data-generating probability distribution is known, we propose a DRO problem based on partition-adapted conditional expectations whose complexity grows exponentially with the uncertainty dimensionality; When only historical observations of the uncertainty are available, we propose a DRO problem based on the Wasserstein metric to incorporate ambiguity over the actual data-generating probability distribution. For this latter approach, existing methods rely on dual vertex enumeration of the second-stage problem rendering the DRO problem intractable in practical applications. In this context, we propose algorithmic schemes to address the computational complexity of both approaches. Computational experiments are presented for the farmer problem, aircraft allocation problem, and the stochastic unit commitment problem.

DAVI MICHEL VALLADAO

ALEXANDRE STREET DE AGUIAR

BRUNO DA COSTA FLACH

ALEXANDRE STREET DE AGUIAR

BERNARDO KULNIG PAGNONCELLI

DAVI MICHEL VALLADAO

BRUNO FANZERES DOS SANTOS

TITO HOMEM-DE-MELLO

2021-07-20

2021-03-17

[pt] TEXTO

application/pdf

INGLÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=53796@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=53796@2

https://doi.org/10.17771/PUCRio.acad.53796