Pular para o conteúdo

Gerenciamento de cortes

Este capítulo define o ciclo de vida completo dos cortes de Benders no Novo Modelo: o que os cortes representam matematicamente, como os coeficientes dos cortes se relacionam com as variáveis duais do PL, como os cortes por cenário são agregados em um corte único, sob quais condições os cortes são válidos e quais métodos de seleção estão disponíveis para controlar o crescimento do conjunto de cortes.

Para a visão por entidade deste capítulo, veja Valor da água e custo futuro.

Um corte de Benders no estágio t−1t-1 é uma desigualdade linear que fornece um limite inferior para a função de custo futuro Vt(x)V_t(x) sob as condições de validade da §4:

θ≥β0+β⊤x\theta \geq \beta_0 + \beta^{\top} x

onde:

  • θ\theta é a variável de custo futuro no PL do estágio t−1t-1
  • β0\beta_0 é o termo independente do corte
  • xx é o vetor das componentes do estado sobre as quais o corte se projeta, e β\beta o vetor dos respectivos coeficientes do corte, um por componente
  • βhv\beta^v_h é o coeficiente de armazenamento da hidrelétrica hh (valor marginal da água)
  • βh,ℓlag\beta^{lag}_{h,\ell} é o coeficiente da defasagem AR da hidrelétrica hh, defasagem ℓ\ell (valor marginal da tendência hidrológica)
  • vhv_h, ah,ℓa_{h,\ell} são as variáveis de estado de armazenamento e de defasagem AR (veja Aumento do espaço de estados §1)

O corte tem um coeficiente para cada dimensão de estado habilitada: o armazenamento vhv_h e as defasagens de afluência ah,ℓa_{h,\ell}, quando a seleção de projeção do estágio as mantém (Aumento do espaço de estados §7), e as parcelas de água em trânsito (in-transit buckets) e as posições do anel de despacho antecipado (commitment ring slots), quando presentes, sempre. Um corte é armazenado de forma densa sobre as componentes nas quais se projeta: cada uma dessas componentes tem um coeficiente em todo corte, calculado a partir da resolução (§2), e um coeficiente pode ser zero. No PL do estágio, a linha do corte tem os termos de armazenamento, das parcelas de água em trânsito e das posições do anel como coeficientes nas colunas de saída e avalia os termos das defasagens de afluência no seu lado direito, porque as defasagens de afluência não são colunas do PL (Folding do PAR(p) §3); a linha omite as entradas cujo coeficiente é estruturalmente zero.

O Novo Modelo acrescenta cortes de forma monotônica ao longo das iterações: um corte ativo nunca é removido do PL do limite inferior durante uma execução de treinamento (training). Como o conjunto de cortes só cresce, a estimativa do limite inferior é não decrescente ao longo das iterações de uma execução de treinamento. Trata-se de uma garantia em nível metodológico — a aproximação externa da função de valor só pode se tornar mais justa a cada iteração.

Depois de resolver o subproblema do estágio tt para o estado visitado x^t−1\hat{x}_{t-1} e o cenário ωt\omega_t, os coeficientes do armazenamento, das parcelas de água em trânsito e das posições do anel de despacho antecipado são obtidos dos custos reduzidos do PL nas colunas de estado de entrada fixadas — as colunas cujos limites inferior e superior foram igualados ao valor do estado de entrada (veja Aumento do espaço de estados §2). As defasagens de afluência não são colunas do PL, e seus coeficientes vêm dos duais da resolução pela regra da cadeia (abaixo).

Uma variável do PL do estado de entrada é fixada no valor visitado por limites de coluna iguais, e o custo reduzido dessa coluna fornece diretamente o coeficiente do corte:

Coluna fixadaCusto reduzidoCoeficiente do corteUnidade
Armazenamento de entrada (hidrelétrica hh)cˉhin\bar{c}^{in}_hβt,hv=cˉhin/dhcol\beta^v_{t,h} = \bar{c}^{in}_h / d^{col}_hR$/hm³

onde dcold^{col} é o fator de pré-escalonamento por coluna que desfaz o escalonamento do custo reduzido; um fator adicional KK converte para as unidades de custo originais na fronteira de relatório (veja Estrutura e escalonamento do PL §2). Quando o estudo tem água em trânsito ou térmicas com antecipação de despacho, cada coluna de entrada de uma parcela de água em trânsito e cada coluna de entrada de uma posição do anel de despacho antecipado contribui com um coeficiente pela mesma regra; o coeficiente multiplica a coluna de saída correspondente do estágio do corte (Aumento do espaço de estados §3; Aumento do espaço de estados — Coeficiente de corte das posições do anel de despacho antecipado).

Coeficientes das defasagens de afluência. As defasagens de afluência de entrada chegam ao PL do estágio somente pelos lados direitos: pela afluência realizada z^h\hat{z}_h, que o balanço hídrico e as demais linhas que leem a afluência tomam como constante (Folding do PAR(p) §2), e pelos termos de defasagem das linhas de corte. O coeficiente βt,h,ℓlag\beta^{lag}_{t,h,\ell}, em R$/(m³/s), é a derivada de QtQ_t ao longo dos dois caminhos, calculada a partir dos duais desescalonados das linhas pela regra da cadeia (Folding do PAR(p) §4). Em aritmética exata, é igual ao custo reduzido da coluna de defasagem fixada da formulação que escreve o modelo PAR(p) como linhas do PL (Folding do PAR(p) §5).

O termo independente do corte garante que o corte passe pelo estado visitado:

β0,t=Qt(x^t−1,ωt)−βt⊤x^t−1\beta_{0,t} = Q_t(\hat{x}_{t-1}, \omega_t) - \beta_t^{\top} \hat{x}_{t-1}

