Pular para o conteúdo

A PDDE em uma página

Este capítulo oferece ao leitor que não conhece a programação dinâmica estocástica o contexto mínimo necessário para acompanhar o restante deste site. Ele apresenta a ideia da PDDE (SDDP) em uma página; os capítulos para os quais ele aponta, a começar por Algoritmo da PDDE, desenvolvem cada afirmação em detalhe.

O despacho ótimo ao longo de um horizonte multiestágio não pode ser resolvido pela enumeração de todos os cenários: o número de trajetórias de cenários cresce exponencialmente com o número de estágios. A PDDE evita a enumeração explorando a estrutura do problema.

Os estágios e as trajetórias de cenários apresentados aqui são o caso particular de um grafo da política (policy graph) mais geral, formado por nós e transições; veja Grafos da política para a estrutura geral.

Em cada estágio, o futuro é resumido por uma função de custo futuro VtV_t — o custo esperado mínimo daquele estágio em diante, como função do estado de entrada (níveis dos reservatórios, defasagens das afluências). O problema de despacho obedece a uma recursão por estágios (de Bellman): o custo futuro no estágio tt é o custo esperado da melhor decisão no presente mais o custo futuro do estado que essa decisão deixa:

Vt(xt−1)=Eωt ⁣[ min⁡xt,ut  ct(xt,ut)+Vt+1(xt) ]V_t(x_{t-1}) = \mathbb{E}_{\omega_t}\!\left[\, \min_{x_t, u_t}\; c_t(x_t, u_t) + V_{t+1}(x_t) \,\right]

com condição final VT+1(x)=0V_{T+1}(x) = 0. A minimização percorre o estado viável do estágio tt, xtx_t, e o controle utu_t, (xt,ut)∈Xt(xt−1,ωt)(x_t, u_t) \in \mathcal{X}_t(x_{t-1}, \omega_t), dados o estado de entrada xt−1x_{t-1} e a incerteza realizada ωt\omega_t. Para subproblemas de PL, VtV_t é convexa e linear por partes — a propriedade que a PDDE explora.

A PDDE nunca constrói Vt+1V_{t+1} explicitamente. Ela a aproxima por baixo com uma coleção crescente de funções afins chamadas cortes de Benders, cada uma delas uma subestimativa válida em todo o domínio:

Vt+1(x)  ≥  β0,i+βi⊤xfor every cut iV_{t+1}(x) \;\ge\; \beta_{0,i} + \beta_i^\top x \qquad \text{for every cut } i

No problema do estágio, o custo futuro é representado por uma variável de epígrafo (epigraph variable) θt\theta_t, que aproxima Vt+1(xt)V_{t+1}(x_t) e é limitada por todos os cortes (θt≥β0,i+βi⊤xt\theta_t \ge \beta_{0,i} + \beta_i^\top x_t), de modo que a aproximação é a envoltória superior max⁡i(β0,i+βi⊤x)\max_i (\beta_{0,i} + \beta_i^\top x).

A aproximação melhora iterativamente. Partindo de nenhum corte, o algoritmo alterna duas etapas:

Simulação forward: partindo do estado inicial, simula-se um lote de trajetórias de cenários ao longo de todos os estágios sob a política vigente — a regra que define as decisões de cada estágio resolvendo o problema do estágio com os cortes vigentes —, registrando o estado que cada trajetória atinge em cada estágio. Esses estados são os estados visitados.

Simulação backward: partindo do último estágio e retrocedendo até o segundo, resolve-se o subproblema de cada estágio em cada estado visitado sob cada uma das aberturas do estágio — suas realizações de ruído previamente geradas — e agrega-se a informação dual resultante em um novo corte por estado visitado para o estágio anterior: a formulação de corte único (single-cut). O corte expressa como o custo futuro varia quando o estado de entrada varia.

Sorteio das trajetórias de cenáriosamostradas, ou todas se enumeradasSimulação forwardestados visitados sob a política vigenteSimulação backwardum novo corte por estado visitadoAtualização dos limiteslimite inferior e superiorCritérios de parada atendidos?Políticaos cortes finais nãosim

Uma iteração da PDDE: sorteia-se um lote de trajetórias de cenários (amostradas, ou todas as trajetórias quando a simulação forward é enumerada); a simulação forward as simula sob a política vigente e registra os estados visitados; a simulação backward acrescenta um corte por estado visitado; a seleção periódica de cortes é executada quando configurada; os limites são atualizados; o ciclo se repete até que os critérios de parada sejam atendidos, e os cortes finais definem a política.

À medida que as iterações se acumulam, a aproximação linear por partes cobre uma parte maior do espaço de estados e o limite inferior nunca diminui:

A função de custo futuro convexa V(x)V(x) aproximada por baixo por cortes de Benders. Cada corte é uma tangente em um estado visitado — sua inclinação é a derivada analítica — e a envoltória superior dos cortes se aproxima da função verdadeira à medida que cortes são acrescentados.

