Grafos da política
Objetivo
Seção intitulada “Objetivo”O índice de estágio usado ao longo de Algoritmo da PDDE (SDDP) (a convenção matemática com base 1) é o caso particular de uma estrutura mais geral: um grafo da política (policy graph) formado por nós e transições, em que um estágio pode conter mais de um nó e um nó pode ter sua própria realização local. Este capítulo define essa estrutura — nós, transições e conjuntos de cortes de custo futuro; os dois eixos de probabilidade de um grafo da política; por que o desconto é uma grandeza do estágio, e não da aresta; como a estrutura se relaciona com a família SDDP.jl; suas limitações estruturais atuais; e a restrição adicional que uma simulação backward/forward exata (enumerada) impõe e que uma simulação amostrada não impõe. Trata-se da base estrutural sobre a qual se apoiam os demais capítulos de modelagem estocástica.
Para a visão por entidade deste capítulo, veja Cenários e aberturas.
1. Nós, transições e conjuntos de cortes de custo futuro
Seção intitulada “1. Nós, transições e conjuntos de cortes de custo futuro”Um nó tem um identificador único, situa-se em um estágio do estudo , pode apontar para a coluna de realizações do próprio estágio (presente apenas quando o estágio do nó tem um cenário fornecido externamente) e pode ter um rótulo.
Uma transição é uma aresta orientada de um nó para outro nó exatamente um estágio adiante, ponderada por uma probabilidade de transição. Toda aresta avança o grafo exatamente um estágio — um grafo da política não tem arestas no mesmo estágio nem arestas para trás.
O grafo da política mais simples é uma cadeia de estágios implícita: nenhum nó é declarado, cada estágio contém exatamente um nó (sem nome), e as extremidades de cada transição são ids de estágio, e não ids de nó. Essa é a cadeia já descrita em Algoritmo da PDDE §2 e é o grafo pressuposto por todos os capítulos anteriores. Declarar os nós explicitamente generaliza a mesma estrutura: um estágio pode então conter vários nós, cada um com sua própria identidade e (opcionalmente) seu próprio ponteiro de realização.
Um nó sem transição de saída é uma folha; um nó sem transição de entrada é uma raiz. Todo nó que não é folha possui seu próprio conjunto de cortes de custo futuro (cortes de Benders) — a generalização por nó do conjunto de cortes por estágio descrito em Gerenciamento de cortes. Na cadeia de estágios implícita, um nó por estágio reduz isso exatamente ao conjunto por estágio lá documentado. Todas as folhas do grafo compartilham um único conjunto, ao qual a simulação backward não acrescenta cortes, pois o custo futuro de uma folha é a condição final compartilhada (§5).
A simulação backward, executada nó a nó das folhas em direção à raiz, constrói o corte de um nó a partir dos subproblemas de seus filhos: em cada estado visitado, resolve cada filho sob cada abertura desse filho e agrega todos os pares (filho, abertura) de uma só vez (§2). A simulação forward amostra uma única trajetória raiz→folha — um nó por estágio ao longo do caminho percorrido — e toma decisões usando a aproximação de cortes atual de cada nó visitado.
Os círculos são nós que possuem conjunto de cortes (não folhas); as elipses são folhas que compartilham o único conjunto final. Os três painéis são grafos da política finitos/acíclicos válidos. A cadeia de estágios e o leque terminal são árvores — todo nó tem grau de entrada no máximo 1 —, enquanto o híbrido com recombinação une dois nós do estágio 1 em um único nó do estágio 2, que passa a ter grau de entrada 2. A §6 retoma por que essa distinção importa.
2. Dois eixos de probabilidade
Seção intitulada “2. Dois eixos de probabilidade”Um grafo da política tem duas estruturas de probabilidade que permanecem conceitualmente distintas:
- Pesos entre nós (arestas). As probabilidades das transições de saída de cada nó somam 1 (a verificação feita na carga está na aba Configurar de Implementação no Novo Modelo). Este eixo determina para qual nó filho uma trajetória se move.
- Aberturas dentro do nó. Independentemente de suas arestas de saída, um nó tem seu próprio conjunto local de aberturas — as realizações sob as quais seu subproblema do estágio é avaliado. Este eixo determina qual realização é avaliada depois que o próprio nó é alcançado; trata-se do mesmo conceito de abertura dentro do estágio descrito para a cadeia em Algoritmo da PDDE §3 e em Geração de cenários, com escopo por nó em vez de por estágio.
A simulação backward compõe os dois eixos em uma única lei conjunta. O corte de um nó é construído sobre os pares formados por um filho e uma abertura desse filho, cada par ponderado pelo produto da probabilidade de transição da aresta pela probabilidade da abertura dentro do filho, uniforme sobre . A medida de risco do estágio do nó atua uma única vez sobre essa lei conjunta, e não sobre as aberturas de cada filho com os resultados depois ponderados entre os filhos.
Equação de Bellman do nó e corte
Seção intitulada “Equação de Bellman do nó e corte”Seja a função de custo futuro aproximada pelo conjunto de cortes do nó , uma função do estado que o nó transmite aos seus filhos; na cadeia de estágios, , a função de valor de Algoritmo da PDDE §2 no estágio seguinte ao do nó. Sob o valor esperado,
em que a soma externa percorre os filhos de , é o conjunto viável do estado e do controle do filho dados o estado de entrada e a abertura , é o custo imediato do filho e é o fator de desconto do seu estágio (§3). Em uma folha, é a função terminal compartilhada por todas as folhas (§5): zero, ou a função terminal importada fixa de Algoritmo da PDDE §7.
O corte do nó em um estado visitado limita a variável de custo futuro do nó :
com
em que é o vetor de coeficientes obtido do subproblema do filho em sob a abertura , e é seu termo independente, sendo o valor ótimo desse subproblema (Gerenciamento de cortes §2 e §3). Sob uma medida de risco, a soma dupla de é substituída pela medida de risco do estágio do nó aplicada uma única vez à lei conjunta dos pares , e os produtos no corte são substituídos pelas probabilidades ajustadas ao risco de Medidas de risco calculadas sobre essa lei.
3. O desconto é definido por estágio, não por aresta
Seção intitulada “3. O desconto é definido por estágio, não por aresta”O fator de desconto definido em Formulação da taxa de desconto é uma propriedade da transição de estágio , e não de uma aresta do grafo da política. O modelo-base (template) do estágio o contém uma única vez, como coeficiente de na função objetivo, e contém o desconto de entrega de Formulação da taxa de desconto em cada coluna de decisão antecipada (Aumento do espaço de estados); ambos são fixos por estágio.
Um grafo de nós explícito mantém essa convenção por estágio: uma substituição do desconto aplica-se a um estágio, e uma transição entre dois nós declarados não pode ter sua própria substituição de desconto. A razão é estrutural, e não acidental — como os fatores de desconto são fixados no modelo-base do estágio uma vez por estágio, uma substituição por aresta (e, portanto, potencialmente por nó) exigiria um modelo-base separado por nó, o que o modelo-base único compartilhado do estágio não suporta. Existe um ponto de declaração por transição, preparado para o futuro, justamente porque a cadeia de estágios implícita tem uma transição por estágio, de modo que uma declaração por aresta ali equivale a uma declaração por estágio; quando um estágio pode conter vários nós, essa equivalência se rompe e apenas a declaração por estágio continua significativa.
4. Correspondência com a família SDDP.jl
Seção intitulada “4. Correspondência com a família SDDP.jl”A estrutura de nós/transições/conjuntos de cortes acima é a mesma abstração que Dowson (2020) define como policy graph e que o pacote SDDP.jl implementa (Dowson & Kapelevich, 2021): cada nó tem um subproblema local e seu próprio conjunto de cortes, ligados por arcos ponderados por probabilidades, e a simulação backward agrega os conjuntos dos sucessores no corte do nó pai exatamente como descrito na §1. O grafo do Novo Modelo é o membro finito, acíclico e terminado em folhas dessa família — toda trajetória começa em uma raiz e termina em uma folha após um número limitado de estágios, sem ciclo de volta a um estágio anterior. A §5 enuncia as restrições adicionais que o Novo Modelo impõe dentro desse membro.
5. Limitações conhecidas
Seção intitulada “5. Limitações conhecidas”O grafo da política do Novo Modelo tem três limitações estruturais além da própria forma finita/acíclica/terminada em folhas:
- Um único nó inicial. Um caso fornece um único registro de condições iniciais para todo o grafo, de modo que o estado de entrada que ancora o grafo é compartilhado por construção — o grafo é ancorado em uma única raiz, mesmo onde o esquema permitiria estruturalmente mais de um nó no estágio 0.
- Um único valor terminal compartilhado entre as folhas. Toda folha, independentemente do nó ou do caminho que a alcança, remete ao mesmo conjunto final compartilhado, ao qual a simulação backward não acrescenta cortes. Isso generaliza a condição final de Algoritmo da PDDE §2: há um único valor de custo futuro terminal para todo o grafo, e não um por folha — zero, , ou a função terminal importada fixa de Algoritmo da PDDE §7.
- Apenas horizonte finito. Somente a forma de grafo acíclica e terminada em folhas é aceita; a variante cíclica (horizonte periódico infinito) é reservada e rejeitada na carga do caso. Veja Modos de horizonte para o projeto cíclico pretendido que essa reserva antecipa.
6. O requisito estrutural de árvore enumerada
Seção intitulada “6. O requisito estrutural de árvore enumerada”Uma simulação backward/forward enumerada (exata) — em oposição a uma amostrada — visita todos os nós de forma determinística e reconstrói o estado de entrada de cada nó ao longo de um único caminho a partir de seu pai. Essa reconstrução só é bem definida sob duas restrições adicionais sobre o grafo, além da forma finita/acíclica/terminada em folhas:
- Um conjunto de aberturas unitário em cada nó (). Uma simulação exata avalia exatamente uma abertura por nó: um nó com mais de uma abertura é rejeitado na preparação, de modo que a ramificação é expressa estruturalmente, como nós irmãos distintos, cada um com sua única abertura.
- Grau de entrada 1 em todos os nós — uma árvore pura, sem recombinação. Um nó alcançado a partir de mais de um predecessor (o painel híbrido com recombinação da §1) tem mais de um estado de entrada candidato. Reconstruir seu estado ao longo do caminho de apenas um dos pais descartaria silenciosamente as trajetórias que chegam pelo outro pai.
Ambas as restrições existem pela mesma razão: uma simulação exata não guarda, por trajetória, a memória de como chegou a um nó; logo, o estado de entrada de um nó deve corresponder exata e inequivocamente ao único caminho que leva a ele. Uma simulação amostrada carrega seu próprio estado de entrada junto com cada trajetória que avalia, e por isso não está sujeita a nenhuma das restrições — ela avalia o conjunto de aberturas de um nó por sorteio, em vez de enumerá-lo, e resolve nativamente uma junção de recombinação, em vez de reconstruir um único caminho.
Como a contagem enumerada cresce multiplicativamente ao longo de cada caminho raiz→folha, o número total de folhas que uma simulação enumerada visitaria é verificado quanto a estouro (overflow) antes da execução; um grafo cuja enumeração exata estouraria é rejeitado na preparação, em vez de ser truncado silenciosamente ou sofrer transbordamento circular.
Dos três painéis da §1: a cadeia de estágios e o leque terminal são árvores puras e admitem uma simulação exata (sujeita à restrição de abertura unitária em cada nó); o híbrido com recombinação é rejeitado para uma simulação exata em sua junção com grau de entrada 2 e exige, em vez disso, uma simulação amostrada.
Implementação no Novo Modelo
Seção intitulada “Implementação no Novo Modelo”A metodologia acima define os nós, as transições e suas probabilidades; a aba abaixo mostra como a interface do software Novo Modelo os declara e verifica as probabilidades na carga.
O Novo Modelo lê o grafo da política (policy graph) a partir do objeto policy_graph do stages.json.
Esta aba apresenta a grafia dos nós, das transições e das probabilidades que
Grafos da política define acima, e a regra que verifica as
probabilidades na carga; a tabela completa de campos está em
stages.json.
Campos de nó e de transição
Seção intitulada “Campos de nó e de transição”Uma entrada de policy_graph.nodes[] tem as chaves id, stage_id, scenario_id e
label. As chaves id e stage_id são obrigatórias, label é um nome opcional
legível, e scenario_id só está presente em um nó cujo estágio
recebe um cenário fornecido externamente.
Uma entrada de policy_graph.transitions[] tem as chaves source_id, target_id e
probability. As duas extremidades são ids de nós quando nodes[] é declarado e,
caso contrário, ids de estágios. No dialeto de cadeia de estágios (sem nodes[]), uma transição
também pode conter annual_discount_rate_override; com nodes[], essa chave é rejeitada.
As regras da sobrescrita estão na aba Configurar de
Formulação da taxa de desconto.
A chave scenario_id só se aplica sob uma simulação forward enumerada. Nesse caso, ela é
obrigatória em todo nó cujo estágio recebe um cenário fornecido externamente, e
deve indexar uma coluna válida de cada uma dessas classes externas; é rejeitada em um
nó cujo estágio não recebe nenhum. Uma simulação forward amostrada rejeita qualquer scenario_id
na inicialização, indicando o primeiro nó que o declara e o respectivo estágio.
O objeto policy_graph a seguir declara um leque terminal sob uma simulação forward
enumerada: um nó-tronco no estágio 0, que fixa o único cenário externo do seu estágio, e
três filhos no estágio 1, cada um fixando um de três cenários fornecidos externamente.
{ "policy_graph": { "type": "finite_horizon", "annual_discount_rate": 0.06, "nodes": [ { "id": 0, "stage_id": 0, "scenario_id": 0, "label": "trunk" }, { "id": 1, "stage_id": 1, "scenario_id": 0, "label": "dry" }, { "id": 2, "stage_id": 1, "scenario_id": 1, "label": "normal" }, { "id": 3, "stage_id": 1, "scenario_id": 2, "label": "wet" } ], "transitions": [ { "source_id": 0, "target_id": 1, "probability": 0.25 }, { "source_id": 0, "target_id": 2, "probability": 0.5 }, { "source_id": 0, "target_id": 3, "probability": 0.25 } ] }}Probabilidades de transição
Seção intitulada “Probabilidades de transição”Os valores de probability de saída de cada origem devem somar 1 com tolerância de 1e-6;
uma origem cuja soma se afaste mais que isso faz a carga falhar, e o erro indica a
origem e a soma. Quando a verificação é aprovada, o carregador reescala as probabilidades de saída de cada
origem para que somem exatamente 1. Uma soma nula ou não finita é rejeitada.
Referências cruzadas
Seção intitulada “Referências cruzadas”- Algoritmo da PDDE — a estrutura das simulações forward/backward e a condição final que este capítulo generaliza para um grafo
- Gerenciamento de cortes — o conjunto de cortes somente de acréscimo (append-only) que este capítulo generaliza do nível de estágio para o nível de nó
- Formulação da taxa de desconto — o fator de desconto por estágio referido na §3
- Geração de cenários — o conjunto de aberturas dentro do nó referido na §2
- Modos de horizonte — a variante cíclica do grafo reservada na §5
- Arquivos de estágios — a referência campo a campo de
stages.jsonpara a forma de nós/transições introduzida conceitualmente na §1 - Configuração — como um estudo escolhe entre uma simulação enumerada e uma amostrada (§6)
- Glossário — definições dos termos nó, transição e grafo da política
Referências
Seção intitulada “Referências”Consulte a Bibliografia completa para todas as fontes citadas na metodologia.