onde Qt(x^t−1,ωt)Q_t(\hat{x}_{t-1}, \omega_t) é o valor ótimo da função objetivo do subproblema do estágio tt, e o produto βt⊤x^t−1\beta_t^{\top} \hat{x}_{t-1} percorre as componentes sobre as quais o corte se projeta (§1), cada coeficiente pareado com o valor visitado de sua própria componente: armazenamento e defasagens de afluência quando o estágio as mantém, parcelas de água em trânsito e posições do anel de despacho antecipado sempre. Uma componente que o corte elimina na projeção não contribui com termo no produto; seu termo linear no valor visitado é incorporado ao termo independente (§4, condição 4). O estado visitado x^t−1\hat{x}_{t-1} no qual esse termo independente se ancora é o estado de saída canonicalizado (relido e limitado) da resolução forward do estágio anterior — o primal do PL projetado sobre seus limites admissíveis —, de modo que as colunas de estado de entrada fixadas e o termo independente compartilham uma mesma âncora dentro da caixa (veja Algoritmo da PDDE §3.1).

Convenção de sinais: pela dualidade em PL, o valor ótimo QtQ_t é convexo e linear por partes no estado de entrada, e o vetor β\beta lido em uma base ótima é um subgradiente dele em x^\hat{x}: Qt(x)≥Qt(x^)+β⊤(x−x^)Q_t(x) \geq Q_t(\hat{x}) + \beta^\top (x - \hat{x}) para todo estado de entrada xx. Onde QtQ_t é diferenciável em x^\hat{x}, βj=∂Qt/∂x^j\beta_j = \partial Q_t / \partial \hat{x}_j; onde o PL do estágio tem várias soluções duais ótimas, QtQ_t pode ter uma quebra (um ponto não diferenciável) em x^\hat{x}, e β\beta é o subgradiente dado pela base final. Para uma coluna fixada em x‾j=xˉj=x^j\underline{x}_j = \bar{x}_j = \hat{x}_j, o custo reduzido é a componente jj desse subgradiente — igual, pela paridade KKT, ao multiplicador que a restrição de igualdade equivalente xjin=x^jx^{in}_j = \hat{x}_j teria —, de modo que o coeficiente do corte é tomado diretamente do custo reduzido, sem inversão de sinal (após o desfazimento do escalonamento por coluna descrito acima). O custo reduzido captura automaticamente todos os efeitos a jusante: para o armazenamento, isso inclui as contribuições do balanço hídrico, dos hiperplanos da FPHA, da restrição de evaporação e de quaisquer restrições genéricas que referenciem a variável de armazenamento de entrada vhinv^{in}_h (veja Formulação do PL). Para uma defasagem de afluência, a regra da cadeia soma os efeitos ao longo dos dois caminhos pelos quais a defasagem chega ao PL: as linhas que leem a afluência realizada e os termos de defasagem das linhas de corte.

Sinal do coeficiente de armazenamento: mais armazenamento de entrada reduz QtQ_t sempre que a água adicional desloca geração térmica ou déficit, neste estágio ou em um posterior, de modo que o coeficiente de armazenamento é não positivo nesses casos; ele pode tornar-se positivo quando a água adicional só pode deixar o reservatório a um custo, como um custo de vertimento ou uma penalidade por limite de vazão defluente.

Dimensão do corte: o subconjunto de estados habilitados

Seção intitulada “Dimensão do corte: o subconjunto de estados habilitados”

Os cortes de cada estágio se projetam sobre as componentes do estado que a seleção do estágio mantém — o armazenamento e as defasagens de afluência conforme cada estágio os seleciona, as parcelas de água em trânsito e as posições do anel de despacho antecipado sempre —, conforme definido em Aumento do espaço de estados §7.

Em uma execução com vários processos (ranks MPI), a sincronização de cortes de cada estágio deriva seu leiaute de transmissão da própria dimensão de corte desse estágio. A aba Configurar, em Implementação no Novo Modelo, lista o campo por estágio.