A PDDE mantém dois limites para o custo ótimo (ajustado ao risco):

Limite inferior z‾\underline{z}: o valor ajustado ao risco do primeiro estágio sobre suas aberturas, com os cortes vigentes (definição). Sob as hipóteses de Gerenciamento de cortes — quando valem os limites e os certificados, esse valor é um limite inferior válido para o custo ótimo (ajustado ao risco) e não diminui à medida que cortes são acrescentados.

Limite superior zˉ\bar{z}: uma simulação forward enumerada, que visita cada trajetória de cenários uma única vez, fornece o custo exato ajustado ao risco da política — um limite superior para o valor ótimo — quando a medida de risco é uniforme entre os estágios; uma simulação forward amostrada fornece o custo médio das trajetórias amostradas, uma estimativa estatística com intervalo de confiança que nada certifica (Avaliação do limite superior, Camada 3).

O gap de otimalidade é o limite superior menos o limite inferior; sua forma percentual normaliza essa diferença pela magnitude do limite inferior, com piso de uma unidade monetária (veja Gap de otimalidade).

O treinamento (training) é encerrado quando seus critérios de parada são atendidos: um limite de iterações ou de tempo, um limite inferior estagnado ou, com um limite superior exato, um gap dentro da tolerância (Critérios de parada).

Um limite inferior não decrescente e uma estimativa amostral do limite superior, com sua faixa de confiança de 95%, aproximam-se ao longo das iterações. A faixa descreve o custo amostrado e nada certifica; o critério de gap compara o limite inferior com um limite superior exato.

Sob a medida de valor esperado em todos os estágios e as hipóteses da Camada 2, que também indica as configurações de seleção de cortes que as violam, o limite inferior converge para o valor ótimo com probabilidade 1 à medida que as iterações se acumulam. Sob uma medida avessa ao risco, a convergência da PDDE sem seleção de cortes é demonstrada na literatura (Guigues & Römisch, 2012; Philpott, de Matos & Finardi, 2013; Guigues, 2016), cada uma sob suas próprias hipóteses; a Camada 2 não enuncia nenhum resultado para esse caso.

O algoritmo básico da PDDE minimiza o custo esperado. O Novo Modelo admite formulações avessas ao risco por meio de medidas de risco aninhadas aplicadas em cada estágio, baseadas no valor em risco condicional (CVaR), que desloca peso para os cenários de custo elevado:

CVaRα(Z)=min⁡η∈R{η+1αE[(Z−η)+]}\text{CVaR}_\alpha(Z) = \min_{\eta \in \mathbb{R}} \left\{ \eta + \frac{1}{\alpha} \mathbb{E}\left[(Z - \eta)^+\right] \right\}

em que α∈(0,1]\alpha \in (0, 1] é a fração da cauda — CVaRα\text{CVaR}_\alpha é o custo esperado na pior fração α\alpha dos cenários. O Novo Modelo usa uma combinação convexa do valor esperado e do CVaR,

ρλ,α[Z]=(1−λ) E[Z]+λ⋅CVaRα[Z]\rho^{\lambda, \alpha}[Z] = (1 - \lambda)\, \mathbb{E}[Z] + \lambda \cdot \text{CVaR}_\alpha[Z]

com peso de aversão ao risco λ∈[0,1]\lambda \in [0, 1] (λ=0\lambda = 0 recupera a média neutra ao risco; λ=1\lambda = 1 é o CVaR puro). A medida é aplicada dentro da simulação backward: os coeficientes dos cortes são agregados por médias ponderadas pelo risco, em vez de valores esperados simples. Veja Medidas de risco para a formulação.

Distribuição de custos com a média, VaRα\mathrm{VaR}_\alpha e CVaRα\mathrm{CVaR}_\alpha marcados e a pior cauda α\alpha sombreada; aumentar λ\lambda desloca a política da média em direção à cauda.

Esta visão geral omite os detalhes de implementação: o leiaute do PL, o armazenamento dos cortes, a árvore de cenários e a estratégia de aproveitamento de base. Os grupos Modelagem do sistema, Modelagem estocástica e O algoritmo da PDDE tratam desses temas.

Para o algoritmo completo, com a formulação do PL do estágio, a dedução dos coeficientes dos cortes e o monitoramento da convergência, veja Algoritmo da PDDE.

Para a mecânica dos cortes — como os cortes são gerados, armazenados e eliminados —, veja Gerenciamento de cortes.

  • Algoritmo da PDDE — tratamento algorítmico completo: formulação do PL do estágio, geração de cortes, monitoramento da convergência
  • Gerenciamento de cortes — armazenamento de cortes, seleção Nível 1 (Level-1), o método dinâmico e o limite de cortes ativos
  • Medidas de risco — formulações do CVaR e de medidas de risco aninhadas para a PDDE avessa ao risco
  • Critérios de parada — limites de iterações e de tempo, estagnação do limite (bound stalling), o critério de gap e como os critérios se combinam