Algoritmo da PDDE
Objetivo
Seção intitulada “Objetivo”Este capítulo descreve o algoritmo de Programação Dinâmica Dual Estocástica — PDDE (SDDP) — tal como implementado no Novo Modelo: a formulação estocástica multiestágio, a estrutura iterativa de simulações forward/backward, o monitoramento da convergência, as topologias do grafo da política (policy graph), os requisitos das variáveis de estado e a formulação de corte único (single-cut). Ele serve de fundamento algorítmico ao qual os demais capítulos de metodologia fazem referência.
Para as convenções de notação (conjuntos de índices, parâmetros, variáveis de decisão, variáveis duais), veja Convenções de notação.
Para a visão por entidade deste capítulo, veja Valor da água e custo futuro.
1. Contexto do problema
Seção intitulada “1. Contexto do problema”O Novo Modelo resolve o problema do despacho hidrotérmico: determinar a programação ótima de geração das usinas hidrelétricas e termelétricas ao longo de um horizonte de planejamento sob incerteza nas afluências. Características principais:
- Flexível para horizontes curtos ou longos: estágios diários, semanais ou mensais, em horizontes de curto a longo prazo
- Espaço de estados grande: a dimensão do estado cresce com o número de reservatórios e com as ordens AR dos seus modelos de afluência
- Afluências estocásticas: modelos autorregressivos PAR(p) com padrões sazonais
- Complexidade de modelagem ajustável por estágio: a geração de cenários, a produção hidrelétrica e outros aspectos são configuráveis por estágio e por elemento
2. Formulação como programação estocástica multiestágio
Seção intitulada “2. Formulação como programação estocástica multiestágio”O problema do despacho hidrotérmico é formulado como um programa estocástico multiestágio:
sujeito às restrições de acoplamento entre estágios e à realização da incerteza. A formulação aninhada usa funções de valor:
com condição final , que um estudo pode substituir por uma função terminal importada (§7).
Ideia-chave: a função de valor é convexa e linear por partes (para subproblemas de PL), o que permite a aproximação externa por cortes de Benders.
Aproximação da função de valor por cortes de Benders — cada corte é uma tangente em um estado visitado (sua inclinação é a derivada analítica ), estreitando a aproximação externa em direção à verdadeira função de custo futuro convexa.
3. O algoritmo da PDDE
Seção intitulada “3. O algoritmo da PDDE”A PDDE constrói iterativamente aproximações lineares por partes , na iteração , das verdadeiras funções de valor. Cada iteração começa com uma simulação forward que resolve os estágios em ordem ao longo de trajetórias de cenários amostradas ou enumeradas, registrando os estados visitados e os custos das trajetórias a partir dos quais se calcula o limite superior (Avaliação do limite superior). Em seguida, uma simulação backward percorre os estágios do último até o segundo: em cada estágio , resolve todo par (filho, abertura) em cada estado visitado , agrega um corte por estado visitado para o estágio e sincroniza os processos para que cada um detenha esses cortes antes de passar ao estágio . A seleção periódica de cortes e o limite de cortes ativos são então executados, quando o estudo os configura, e o limite inferior é avaliado resolvendo-se o primeiro estágio sobre suas aberturas. Se os critérios de parada não forem atendidos, a iteração recomeça pela simulação forward; uma vez atendidos, o treinamento (training) é encerrado, e a política é simulada quando o estudo habilita a fase de simulação (Critérios de parada descreve como os critérios se combinam).
3.1 Simulação forward
Seção intitulada “3.1 Simulação forward”A simulação forward simula o sistema sob a política vigente para gerar os estados visitados — os estados que serão usados pela simulação backward para construir os cortes.
Para cada uma das trajetórias de cenários independentes:
- Parte-se do estado inicial conhecido (volumes armazenados iniciais e histórico de afluências)
- Em cada estágio , amostra-se uma realização de cenário do conjunto de cenários do estágio e resolve-se o PL do estágio usando o estado de entrada e o cenário amostrado. O PL inclui todos os cortes de Benders vigentes como restrições sobre a variável de custo futuro
- Registra-se o estado ótimo (volumes armazenados ao fim do estágio e defasagens AR atualizadas), canonicalizado sobre seus limites admissíveis (veja abaixo), como estado visitado do estágio
- Repassa-se como estado de entrada do estágio
Com simulação forward enumerada, toda trajetória da raiz até uma folha do grafo da política é visitada exatamente uma vez em cada iteração, sem amostragem, e as trajetórias fazem o papel das trajetórias; todo nó desse grafo possui uma única abertura, que o passo 2 toma como a realização do estágio (Grafos da política §6).
A simulação forward produz: (a) os estados visitados em cada estágio para cada trajetória e (b) os custos dos estágios para a estimativa do limite superior.
Paralelização: as trajetórias forward são independentes — o Novo Modelo distribui as trajetórias entre os processos (ranks MPI), com threads resolvendo PLs de estágio individuais dentro de cada processo.
Aproveitamento de base: quando a simulação backward faz aproveitamento de base (warm-start da base), a base da resolução forward no estágio serve de ponto de partida para as resoluções da simulação backward do estágio no mesmo estado visitado, reduzindo seus tempos de resolução (Aproveitamento de base do PL).
Canonicalização do estado: o estado de saída registrado não é o primal bruto do PL, mas sua projeção sobre os limites admissíveis resolvidos. Cada coordenada limitada — armazenamento ao fim do estágio, volume de água em trânsito e qualquer compromisso mantido de termelétrica com antecipação de despacho — é trazida para dentro do seu intervalo resolvido, enquanto as defasagens de afluência (AR), que não são limitadas, passam inalteradas. A projeção é a identidade para um ótimo dentro dos limites, de modo que uma resolução cujo estado permanece dentro dos limites não é afetada por ela. Ela é aplicada uma única vez, na leitura de volta, e todos os consumidores leem esse único vetor canônico: a trajetória forward, o estado visitado da simulação backward e o termo independente (intercepto) do corte ancorado nele (veja Gerenciamento de cortes). É isso que faz de uma função bem definida do valor ótimo do estágio e de seus limites resolvidos — independente do vértice ótimo degenerado em que a resolução terminou ou de erros de arredondamento. Veja Determinismo e rastreabilidade.
3.2 Simulação backward
Seção intitulada “3.2 Simulação backward”A simulação backward aprimora a aproximação da função de valor gerando novos cortes de Benders, percorrendo os estágios em ordem inversa, de até , e acrescentando cortes aos estágios até .
Em cada estágio , para cada estado visitado coletado durante a simulação forward:
- Resolve-se o PL do estágio para todo cenário (ramificação), usando o estado visitado como estado de entrada
- De cada solução do PL, extraem-se o valor ótimo da função objetivo , os custos reduzidos das colunas fixadas do estado de entrada e os duais das linhas que leem a afluência realizada e das linhas de corte. Os coeficientes do armazenamento e das defasagens de afluência entram no corte quando a projeção do corte do estágio mantém essas componentes; os coeficientes das parcelas de água em trânsito (in-transit buckets) e das posições do anel de despacho antecipado (commitment ring slots) das termelétricas com antecipação de despacho sempre entram (Aumento do espaço de estados §7). Os custos reduzidos fornecem diretamente os coeficientes do armazenamento, das parcelas e das posições — não é necessária nenhuma combinação com os duais das restrições da FPHA ou das restrições genéricas —, e os duais fornecem os coeficientes das defasagens de afluência pela regra da cadeia (Folding do PAR(p) §4). Veja Gerenciamento de cortes
- Calculam-se os termos do corte por cenário no estado visitado, sendo cada coeficiente de armazenamento, de parcela e de posição de o custo reduzido do passo 2 dividido pelo fator de escala da sua coluna, e cada coeficiente de defasagem de afluência a regra da cadeia do passo 2 sobre os duais desescalonados (Gerenciamento de cortes §2). O Novo Modelo forma os coeficientes das defasagens de afluência uma vez por filho, a partir dos duais agregados com os pesos do passo 4, o que, em aritmética exata, dá o agregado dos coeficientes por cenário (Folding do PAR(p) §4)
- Agregam-se os termos do corte por cenário em um único corte. Em um grafo da política, o corte de um nó agrega todo par (filho, abertura) de , ponderado por , com a medida de risco atuando uma única vez sobre essa lei conjunta; na cadeia de estágios, o nó tem um único filho e os pesos são as probabilidades uniformes sobre . Veja Gerenciamento de cortes §3
- Acrescenta-se o corte agregado ao conjunto de cortes do estágio
A simulação backward produz um novo corte por estágio, por estado visitado e por iteração.
Árvore de cenários com simulação forward amostrada — a simulação forward amostra M trajetórias esparsas pela árvore de ramificação, enquanto a simulação backward avalia todas as aberturas em cada estado visitado e as agrega em um único corte de Benders. A assimetria entre forward esparsa e backward exaustiva mantém a iteração tratável quando a avaliação da árvore completa é inviável; uma simulação forward enumerada, em vez disso, visita todas as trajetórias (§3.1).
3.3 Monitoramento da convergência
Seção intitulada “3.3 Monitoramento da convergência”Limite inferior: é o valor ajustado ao risco do primeiro estágio sobre suas aberturas, com os cortes vigentes (Avaliação do limite superior — Limite inferior). Ele não diminui ao longo das iterações, e a Camada 1 estabelece quando ele é um limite válido.
Limite superior: com simulação forward amostrada, é uma estimativa estatística — a média amostral sobre as trajetórias da simulação forward; com simulação forward enumerada, é o limite exato ponderado pelas probabilidades sobre todas as trajetórias até as folhas, sem erro amostral (veja Avaliação do limite superior). A forma da média amostral:
em que é o fator de desconto acumulado do estágio (Formulação da taxa de desconto §5). Com uma função terminal importada (§7), o custo de cada trajetória inclui também o valor descontado dessa função no estado final da trajetória.
Gap de otimalidade: a distância entre o limite superior e o limite inferior, expressa em percentual do limite inferior; Critérios de parada o define, bem como o critério de parada por gap que o utiliza.
3.4 Modelo de execução e considerações de desempenho
Seção intitulada “3.4 Modelo de execução e considerações de desempenho”A estrutura de iterações da PDDE tem propriedades específicas que orientam a estratégia de paralelização e o projeto do ciclo de vida do solver. Elas são resumidas aqui como restrições de arquitetura.
Sincronização da simulação backward: a simulação backward impõe uma barreira de sincronização por estágio: os cortes gerados pelas resoluções do estágio estão completos, e sincronizados entre os processos, antes que qualquer resolução do estágio comece, de modo que toda resolução do estágio os inclua. Isso serializa o algoritmo nas fronteiras entre estágios.
Cada resolução de estágio, forward ou backward, carrega o modelo (template) de PL do estágio, que contém os cortes ativos no momento em que o modelo foi construído, e acrescenta os cortes adicionados desde então; no método dinâmico, uma vez iniciado o seu laço preguiçoso (lazy), essas resoluções carregam, em vez disso, um subconjunto residente limitado do conjunto de cortes (Gerenciamento de cortes §8). O trabalho é distribuído entre processos e threads conforme descrito em Aceleradores de desempenho.
A arquitetura de software que implementa essas restrições está descrita no README de novomodelo-sddp.
4. Estrutura do grafo da política
Seção intitulada “4. Estrutura do grafo da política”A cadeia de estágios usada ao longo deste capítulo — um nó por estágio , ligados por transições de probabilidade e terminando em ou em uma função terminal importada (§7) — é o caso particular de um grafo da política mais geral: uma estrutura de nós, transições ponderadas por probabilidades e conjuntos de cortes de custo futuro por nó. Veja Grafos da política para a estrutura completa de nós/transições/conjuntos de cortes, os dois eixos de probabilidade (pesos das arestas entre nós versus aberturas dentro do nó), a convenção de desconto separado e o mapeamento para a família SDDP.jl.
O grafo da política do Novo Modelo é apenas de horizonte finito: um grafo acíclico, terminado em folhas, no qual toda trajetória começa em uma raiz e alcança uma folha após um número limitado de estágios. Uma forma de grafo cíclica — um estágio posterior com transição de volta para um anterior, para planejamento com horizonte periódico infinito — está reservada e é rejeitada na carga do caso. Veja Modos de horizonte para o projeto-alvo cíclico que essa reserva antecipa, e Grafos da política para a lista completa de limitações estruturais.
5. Variáveis de estado e a propriedade de Markov
Seção intitulada “5. Variáveis de estado e a propriedade de Markov”Para que a PDDE gere cortes válidos, o subproblema deve satisfazer a propriedade de Markov: os custos futuros dependem apenas do estado atual, e não da trajetória pela qual o estado atual foi alcançado.
Variáveis de estado no Novo Modelo:
| Componente | Variável | Quantidade | Descrição |
|---|---|---|---|
| Armazenamento hidrelétrico | Volume do reservatório ao fim do estágio | ||
| Defasagens AR de afluência | Afluências defasadas dos modelos AR(), armazenadas em número de por usina (Aumento do espaço de estados §4) | ||
| Parcelas de água em trânsito | Água defluída ainda em trânsito sob atraso de tempo de viagem — uma parcela por usina receptora por defasagem de maturação | ||
| Posições do anel de despacho antecipado | um anel por usina com antecipação | Compromissos decididos e ainda não entregues — cada um ocupa uma posição do anel da sua usina até o seu estágio de entrega |
As duas últimas componentes estão presentes apenas quando o estudo as declara: os arcos com tempo de viagem da água introduzem as parcelas de água em trânsito, e as termelétricas com antecipação de despacho introduzem as posições do anel de despacho antecipado. Um estudo sem nenhuma delas reduz-se ao estado clássico de armazenamento (+ defasagens AR). As quatro componentes são estado de Markov genuíno. O armazenamento, as parcelas e as posições do anel são fixados por limites de coluna nas suas colunas de estado de entrada, e o custo reduzido de cada coluna fornece seu coeficiente no corte (seção 3.2); as defasagens de afluência não têm coluna no PL, chegam ao PL pelos lados direitos e recebem seus coeficientes no corte dos duais, pela regra da cadeia (§5.1).
5.1 Expansão do estado com as defasagens AR
Seção intitulada “5.1 Expansão do estado com as defasagens AR”O modelo de afluências PAR(p) requer as afluências passadas para calcular a afluência atual. Para manter a propriedade de Markov, essas defasagens são incluídas como variáveis de estado. Elas não são colunas do PL: antes de cada resolução, a afluência realizada de cada usina hidrelétrica é calculada a partir das defasagens de entrada e do ruído da abertura,
em que é o valor da afluência com defasagem repassado pelo estágio anterior, e entra nas linhas que leem a afluência como constante do lado direito (Formulação do PL §5). Os coeficientes das defasagens , que entram no corte quando a projeção do corte do estágio mantém as componentes de defasagem de afluência, capturam o valor marginal do histórico de afluências; eles são calculados a partir dos duais desescalonados da resolução pela regra da cadeia — veja Gerenciamento de cortes §2 e Folding do PAR(p).
Veja Modelo de afluências PAR(p) para a formulação autorregressiva completa e Aumento do espaço de estados §4 para o modo como as defasagens entram no PL do estágio.
5.2 Expansão do estado com tempo de viagem e termelétricas com antecipação
Seção intitulada “5.2 Expansão do estado com tempo de viagem e termelétricas com antecipação”Dois outros mecanismos expandem o vetor de estado além do armazenamento e das defasagens AR, e ambos são tratados como estado de Markov pela mesma fixação por limites de coluna do armazenamento — os custos reduzidos das suas colunas fixadas, cada um dividido pelo fator de escala da sua coluna, fornecem seus coeficientes no corte.
Parcelas de água em trânsito. Quando o arco principal da cascata de uma usina hidrelétrica possui tempo de viagem, a água defluída chega à usina de jusante apenas após um atraso. O volume em trânsito é acompanhado como estado de Benders aumentado — uma parcela por usina de jusante por defasagem de maturação —, de modo que o custo futuro de um estágio dependa apenas dos volumes em trânsito atuais, e não da trajetória de defluências que os produziu.
Posições do anel de despacho antecipado. Uma termelétrica com antecipação de despacho compromete geração antes do seu estágio de entrega, por um número de estágios ou por uma antecedência física. Cada compromisso decidido e ainda não entregue ocupa uma posição do anel de despacho antecipado da usina desde o seu estágio de decisão (o primeiro estágio, para um compromisso decidido antes do estudo) até o seu estágio de entrega. As posições do anel de despacho antecipado são estado de Markov para que o corte de cada estágio valore os compromissos já em curso.
Ambas as expansões são opcionais e específicas de cada instância; veja Visão geral da modelagem dos elementos do sistema para a configuração das entidades, Aumento do espaço de estados §6 para as linhas das parcelas de água em trânsito e Aumento do espaço de estados §5 para o controle da entrega das termelétricas com antecipação no PL do estágio.
6. Formulação de corte único
Seção intitulada “6. Formulação de corte único”Um corte agregado por estado visitado por iteração:
em que e agregam os termos por cenário e da §3.2 com os pesos de Gerenciamento de cortes §3: sob o valor esperado, e , e sob uma medida de risco as probabilidades ajustadas ao risco de Medidas de risco §7 substituem esses pesos.
- Vantagens: menos cortes, PL menor e resoluções mais rápidas do que em uma formulação multicorte (multi-cut) (Birge & Louveaux, 1988), que mantém um corte por abertura em cada estado visitado
- Desvantagens: pode exigir mais iterações para convergir do que uma formulação multicorte
O Novo Modelo implementa a formulação de corte único (Gerenciamento de cortes §3).
7. Cortes de fronteira terminal
Seção intitulada “7. Cortes de fronteira terminal”Por padrão, a recursão termina com a condição final da §2. Um estudo pode substituí-la por uma função terminal fixa definida por cortes importados de um conjunto de cortes de uma política de origem, os cortes de fronteira terminal (cortes de final de horizonte), que formam o conjunto de cortes do estágio terminal. A simulação backward não gera corte algum para esse conjunto, e nenhum é eliminado dele, de modo que a função permanece fixa durante toda a execução.
Os cortes importados são válidos para a função de custo futuro do modelo de origem, de modo que o limite inferior e a política do estudo são válidos em relação à função importada, a função terminal fixa das hipóteses da Camada 1. Um modelo do estudo posterior que difira do modelo de origem não é corrigido pelo treinamento, e a diferença introduz viés na política perto do fim do horizonte. Os cortes importados apenas limitam inferiormente a variável de custo futuro, de modo que tal diferença nunca torna inviável um subproblema de estágio; ela altera o valor.
O conjunto de cortes de origem, as condições de compatibilidade, o estado propagado e a reconciliação de calendário são tratados em Fronteira pós-estudo e estudos encadeados.
Implementação no Novo Modelo
Seção intitulada “Implementação no Novo Modelo”A metodologia acima define a estrutura de simulações forward/backward e as restrições do modelo de execução que a moldam; a aba abaixo descreve como a interface de software do Novo Modelo configura o escalonamento do trabalho da simulação backward.
O parâmetro de distribuição de trabalho da simulação backward do Novo Modelo fica
no bloco training.parallelism do config.json. Esta aba mostra como o
escalonador é escolhido; a simulação backward e o modelo de execução dentro dos
quais o escalonador distribui o trabalho permanecem nas seções de metodologia acima
(§3.2 Simulação backward,
§3.4 Modelo de execução e considerações de desempenho).
training.parallelism — Configuração do escalonador da simulação backward
Seção intitulada “training.parallelism — Configuração do escalonador da simulação backward”O escalonador decide como o trabalho da simulação backward é dividido entre os
workers: por padrão, um estado visitado por unidade de trabalho, ou um par
(trial point, opening block) (estado visitado, bloco de aberturas) por unidade de
trabalho com by_node. Com qualquer dos dois escalonadores, o conjunto de cortes e
o limite inferior do treinamento (training) não dependem do número de workers nem
da ordem em que os workers assumem as unidades. Os dois escalonadores encadeiam de
forma diferente as aberturas de um estado visitado; assim, uma resolução pode partir
de outra base
(Aproveitamento de base do PL §2) e,
quando um PL do estágio tem várias soluções ótimas, terminar em outra delas; os
cortes dos dois podem então diferir. O exemplo seleciona by_node com quatro
aberturas por bloco:
{ "training": { "parallelism": { "backward_scheduler": { "method": "by_node", "block_size": 4 } } }}training.parallelism lista os
métodos, campos, valores padrão e erros de carregamento;
Escalonamento por nó explica quando
usar by_node e sua interação com o método de seleção dynamic.
Referências cruzadas
Seção intitulada “Referências cruzadas”- Convenções de notação — Todos os conjuntos de índices, parâmetros, variáveis de decisão e definições de variáveis duais
- Formulação do PL — O PL completo do subproblema do estágio que as simulações forward/backward resolvem
- Grafos da política — A generalização da cadeia de estágios em nós/transições/conjuntos de cortes; os dois eixos de probabilidade, a convenção de desconto separado e as limitações estruturais (apenas horizonte finito, cíclico reservado)
- Gerenciamento de cortes — Geração, agregação e seleção de cortes, condições de validade e a garantia de monotonicidade do conjunto somente de acréscimo (append-only)
- Determinismo e rastreabilidade — Canonicalização, na leitura de volta, dos valores dos estados visitados sobre os limites admissíveis, e os mecanismos de reprodutibilidade (ordenação canônica dos blocos de estado, ordem de resolução fixada) em que ela se apoia
- Modelo de afluências PAR(p) — Modelo estocástico de afluências que gera a incerteza na simulação forward
- Folding do PAR(p) — a afluência realizada como constante do lado direito e os coeficientes dos cortes nas defasagens de afluência pela regra da cadeia
- Formulação da taxa de desconto — Equação de Bellman com desconto, taxas dependentes do estágio, fator de desconto sobre θ
- Modos de horizonte — O projeto-alvo reservado do grafo da política cíclico (função de período sazonal, inequação de convergência do ciclo, conjunto de cortes indexado por período sazonal, operador de Bellman de ponto fixo) que a restrição a horizonte finito em Grafos da política antecipa
- Fronteira pós-estudo e estudos encadeados — a função terminal importada: conjunto de cortes de origem, condições de compatibilidade, estado propagado e reconciliação de calendário
- Avaliação do limite superior — Métodos de estimativa do limite superior
- Critérios de parada — Critérios de convergência que encerram o processo iterativo
- Medidas de risco — CVaR e extensões avessas ao risco da recursão de Bellman
- Sistema de penalidades — Folgas de recurso e a precondição sob a qual elas mantêm viável todo PL de estágio (recurso relativamente completo)
- Formulações específicas por equipamento — Modelagem dos equipamentos térmicos
- Geração de cenários — Árvore de aberturas fixa, abstração do esquema de amostragem, árvores de cenários enumeradas
- Executando o Novo Modelo: Executando estudos — o fluxo de trabalho do software que treina e executa este algoritmo.