Na formulação de corte único (single-cut), os cortes por resultado da simulação backward são agregados em um único corte por estado visitado. O corte de um nó nn do grafo da política (policy graph) (Grafos da política) agrega sobre os pares (n′,ω)(n', \omega) formados por todo filho n′n' de nn e toda abertura ω∈Ωn′\omega \in \Omega_{n'} desse filho, cada par ponderado pelo produto P(n→n′) pn′(ω)P(n \to n')\, p_{n'}(\omega) da probabilidade de transição de nn para n′n' pela probabilidade da abertura ω\omega dentro de n′n'. Sob a esperança, o corte agregado é a esperança dos cortes por par sob essa lei conjunta:

βˉ0=∑(n′,ω)P(n→n′) pn′(ω) β0(n′,ω)\bar{\beta}_0 = \sum_{(n', \omega)} P(n \to n')\, p_{n'}(\omega)\, \beta_0(n', \omega) βˉ=∑(n′,ω)P(n→n′) pn′(ω) β(n′,ω)\bar{\beta} = \sum_{(n', \omega)} P(n \to n')\, p_{n'}(\omega)\, \beta(n', \omega)

onde β0(n′,ω)\beta_0(n', \omega) e β(n′,ω)\beta(n', \omega) são o termo independente e o vetor de coeficientes do corte lidos do subproblema do filho n′n' sob a abertura ω\omega no estado visitado (§2). A soma dos coeficientes é uma soma vetorial sobre todas as componentes nas quais o corte se projeta (§1): o armazenamento e as defasagens de afluência quando a projeção os mantém, e as parcelas de água em trânsito e as posições do anel de despacho antecipado sempre. Sob uma medida de risco, os produtos P(n→n′) pn′(ω)P(n \to n')\, p_{n'}(\omega) são substituídos pelas probabilidades ajustadas ao risco de Medidas de risco, calculadas sobre essa mesma lei conjunta: a medida de risco do estágio do nó nn atua uma única vez sobre todos os pares em conjunto, nunca sobre as aberturas de cada filho separadamente com a posterior média dos resultados entre os filhos.

Na cadeia de estágios, todo nó que não é folha tem um único filho, alcançado com probabilidade 11, de modo que os pares são as aberturas ω∈Ωt\omega \in \Omega_t do estágio tt e seus pesos são os uniformes p(ω)p(\omega): a agregação percorre as aberturas de um único estágio.

O corte agregado (βˉ0,βˉ)(\bar{\beta}_0, \bar{\beta}) é adicionado ao conjunto de cortes do nó nn, que na cadeia de estágios é o conjunto de cortes do estágio t−1t-1.

Um corte é válido se for um limite inferior da verdadeira função de custo futuro em todo o espaço de estados viável:

β0,i+βi⊤x≤Vt+1(x)∀x∈Xt\beta_{0,i} + \beta_i^\top x \leq V_{t+1}(x) \quad \forall x \in \mathcal{X}_t

Aqui, βi\beta_i é lido como zero em toda componente que o corte elimina na projeção, de modo que o corte é constante nessas componentes.

Condições de validade: os cortes gerados pela PDDE são válidos sob:

  1. Convexidade do custo futuro em relação ao estado de entrada — o estado de entrada entra de forma afim em cada problema de estágio, pelos limites de suas colunas fixadas; a Camada 1 indica o que viola essa condição.
  2. Recurso relativamente completo — viabilidade para todos os estados e cenários. No Novo Modelo, o sistema de folgas de recurso (penalidades da Categoria 1) o proporciona em todo caso que atende à precondição de recurso completo.
  3. Extração correta das sensibilidades — os custos reduzidos e os duais das linhas que fornecem os coeficientes do corte devem provir de uma solução ótima do PL (e não de uma inviável ou ilimitada)
  4. Cortes abrangem todas as componentes do estado das quais o custo futuro depende — o termo independente absorve a contribuição de toda componente que o corte elimina na projeção (Aumento do espaço de estados §7), em seu valor visitado, de modo que só se garante que o corte fique abaixo do custo futuro na fatia que passa pelo estado visitado na qual essas componentes mantêm seus valores visitados. Quando o custo futuro depende de uma dessas componentes, como depende das defasagens de afluência sob um modelo PAR com termos de defasagem, não há garantia de que z‾k\underline{z}^k seja um limite inferior, e o gap não é um certificado.

Três garantias se associam aos limites que a PDDE informa, cada uma sob suas próprias hipóteses: um limite inferior válido, a convergência desse limite e um certificado sobre o gap entre os dois limites. As Camadas 2 e 3 exigem, cada uma, a Camada 1. A tabela resume os três graus; as subseções enunciam cada hipótese e o que a viola.

CamadaO que valeRequerViolado por
1. Limite inferior válidoz‾k\underline{z}^k é no máximo o valor ótimo do modelo tal como treinadoUm custo futuro convexo em relação ao estado de entrada e não negativo; recurso relativamente completo; cortes exatos em seus estados visitados e abrangendo todas as componentes do estado das quais o custo futuro depende; uma função terminal fixaUm método de não negatividade das afluências por truncamento em um modelo PAR com termos de defasagem; um corte que omite uma componente do estado da qual o custo futuro depende; um custo futuro que assume valores negativos
2. Convergênciaz‾k\underline{z}^k converge para esse valor ótimo com probabilidade 1 sob uma medida de esperança em todos os estágiosCamada 1; um número finito de aberturas em todo nó; uma simulação forward que amostra os caminhos de cenários da simulação backward ou os enumera; uma seleção que preserva a aproximação em todo estado visitadoUma simulação forward que sorteia de outra distribuição; a seleção de cortes Nível 1 (Level-1) tal como o Novo Modelo a executa; um limite por estágio de cortes ativos; um k1k_1 finito
3. Certificado do gapzˉk−z‾k\bar{z}^k - \underline{z}^k limita o gap de otimalidade da políticaCamada 1; um limite superior exato sobre a mesma árvore e sob a mesma medida: uma simulação forward enumerada e uma medida uniforme entre os estágiosUm limite superior amostrado, fora da amostra (out-of-sample), histórico ou externo; uma medida que varia entre os estágios

Em toda iteração kk, z‾k\underline{z}^k é no máximo o valor ótimo do modelo tal como treinado, sob o objetivo aninhado ajustado ao risco de Medidas de risco. Ele se apoia nas seguintes hipóteses:

  • Convexidade. O custo futuro de todo estágio é convexo em relação ao estado de entrada: o estado de entrada entra de forma afim em cada problema de estágio, pelos limites de suas colunas fixadas e, no caso das defasagens de afluência, pelos lados direitos das linhas que leem a afluência realizada e das linhas de corte. Os métodos de truncamento de Métodos de tratamento de afluências negativas §7 violam essa propriedade nas componentes de defasagem de afluência sob um modelo PAR com termos de defasagem (ordem acima de zero ou componente anual), porque a correção que aplicam, o montante truncado max⁡(0,−ah)\max(0, -a_h) da realização bruta aha_h, é uma função não afim da realização e, portanto, das defasagens do estado visitado; manter as componentes de defasagem no corte não restaura a propriedade. Cada corte fica abaixo do problema de estágio com a correção congelada em seu próprio estado visitado, mas, longe desse ponto, pode ficar acima do custo futuro, e o limite inferior pode exceder o limite superior. Sem método de não negatividade, ou com o método de penalidade, a afluência permanece afim nas defasagens.
  • Recurso relativamente completo. Todo problema de estágio é viável para todo estado de entrada e toda realização, o que as folgas penalizadas de Sistema de penalidades proporcionam sob a sua precondição de recurso completo.
  • Cortes exatos. Todo corte é exato em seu estado visitado e fica abaixo do custo futuro ajustado ao risco em todo ponto: a simulação backward resolve até a otimalidade o problema de estágio de todo par sucessor–abertura e combina os cortes resultantes com probabilidades do conjunto de risco da medida de risco coerente do estágio que atingem essa medida no estado visitado.
  • Abrangência completa do estado. Os cortes abrangem todas as componentes do estado das quais o custo futuro depende. Quando uma componente da qual o custo futuro depende é eliminada na projeção do corte (Aumento do espaço de estados §7), só se garante que o corte fique abaixo do custo futuro onde essa componente é igual ao seu valor visitado. Em um estudo cujos períodos de defasagem abrangem vários estágios, o custo futuro dentro de um período aberto também depende da soma parcial do período, que não é componente do estado, de modo que só se garante que os cortes fiquem abaixo dele onde essa soma parcial é a mesma em todos os caminhos (Estudos com múltiplas resoluções §2.1).
  • Custo futuro não negativo. O custo futuro de todo estágio é não negativo. A variável de custo futuro θ\theta é limitada inferiormente por zero, de modo que a aproximação só fica abaixo do custo futuro onde esse custo futuro é não negativo.
  • Função terminal fixa. A função terminal é fixa durante toda a execução: zero, ou uma fronteira terminal importada (Fronteira pós-estudo e estudos encadeados).

Sob uma medida de esperança em todos os estágios, z‾k\underline{z}^k converge com probabilidade 1 para o valor ótimo do modelo tal como treinado. Isso requer as hipóteses abaixo; a §9 enuncia o teorema, que é demonstrado para esse caso. Sob uma medida avessa ao risco em qualquer estágio, a Camada 1 ainda limita inferiormente o valor ótimo, mas o teorema citado não estabelece a convergência de z‾k\underline{z}^k.

  • A Camada 1 vale, e todo nó tem um número finito de aberturas.
  • A simulação forward sorteia os próprios caminhos de cenários da simulação backward, cada um com probabilidade positiva, ou os enumera. Uma simulação forward que sorteia de outra distribuição, como ruído fora da amostra, registros históricos ou cenários externos, está fora das hipóteses do teorema.
  • A seleção mantém a aproximação que o teorema da §9 pressupõe: nenhuma seleção, ou o método dinâmico da §8 com todo corte ativo como candidato, k1=∞k_1 = \infty, cujas resoluções retornam o ótimo sobre os cortes ativos a menos da tolerância de violação da §8.1.

Três características da seleção de cortes desta página saem da última hipótese:

  • A seleção Nível 1 (§7), tal como o Novo Modelo a executa, afasta-se da regra coberta pelo teorema (§9): é executada a cada nseln_{\text{sel}} iterações, deixa sem seleção o conjunto de cortes do primeiro estágio e, com uma janela ww, avalia os cortes apenas nos estados visitados das últimas ww iterações. Nenhum resultado de convergência é reivindicado para ela.
  • Um limite por estágio no número de cortes ativos (§5) desativa os cortes que estiveram ativos na solução há mais tempo, assim que o limite é excedido, qualquer que seja seu valor nos estados visitados armazenados; apenas os cortes da iteração corrente e os cortes carregados ficam isentos.
  • Com um k1k_1 finito (§8.2), o método dinâmico nunca avalia um corte gerado k1k_1 ou mais iterações antes, de modo que seu laço pode terminar deixando de fora um corte antigo violado.

zˉk−z‾k\bar{z}^k - \underline{z}^k limita superiormente o gap de otimalidade da política, a diferença entre o custo ajustado ao risco da política e o valor ótimo. Isso requer a Camada 1 e um limite superior exato sobre a mesma árvore e sob a mesma medida: uma simulação forward enumerada, que avalia a política em todos os caminhos da árvore usada pela simulação backward, e uma medida uniforme entre os estágios, seja a esperança em todos os estágios, seja uma mesma medida CVaR, com o mesmo peso de aversão ao risco e a mesma fração da cauda, em todos os estágios; um estágio cujo peso de aversão ao risco é zero corresponde à esperança, qualquer que seja sua fração da cauda. Uma estimativa amostrada, fora da amostra, histórica ou externa não é um certificado: ela carrega erro amostral ou avalia outra distribuição, e pode ficar abaixo de z‾k\underline{z}^k. Veja Gap de otimalidade para o gap e Avaliação do limite superior para o limite exato.

5. Crescimento dos cortes e motivação para a seleção

Seção intitulada “5. Crescimento dos cortes e motivação para a seleção”

O número de cortes cresce como O(iterations×Nforward_passes)\mathcal{O}(\text{iterations} \times N_{\text{forward\_passes}}). Muitos cortes antigos tornam-se redundantes à medida que cortes novos e mais justos são gerados. Sem seleção, o número de linhas de corte no PL cresce linearmente com o número de iterações.

Conjunto somente de acréscimo com posições estáveis: os cortes nunca são apagados. Todo corte já gerado é mantido durante toda a execução em um índice de posição estável e determinístico — a posição é uma função fixa da iteração e do índice da simulação forward, o que torna a ordem dos cortes reproduzível entre execuções e números de processos (veja Determinismo e rastreabilidade). O conjunto nunca é compactado.

Mecanismo de desativação (seleção Nível 1 e limite de cortes ativos): a desativação é um indicador de atividade no conjunto, associado a uma posição estável — não altera nenhuma linha nem limite do PL. Um corte desativado mantém sua posição, mas é excluído da reconstrução do modelo-base (template) a cada iteração, de modo que apenas os cortes ativos são codificados como linhas do PL em cada resolução forward/backward. O PL persistente do limite inferior é somente de acréscimo: suas linhas de corte nunca são removidas (de modo que o limite inferior permanece monotônico), e cada linha continua restringindo depois de acrescentada. Como o índice de posição é preservado, a reativação é exata: um corte que a seleção restaura posteriormente é reincorporado ao modelo-base na mesma posição, com os coeficientes com que foi gerado.

Há dois métodos de seleção disponíveis. A seleção Nível 1 (§7) executa uma passagem de posse a cada nseln_{\text{sel}} iterações: mantém os cortes que detêm a posse de um estado visitado armazenado e desativa os demais. O método dinâmico (§8) mantém o conjunto inteiramente somente de acréscimo — nunca desativa nenhum corte — e, em vez disso, controla quais cortes estão residentes em cada resolução individual do PL do estágio.

Limite de cortes ativos: um limite BB no número de cortes ativos gerados pela execução corrente no conjunto de cada nó estritamente entre o primeiro e o último estágio. Ele se aplica em toda iteração, depois que os cortes da iteração são adicionados e depois da passagem Nível 1, quando houver, com ou sem método de seleção. Quando a contagem excede BB, o excedente é removido dentre os cortes de iterações anteriores, em ordem crescente da iteração em que o corte esteve ativo na solução pela última vez (um corte que nunca esteve ativo na solução conta a partir da iteração que o gerou), depois do número de resoluções em que esteve ativo na solução e, por fim, da posição. Os cortes da iteração corrente contam para BB e nunca são removidos, e os cortes carregados não contam nem são removidos, de modo que um conjunto pode conter mais de BB cortes ativos. A remoção desativa o corte e o mantém no conjunto; uma passagem Nível 1 posterior reativa um corte removido que detém a posse de um estado visitado armazenado, e o limite é então aplicado novamente na mesma iteração. O limite não é admitido com o método dinâmico, que nunca reativa um corte, nem com uma simulação forward enumerada, que não registra atividade na solução.

A seleção Nível 1 trabalha a partir de uma visão de atividade por avaliação de valor. Em um estado visitado armazenado x^\hat{x} de um conjunto, o valor de cada corte é β0,i+βi⊤x^\beta_{0,i} + \beta_i^\top \hat{x}, e o melhor valor por estado é

V∗(x^)=max⁡i∈L{β0,i+βi⊤x^}V^*(\hat{x}) = \max_{i \in \mathcal{L}} \left\{ \beta_{0,i} + \beta_i^\top \hat{x} \right\}

tomado sobre os cortes vivos L\mathcal{L} do conjunto: todo corte avaliado — os cortes cujo próprio estado visitado o conjunto armazenou quando foram gravados, ativos e inativos — e todo corte carregado sem estado visitado armazenado enquanto estiver ativo. O corte vivo que atinge V∗(x^)V^*(\hat{x}) detém a posse de x^\hat{x}; quando vários o atingem exatamente, o corte na posição mais baixa detém a posse. Os valores são comparados exatamente, sem faixa de tolerância:

owner(x^)=min⁡{i∈L:β0,i+βi⊤x^=V∗(x^)}\text{owner}(\hat{x}) = \min \left\{ i \in \mathcal{L} : \beta_{0,i} + \beta_i^\top \hat{x} = V^*(\hat{x}) \right\}

Um corte no máximo por estado é aquele sobre o qual a variável de custo futuro θ\theta repousa em x^\hat{x}, de modo que um corte que detém a posse de um estado é a contrapartida, na avaliação de valor, de um corte ativo na solução nesse ponto. Como a ordem das posições segue a ordem de geração, a posição mais baixa é a do mais antigo dos cortes empatados: manter apenas o mais antigo dos cortes empatados é a regra do Nível 1 com memória limitada (Limited-Memory Level 1, LML1) de Guigues (2017).

Estar ativo em uma solução do PL é uma grandeza diferente: uma linha de corte está ativa na solução de uma resolução quando seu multiplicador dual excede um limiar (§10). Esse registro é lido apenas pelo limite de cortes ativos (§5) e pela janela de semeadura do método dinâmico (§8.1); não tem papel algum na posse.

A seleção Nível 1 segue o Nível 1 de de Matos, Philpott & Finardi (2015), com a regra de desempate do Nível 1 com memória limitada (Guigues, 2017): cada estado visitado armazenado tem um único detentor (§6), e uma execução da seleção mantém os cortes que detêm a posse de algum estado. Ela avalia o conjunto de cortes de todo nó estritamente entre o primeiro e o último estágio; o conjunto do primeiro estágio e o conjunto final compartilhado nunca passam por seleção.

A regra. A cada nseln_{\text{sel}} iterações, após a simulação backward:

  • Um corte avaliado que detém a posse de pelo menos um estado armazenado fica ativo; um corte avaliado que não detém a posse de nenhum é desativado e mantido no conjunto.
  • Um corte avaliado inativo que detém a posse de um estado é reativado, de modo que desativação e reativação são simétricas dentro de uma mesma passagem.
  • Um corte da iteração corrente é julgado como qualquer outro: não há isenção.
  • Um corte carregado sem estado visitado armazenado mantém a atividade com que foi carregado; enquanto ativo, disputa a posse e pode manter inativo um corte empatado em posição mais alta.

Nenhum valor de corte é comparado com uma tolerância, de modo que o conjunto ativo após uma passagem é função apenas dos estados armazenados e dos coeficientes dos cortes. A passagem é determinística bit a bit, independentemente do número de threads e de processos (veja Determinismo e rastreabilidade).

Estados armazenados e a janela. Todo corte que a execução gera em um conjunto sujeito a seleção é avaliado: o conjunto armazena o estado visitado no qual o corte foi calculado. Um corte carregado é avaliado quando a política da qual provém o registra assim, e então disputa a posse nos estados armazenados, incluindo seu próprio estado armazenado quando a política o contém. Por padrão, uma execução mantém os estados visitados de toda a execução, de modo que a memória que ocupam cresce com o número de cortes. Com uma janela de ww iterações, uma execução da seleção na iteração kk mantém apenas os estados visitados dos cortes gerados após a iteração k−wk - w e descarta os mais antigos; um estado carregado com um corte de outra execução conta como anterior à primeira iteração da execução. A janela é de pelo menos nseln_{\text{sel}}, de modo que todo estado é avaliado ao menos uma vez antes de poder ser descartado. Uma janela descarta estados, nunca cortes: um corte cujo estado foi descartado continua avaliado e ainda disputa a posse nos estados que restam.

Propriedade da envoltória. Logo após uma execução da seleção na qual o limite de cortes ativos não remove nada, o detentor de todo estado armazenado está ativo, de modo que os cortes ativos do conjunto atingem V∗(x^)V^*(\hat{x}) em todo estado armazenado. Um estado armazenado após a execução pode ter como detentor um corte inativo até a próxima execução, e o limite, aplicado após a passagem, pode desativar um corte que detém a posse de estados; a passagem seguinte o reativa.

Diferenças em relação ao artigo.

  1. O conjunto do primeiro estágio nunca passa por seleção.
  2. A seleção é executada a cada nseln_{\text{sel}} iterações, e não toda vez que um corte é adicionado.
  3. O artigo não define regra para um empate exato; a posição mais baixa, a do mais antigo dos cortes empatados, é a regra do LML1 (Guigues, 2017).

Custo: O(∣new cuts∣×∣stored states∣+∣cuts∣×∣new states∣)\mathcal{O}(|\text{new cuts}| \times |\text{stored states}| + |\text{cuts}| \times |\text{new states}|) multiplicações-adições por conjunto e passagem: o registro de posse é atualizado incrementalmente, avaliando os cortes e estados gravados desde a passagem anterior contra os demais, como um produto de matrizes em blocos.

O método dinâmico é a geração preguiçosa de linhas própria do Novo Modelo; não é a Seleção Dinâmica de Cortes (Dynamic Cut Selection) de de Matos, Philpott & Finardi (2015). Ele é mutuamente exclusivo com a seleção Nível 1 e é inadmissível com uma simulação forward enumerada: a combinação é rejeitada na preparação do estudo com um erro de validação nomeado, cujo motivo é dado na aba Notas de implementação, em Implementação no Novo Modelo. Ele nunca desativa cortes do conjunto — mantém o conjunto inteiramente somente de acréscimo e controla apenas quais cortes estão residentes em cada PL do estágio no momento da resolução.

Motivação: quando o conjunto de cortes de um estágio é grande, resolver cada PL do estágio com todos os cortes ativos domina o tempo de execução. O método dinâmico mantém o conjunto inteiro e resolve cada PL com um pequeno subconjunto residente dele, ampliado até que nenhum corte candidato seja violado na solução, de modo que uma resolução retorna o ótimo sobre seus candidatos a menos da tolerância de violação; quando todo corte ativo é candidato (§8.2), esse é o ótimo com todos os cortes ativos. Ele só pode ser combinado com uma simulação forward amostrada, como impõe a verificação de preparação acima.

A partir da iteração em que o laço preguiçoso começa, cada resolução do treinamento para um (estágio, cenário) executa este laço; antes dela, as resoluções contêm todos os cortes ativos.

  1. Semear o conjunto residente com os cortes ativos cuja última atividade na solução ocorreu há no máximo k2k_2 iterações (a janela de semeadura; um corte que ainda não esteve ativo na solução conta a partir da iteração que o gerou), mais todo corte gerado na iteração corrente. A semente é derivada apenas de metadados sincronizados do conjunto, por posição — a iteração em que cada corte esteve ativo na solução pela última vez e a iteração em que foi gerado —, nunca de um registro de resolução por worker. Isso torna a semente idêntica bit a bit para qualquer número de threads e de processos MPI.

  2. Resolver o PL do estágio com o conjunto residente corrente. Sejam x∗x^* os valores ótimos das colunas de estado de saída e θ∗\theta^* o valor ótimo do custo futuro.

  3. Avaliar os cortes candidatos omitidos (não residentes). Os coeficientes dos cortes são armazenados no espaço bruto (sem escalonamento), enquanto o PL é resolvido no espaço escalonado, de modo que tanto θ∗\theta^* quanto cada coluna de estado precisam primeiro ter o escalonamento desfeito: cada valor escalonado xscaledx_{\text{scaled}} é multiplicado pelo fator de escalonamento de sua coluna, o dcold^{col} da §2, resultando em xrawx_{\text{raw}}. Para o corte candidato ii com lado direito RiR_i, que contém seu termo independente e seus termos de defasagem de afluência (Folding do PAR(p) §3), e coeficientes βi\beta_i nas colunas de estado de saída, o piso de custo futuro que ele imporia em x∗x^* é

    fi=Ri+βi⊤xraw∗f_i = R_i + \beta_i^\top x^*_{\text{raw}}

    O candidato é violado se, e somente se,

    fi−θraw∗>εviol⋅max⁡(∣θraw∗∣,∣fi∣)f_i - \theta^*_{\text{raw}} > \varepsilon_{\text{viol}} \cdot \max\left(\lvert \theta^*_{\text{raw}} \rvert, \lvert f_i \rvert\right)

    (estrito), com εviol∈(0,1)\varepsilon_{\text{viol}} \in (0, 1) uma tolerância relativa. Isso decorre da convenção da linha de corte θ−β⊤x≥Ri\theta - \beta^\top x \ge R_i.

  4. Adicionar os nadicn_{\text{adic}} candidatos mais violados (ordenados por fi−θraw∗f_i - \theta^*_{\text{raw}} decrescente, com empates desfeitos pelo id de posição crescente). Resolver novamente, a partir da base mantida quando a fase usa aproveitamento de base (§8.4), e voltar ao passo 2.

  5. Parar quando nenhum candidato for violado. A resolução só retorna então, de modo que seu objetivo zRz_R e o ótimo zCz_C sobre o conjunto de candidatos satisfazem zR≤zC≤zR+d εviol1−εviol ∣θ∗∣z_R \le z_C \le z_R + d\,\frac{\varepsilon_{\text{viol}}}{1 - \varepsilon_{\text{viol}}}\,\lvert \theta^* \rvert, sendo dd o coeficiente de θ\theta no objetivo. Os duais da simulação backward e os primais da simulação forward são extraídos desse PL final.

Por padrão, todo corte ativo é candidato (k1=∞k_1 = \infty), de modo que a janela não exclui nenhum corte e a saída do passo 5 é o ótimo sobre todos os cortes ativos, a menos da tolerância de violação. Um k1k_1 finito restringe os candidatos aos cortes gerados nas últimas k1k_1 iterações e aos cortes carregados. Trata-se de uma aceleração deliberada e inexata: o resultado passa a ser o ótimo sobre esses candidatos junto com a semente, e um corte mais antigo nunca é avaliado nem adicionado, mesmo quando violado.

Rodadas que adicionam no máximo nadicn_{\text{adic}} cortes cada são executadas até um número fixo de rodadas. Além dele, o limite por rodada é suspenso: todo candidato violado é adicionado em cada rodada, e o laço continua terminando apenas na parada do passo 5 da §8.1. O laço termina porque todo candidato reportado passa a ser residente, de modo que cada rodada reduz o conjunto finito de candidatos omitidos.

8.4 Uniformidade entre simulações e sinergia com o aproveitamento de base

Seção intitulada “8.4 Uniformidade entre simulações e sinergia com o aproveitamento de base”

O laço é executado na simulação backward e na simulação forward do treinamento, e em ambas vai até a parada do passo 5 da §8.1 — sem parada antecipada — para evitar deriva de trajetória: uma parada antecipada na simulação forward deslocaria os estados que a simulação backward visita, produzindo deriva da política. Uma resolução da simulação final semeia o conjunto residente com todos os cortes ativos, de modo que as janelas k1k_1 e k2k_2 se aplicam apenas ao treinamento.

Em uma fase com aproveitamento de base, cada nova resolução interna acrescenta apenas algumas linhas e recomeça a partir da base deixada pela resolução anterior, de modo que o laço limitado permanece barato; em uma fase sem aproveitamento de base, toda nova resolução interna também parte a frio (Aproveitamento de base do PL). A base armazenada de Aproveitamento de base do PL não é aplicada a uma resolução do método dinâmico: a primeira resolução de cada PL do estágio começa sem base armazenada e, em uma simulação backward com aproveitamento de base, as aberturas seguintes de um estado visitado são resolvidas a quente a partir do PL deixado pela abertura anterior.

Uma janela de semeadura k2=0k_2 = 0 é válida e significativa: o conjunto residente é semeado com os cortes gerados na iteração corrente e com os que estiveram ativos na solução nela, e o laço preguiçoso então amplia o conjunto residente a partir daí em cada resolução. Um k2k_2 maior troca um PL inicial um pouco maior por menos iterações internas.

A seleção do conjunto residente é idêntica bit a bit para qualquer número de threads e de processos MPI:

  • A semente vem de metadados sincronizados do conjunto (a iteração em que cada corte esteve ativo na solução pela última vez e a iteração em que foi gerado), e não de registros por worker.
  • O estado ótimo x∗x^* é determinístico por cenário (função do PL, não do processo).
  • A avaliação dos candidatos usa um produto de matrizes em lote determinístico bit a bit.
  • A ordenação das violações usa uma ordem total com desempate por posição crescente, tornando estável a seleção dos nadicn_{\text{adic}} primeiros.

Veja Determinismo e rastreabilidade.

Teorema (Bandarra & Guigues, 2021): para um objetivo de esperança em todos os estágios, a PDDE com um número finito de cenários e seleção de cortes Nível 1 ou Nível 1 com Memória Limitada (Limited-Memory Level 1), aplicada em toda iteração e avaliada em todos os estados visitados, alcança uma solução ótima do primeiro estágio após um número finito de iterações com probabilidade 1.

Ideia central: remover cortes que nunca estão no máximo em nenhum estado visitado não altera a aproximação externa nesses pontos, e o argumento de convergência usa a aproximação apenas neles. Com um número finito de cenários, só pode surgir um número finito de cortes e estados visitados distintos, cada um lido de uma solução básica de um problema de estágio, de modo que o argumento não exige densidade dos estados visitados: a convergência é alcançada após um número finito de iterações.

A seleção Nível 1 tal como o Novo Modelo a executa resolve um empate exato como o LML1, mantendo o mais antigo dos cortes empatados (§6), e afasta-se da regra coberta pelo teorema de três maneiras: é executada a cada nseln_{\text{sel}} iterações, deixa sem seleção o conjunto do primeiro estágio e, com uma janela, avalia apenas os estados visitados dentro dela (§7). Nenhum resultado de convergência é reivindicado para ela, e de Matos, Philpott & Finardi (2015) não enunciam nenhum para o seu Nível 1.

O método dinâmico e a exatidão: uma resolução do método dinâmico retorna, no passo 5 da §8.1, o ótimo sobre seus candidatos a menos da tolerância relativa de violação. Com k1=∞k_1 = \infty, os candidatos são todos os cortes ativos e, como o método não desativa nenhum corte, os cortes ativos são o próprio conjunto, exceto os cortes carregados que uma execução de origem deixou inativos. Um k1k_1 finito sacrifica essa propriedade.

A Camada 2 enuncia as hipóteses sobre a medida de risco, a simulação forward e a seleção de cortes que uma execução de treinamento deve satisfazer para que o teorema se aplique, e as características da seleção que ficam fora delas.

A tabela associa cada chave do objeto training.cut_selection ao seu símbolo nesta página, quando houver, e aos métodos que a leem; training.cut_selection informa o tipo, o valor padrão e as restrições de cada chave.

Símbolo matemáticoChave de configuraçãoAplica-se a
—row_activity_toleranceO limite (§5) e dynamic (§8.1)
BBmax_active_per_stageNenhum método ou level1
nseln_{\text{sel}}selection.check_frequencylevel1
wwselection.lookback_iterationslevel1
k2k_2selection.seed_windowdynamic
k1k_1selection.candidate_recencydynamic
nadicn_{\text{adic}}selection.max_added_per_rounddynamic
εviol\varepsilon_{\text{viol}}selection.violation_tolerancedynamic
—selection.start_iterationdynamic

A metodologia acima define o ciclo de vida completo dos cortes de Benders; as abas abaixo mostram como a interface de software do Novo Modelo configura, persiste e gerencia os cortes em tempo de execução.

As configurações de gerenciamento de cortes do Novo Modelo ficam em dois lugares: o bloco training.cut_selection do config.json (gerenciamento de linhas) e o campo state_variables por estágio do stages.json (projeção dos cortes). O próprio conjunto de cortes é gerado durante o treinamento (training), e não informado pelo caso. Esta aba mostra como cada um é configurado; os algoritmos de seleção propriamente ditos permanecem nas seções da metodologia acima (§5–§9).

training.cut_selection — Configuração do gerenciamento de linhas

Seção intitulada “training.cut_selection — Configuração do gerenciamento de linhas”

O gerenciamento de linhas combina uma etapa de seleção, configurada pelo objeto selection e desligada por padrão, com uma etapa de orçamento por estágio definida por max_active_per_stage. O exemplo executa a seleção de cortes Nível 1 (Level-1) (level1) a cada 5 iterações, mantém os estados visitados das últimas 20 iterações e limita cada estágio intermediário a 500 linhas ativas geradas pela execução:

{
"training": {
"cut_selection": {
"row_activity_tolerance": 1e-6,
"max_active_per_stage": 500,
"selection": {
"method": "level1",
"check_frequency": 5,
"lookback_iterations": 20
}
}
}
}

training.cut_selection lista todos os campos, valores padrão e parâmetros de método, e as combinações recusadas na carga; Processo de gestão de cortes descreve a etapa de orçamento. Quais linhas a simulação pós-treinamento carrega é definido por uma chave separada, simulation.cut_set.

stages[].state_variables — Projeção dos cortes

Seção intitulada “stages[].state_variables — Projeção dos cortes”

Cada estágio do estudo seleciona sobre quais dimensões do estado de entrada seus cortes são projetados — a projeção do estado dos cortes de Aumento do espaço de estados §7.

CampoTipoPadrãoDescrição
storagebooleantrueProjeta os cortes sobre as dimensões de armazenamento.
inflow_lagsbooleanfalseProjeta os cortes sobre as dimensões de defasagem de afluência.

Com inflow_lags definido como true em um estágio, os cortes gerados nesse estágio também contêm os coeficientes das defasagens de afluência; com false, não contêm coeficientes de defasagem de afluência.

A ausência de state_variables resulta no padrão apenas com armazenamento, { "storage": true, "inflow_lags": false }; um campo desconhecido é rejeitado na carga. As parcelas de água em trânsito e as posições do anel de despacho antecipado são sempre projetadas e não têm campo.

Um estudo que fornece coeficientes AR de ordem acima de zero (scenarios/inflow_ar_coefficients.parquet), mas tem inflow_lags definido como false em todos os estágios do estudo, explicitamente ou por padrão, recebe um aviso de validação ModelQuality que não bloqueia a execução; um modelo PAR estimado a partir do histórico de vazões nunca gera esse aviso, porque a verificação é feita sobre a tabela fornecida, antes da estimação. Com as defasagens excluídas da projeção, as defasagens continuam dando a afluência realizada, mas nenhum corte gerado no treinamento contém seus coeficientes (cortes importados de uma política de fronteira podem conter).

Para manter as defasagens de afluência nos cortes gerados por um estágio, defina os dois campos nesse estágio:

"state_variables": { "storage": true, "inflow_lags": true }

A entrada stages[] completa está listada em stages.json.

  • Formulação do PL — Restrições de corte de Benders no PL
  • Aumento do espaço de estados — Fixação do estado por limites de coluna, cujos custos reduzidos fornecem os coeficientes dos cortes no armazenamento, nas parcelas de água em trânsito e nas posições do anel; projeção do estado do corte sobre as componentes do estado que cada estágio seleciona
  • Aproveitamento de base do PL — Aproveitamento da base armazenada nas resoluções dos estágios; uma resolução do método dinâmico não a aplica (§8.4)
  • Modelo de afluências PAR(p) — Variáveis de estado de defasagem AR que aparecem nos coeficientes dos cortes
  • Folding do PAR(p) — os termos de defasagem de afluência no lado direito dos cortes e seus coeficientes pela regra da cadeia
  • Algoritmo da PDDE — Estrutura das simulações forward/backward que conduz a geração de cortes
  • Geração de cenários — Árvore de aberturas fixa que define as ramificações da simulação backward; abstração do esquema de amostragem
  • Sistema de penalidades — Folgas de recurso e a precondição sob a qual elas dão recurso relativamente completo (condição de validade dos cortes)
  • Critérios de parada — Critérios de convergência que dependem da qualidade dos cortes
  • Formulação da taxa de desconto — Escala pelo fator de desconto na agregação dos cortes
  • Medidas de risco — Geração de cortes avessa ao risco (o CVaR modifica os pesos da agregação)
  • Variantes de formulação dos patamares — Estrutura de patamares que afeta como os duais por patamar contribuem para os coeficientes dos cortes
  • Determinismo e rastreabilidade — Resultados idênticos bit a bit para qualquer número de threads e de processos MPI, incluindo a semeadura do conjunto residente do método dinâmico
  • Executando o Novo Modelo: Gerenciamento da política — o guia de software para persistir e recarregar este conjunto de cortes entre execuções.