Pular para o conteúdo

Folding do PAR(p)

Cada PL do estágio depende do modelo de afluências PAR(p) (Modelo de afluências PAR(p)) pela afluência realizada de cada usina hidrelétrica: o modelo a calcula a partir das defasagens de afluência de entrada e do ruído da abertura, e o balanço hídrico e as linhas que leem a afluência a utilizam. Este capítulo descreve como o Novo Modelo mantém o modelo de afluências fora do PL do estágio, dobrando (folding) seus termos para dentro do lado direito das linhas, e como calcula os coeficientes dos cortes nas defasagens de afluência, que o PL não fornece nessa forma. O PL do estágio mantém o valor ótimo de cada resolução, e os cortes possíveis continuam os mesmos (§5).

A formulação expandida escreve o modelo de afluências dentro do PL do estágio. Para cada usina hidrelétrica hh, ela tem:

  • uma coluna por defasagem de afluência de entrada ah,ℓa_{h,\ell}, ℓ=1,…,Pmax⁡\ell = 1, \ldots, P^{\max}, fixada no valor visitado a^h,ℓ\hat{a}_{h,\ell} por seus limites de coluna;
  • uma coluna livre e de custo nulo zhz_h para a afluência realizada, definida pela linha zh−∑ℓψm(t),ℓ ah,ℓ=bh,m(t)+σm(t) εtz_h - \sum_{\ell} \psi_{m(t),\ell} \, a_{h,\ell} = b_{h,m(t)} + \sigma_{m(t)} \, \varepsilon_t;
  • a coluna zhz_h nas linhas de balanço hídrico e nas linhas de restrições genéricas que leem a afluência;
  • em cada linha de corte, o coeficiente da defasagem 1 sobre zhz_h e o coeficiente da defasagem ℓ\ell sobre ah,ℓ−1a_{h,\ell-1}; os coeficientes de defasagem de um corte novo são os custos reduzidos das colunas de defasagem fixadas.

A formulação compacta, que o Novo Modelo monta e resolve em todo estágio do treinamento (training) e da simulação, parte de uma observação: antes da resolução, as defasagens de entrada são o estado visitado e o ruído é o da abertura, de modo que a afluência realizada é um número conhecido,

z^h=bh,m(t)+∑ℓ=1Pmax⁡ψm(t),ℓ a^h,ℓ+σm(t) εt\hat{z}_h = b_{h,m(t)} + \sum_{\ell=1}^{P^{\max}} \psi_{m(t),\ell} \, \hat{a}_{h,\ell} + \sigma_{m(t)} \, \varepsilon_t

em que ψm(t),ℓ\psi_{m(t),\ell} é nulo para uma defasagem que o modelo da usina hh não usa. O PL compacto não tem coluna de defasagem, nem coluna nem linha de afluência realizada. z^h\hat{z}_h entra em toda linha que a lê como uma constante no lado direito (§2). Cada linha de corte mantém seus termos nas colunas do PL (armazenamento, parcelas de água em trânsito (in-transit buckets) e posições do anel de despacho antecipado (commitment ring slots)), e seus termos de defasagem, avaliados em z^\hat{z} e a^\hat{a}, passam para o seu lado direito (§3).

A figura desenha o PL do estágio de cada formulação em blocos, fora de escala: colunas na horizontal, linhas na vertical, o lado direito à direita. Os blocos em azul são os que o modelo de afluências preenche. No PL expandido, são as colunas de defasagem e de afluência realizada, as linhas de definição e os termos de defasagem dos cortes. No PL compacto, as mesmas grandezas chegam ao lado direito como números, calculados fora do PL.

PL expandidoPL compactoPAR(p), fora do PL:ẑ = b + ψ·â + σεColunas da operaçãoColunas de defasagem e zLado direitoLinhas da operaçãoz no balanço hídricoLimites Linhas do PAR(p):z − ψ·ab + σεCortes: θ e armazenamentoCortes: z e defasagensβ₀Colunas da operaçãoLado direitoLinhas da operaçãoLimites − Γ·ẑCortes: θ e armazenamentoβ₀ + termos de defasagem linhas do PAR(p)retiradas do PLẑ e â como númerosz fixada em ẑe eliminada

O PL compacto é o PL expandido com cada coluna zhz_h fixada em z^h\hat{z}_h e eliminada para os limites das linhas em que aparece, e sem as linhas de definição e as colunas de defasagem fixadas: a eliminação que um pré-processamento (presolve) faria, feita na montagem do PL. As colunas de defasagem e de afluência realizada têm coeficiente 00 na função objetivo, de modo que o valor ótimo QtQ_t de cada resolução é o mesmo nas duas formulações. Com N=∣H∣N = \lvert\mathcal{H}\rvert usinas hidrelétricas, o PL compacto tem N(Pmax⁡+1)N (P^{\max} + 1) colunas e NN linhas a menos por estágio, e nenhuma linha de corte tem entrada nas defasagens de afluência.

Os cortes em si são os mesmos nas duas formulações: um corte mantém um coeficiente por componente do estado sobre o qual se projeta, incluídas as defasagens de afluência quando a projeção do estágio as mantém (Gerenciamento de cortes §1, Aumento do espaço de estados §7). Só a linha do corte no PL fica mais curta.

A afluência realizada se divide em uma parte fixada pelo estado visitado e uma parte fixada pela abertura:

z^h=bh,m(t)+∑ℓ=1Pmax⁡ψm(t),ℓ a^h,ℓ⏟z^hx+σm(t) εt⏟z^hε\hat{z}_h = \underbrace{b_{h,m(t)} + \sum_{\ell=1}^{P^{\max}} \psi_{m(t),\ell} \, \hat{a}_{h,\ell}}_{\hat{z}^{x}_h} + \underbrace{\sigma_{m(t)} \, \varepsilon_t}_{\hat{z}^{\varepsilon}_h}
  • z^hx\hat{z}^{x}_h é calculada uma vez por estado visitado, e z^h\hat{z}_h uma vez por resolução. Os termos são somados em uma ordem fixa (a base, os termos de defasagem em ℓ\ell crescente e, por fim, o termo do ruído), de modo que z^h\hat{z}_h tem os mesmos bits qualquer que seja o reaproveitamento das suas partes.
  • ψm(t),ℓ\psi_{m(t),\ell} são os coeficientes em unidades originais de Modelo de afluências PAR(p) §2.3; para uma usina com a componente anual, eles também carregam o termo anual (Modelo de afluências PAR(p) §7.4).

Seja Γr,h\Gamma_{r,h} o coeficiente da afluência realizada da usina hh na linha rr do PL expandido, e 00 onde a linha não a lê:

No PL compacto, cada limite finito brb_r da linha rr passa a ser

br−∑h∈HΓr,h z^hb_r - \sum_{h \in \mathcal{H}} \Gamma_{r,h} \, \hat{z}_h

Γ\Gamma é o único caminho pelo qual uma linha do PL compacto lê a afluência realizada, e nenhum coeficiente da matriz depende de z^\hat{z} nem do estado de entrada: os hiperplanos da FPHA, as inclinações da evaporação e as metas de enchimento são fixados para o estágio (Modelos de função de produção hidrelétrica, Formulação do PL — Linha de evaporação). O estado de entrada entra no PL compacto apenas pelos lados direitos e pelos limites de coluna.

A mesma z^h\hat{z}_h é a afluência realizada em todo o restante da resolução:

O corte ii do PL do estágio tt limita Vt+1V_{t+1}, cujas defasagens de entrada são as defasagens de saída do estágio tt: em um estágio que completa um período de defasagem que começa nele, a afluência realizada do estágio tt (defasagem 11) e as defasagens de entrada do estágio tt deslocadas de uma posição (defasagem ℓ≥2\ell \ge 2) (Formulação do PL §11); o fim desta seção dá as outras formas. No PL compacto, esses valores são números, e a linha de corte fica

θ−∑h∈Hβi,hv vh−⋯≥Ri\theta - \sum_{h \in \mathcal{H}} \beta^v_{i,h} \, v_h - \cdots \ge R_i Ri=β0,i+∑h∈H(βi,h,1lag z^h+∑ℓ=2Pmax⁡βi,h,ℓlag a^h,ℓ−1)R_i = \beta_{0,i} + \sum_{h \in \mathcal{H}} \Big( \beta^{lag}_{i,h,1} \, \hat{z}_h + \sum_{\ell=2}^{P^{\max}} \beta^{lag}_{i,h,\ell} \, \hat{a}_{h,\ell-1} \Big)

em que ⋯\cdots representa os termos nas colunas de saída das parcelas de água em trânsito e das posições do anel (Aumento do espaço de estados §3). O lado direito se divide como a afluência realizada:

Ri=Rix+RiεR_i = R^{x}_i + R^{\varepsilon}_i Rix=β0,i+∑h∈H(∑ℓ=2Pmax⁡βi,h,ℓlag a^h,ℓ−1+βi,h,1lag z^hx),Riε=∑h∈Hβi,h,1lag z^hεR^{x}_i = \beta_{0,i} + \sum_{h \in \mathcal{H}} \Big( \sum_{\ell=2}^{P^{\max}} \beta^{lag}_{i,h,\ell} \, \hat{a}_{h,\ell-1} + \beta^{lag}_{i,h,1} \, \hat{z}^{x}_h \Big), \qquad R^{\varepsilon}_i = \sum_{h \in \mathcal{H}} \beta^{lag}_{i,h,1} \, \hat{z}^{\varepsilon}_h
  • A parte do estado depende do estado visitado, do nó filho e do corte, e não da abertura. Ela é calculada uma vez por estado visitado e nó filho, e todas as aberturas da simulação backward nesse estado a compartilham; a simulação backward pode tomá-la da simulação forward no mesmo estado visitado em vez de calculá-la de novo. A fixação do estado de entrada também é feita uma vez por estado visitado, e não uma vez por abertura.
  • A parte do ruído depende da abertura e do corte, e não do estado visitado. Ela é calculada uma vez por nó e abertura, para todos os estados visitados no nó.
  • Em cada abertura, resta uma soma: Ri=Rix+RiεR_i = R^{x}_i + R^{\varepsilon}_i.

A figura mostra o reaproveitamento em um estado visitado da simulação backward.

Estado visitado x̂Ruídos ε dasaberturas do nóParte do estado, uma vez por estado visitado:β₀ + termos de defasagem + β₁·ẑˣParte do ruído, uma vez por abertura:β₁·σε, para todos os estados visitadosAberturas da simulação backward em x̂Lado direito do corte em cada abertura:parte do estado + parte do ruído12…Ω compartilhadapor abertura

Cada parte é somada em uma ordem fixa, e uma parte guardada é o valor que a mesma conta daria no lugar, de modo que o reaproveitamento não altera nenhum bit: o resultado é o mesmo com ou sem ele, em qualquer número de threads e de processos (rank MPI) (Determinismo e rastreabilidade). O método dinâmico verifica um corte omitido contra o mesmo lado direito (Gerenciamento de cortes §8).

Períodos de defasagem divididos entre estágios. Em um estágio que deixa seu período de defasagem aberto, as defasagens de saída são as de entrada (Estudos com múltiplas resoluções §2.1), de modo que todo termo de defasagem de um corte é βi,h,ℓlag a^h,ℓ\beta^{lag}_{i,h,\ell} \, \hat{a}_{h,\ell}, na parte do estado, e a parte do ruído é nula. Em um estágio que completa um período iniciado antes, a defasagem 1 é a média do período bh+ch z^hb_h + c_h \, \hat{z}_h, com

bh=Sh,tWh,t+wt,W,ch=wt,WWh,t+wt,Wb_h = \frac{S_{h,t}}{W_{h,t} + w_{t,\mathcal{W}}}, \qquad c_h = \frac{w_{t,\mathcal{W}}}{W_{h,t} + w_{t,\mathcal{W}}}

de modo que seu termo põe βi,h,1lag(bh+ch z^hx)\beta^{lag}_{i,h,1} (b_h + c_h \, \hat{z}^{x}_h) na parte do estado e βi,h,1lag ch z^hε\beta^{lag}_{i,h,1} \, c_h \, \hat{z}^{\varepsilon}_h na parte do ruído. bhb_h depende do estado visitado pela soma parcial, e chc_h não depende do estado visitado nem da abertura, de modo que cada parte mantém seu reaproveitamento.

4. Os coeficientes das defasagens pela regra da cadeia

Seção intitulada “4. Os coeficientes das defasagens pela regra da cadeia”

No PL expandido, os coeficientes de defasagem de um corte novo são os custos reduzidos das colunas de defasagem fixadas (Gerenciamento de cortes §2). O PL compacto não tem essas colunas, e o Novo Modelo calcula os coeficientes depois da resolução, a partir das suas variáveis duais, pela regra da cadeia. O valor ótimo QtQ_t depende da defasagem de entrada a^h,ℓ\hat{a}_{h,\ell} por dois caminhos:

  1. por z^hx\hat{z}^{x}_h, com derivada ψm(t),ℓ\psi_{m(t),\ell}, e, a partir de z^h\hat{z}_h, pelos limites deslocados das linhas (§2) e pelos termos da defasagem 1 das linhas de corte (§3);
  2. pelo termo da defasagem ℓ+1\ell+1 de cada linha de corte, que avalia o corte sucessor em a^h,ℓ\hat{a}_{h,\ell}.

Com πr\pi_r a variável dual da linha rr e πicut\pi^{cut}_i a variável dual da linha de corte ii, o valor da afluência realizada da usina hh é

πhz=−∑rΓr,h πr+∑iπicut βi,h,1lag\pi^z_h = -\sum_{r} \Gamma_{r,h} \, \pi_r + \sum_{i} \pi^{cut}_i \, \beta^{lag}_{i,h,1}

e os coeficientes de defasagem do corte novo são

βh,ℓlag=ψm(t),ℓ πhz+∑iπicut βi,h,ℓ+1lag(ℓ<Pmax⁡),βh,Pmax⁡lag=ψm(t),Pmax⁡ πhz\beta^{lag}_{h,\ell} = \psi_{m(t),\ell} \, \pi^z_h + \sum_{i} \pi^{cut}_i \, \beta^{lag}_{i,h,\ell+1} \quad (\ell < P^{\max}), \qquad \beta^{lag}_{h,P^{\max}} = \psi_{m(t),P^{\max}} \, \pi^z_h

πhz\pi^z_h é igual à variável dual da linha de definição da afluência realizada de hh no PL expandido. Γ\Gamma e as variáveis duais são tomados em unidades sem escalonamento (Estrutura e escalonamento do PL §2), de modo que os coeficientes dispensam outra remoção de escala. A figura acompanha a regra para uma usina.

Variáveis duais da resoluçãoValor da afluência realizada π(z)Cortes sucessores na defasagem ℓ+1:Σ π(corte)·β(ℓ+1)Corte novoLinhas que leema afluência: −Σ Γ·πCortes sucessores na defasagem 1:Σ π(corte)·β₁Defasagem 1: ψ₁·π(z) + Σ π(corte)·β₂Defasagem 2: ψ₂·π(z) + Σ π(corte)·β₃…Defasagem mais antiga P: ψ(P)·π(z) × ψ(ℓ), defasagem a defasagem+, na defasagem ℓ
  • Coeficientes de armazenamento, das parcelas de água em trânsito e das posições do anel são os custos reduzidos das colunas de entrada fixadas, como no PL expandido (Gerenciamento de cortes §2).
  • O termo independente é calculado depois dos coeficientes de defasagem, β0=Qt−β⊤x^\beta_0 = Q_t - \beta^{\top} \hat{x} sobre todos os componentes em que o corte se projeta (Gerenciamento de cortes §2).
  • Projeção. Um componente que o corte deixa fora da projeção não tem coeficiente (Aumento do espaço de estados §7): um corte sucessor sem a defasagem ℓ+1\ell+1 não acrescenta termo na defasagem ℓ\ell, e o corte novo mantém os coeficientes de defasagem que a projeção do seu próprio estágio seleciona.
  • Completude. O estado de entrada entra no PL compacto apenas pelos lados direitos e pelos limites de coluna (§2), de modo que os dois caminhos são os únicos e a regra deriva o PL que é resolvido. O montante de truncamento ah−a^-_h é um limite de coluna calculado a partir de z^h\hat{z}_h, e a regra não o deriva; o PL expandido também não, pois nele o montante é igualmente um limite de coluna, de modo que a limitação de Métodos de tratamento de afluências negativas §7 vale nas duas formulações.
  • Agregação. A regra é linear nas variáveis duais, e os pesos de Gerenciamento de cortes §3, sob o valor esperado ou sob uma medida de risco, dependem apenas dos valores objetivo das aberturas. O Novo Modelo agrega as variáveis duais das aberturas de cada nó filho com esses pesos e aplica a regra uma vez por nó filho, com os coeficientes ψ\psi desse filho; em aritmética exata, o resultado é a agregação dos cortes de cada abertura.

Períodos de defasagem divididos entre estágios. A regra deriva os termos de defasagem das linhas de corte tal como a §3 os avalia (Estudos com múltiplas resoluções §2.1). Em um estágio que deixa seu período de defasagem aberto, nenhuma linha de corte lê z^h\hat{z}_h, e cada linha de corte avalia o corte sucessor na defasagem ℓ\ell sobre a própria a^h,ℓ\hat{a}_{h,\ell}:

πhz=−∑rΓr,h πr,βh,ℓlag=ψm(t),ℓ πhz+∑iπicut βi,h,ℓlag(ℓ≤Pmax⁡)\pi^z_h = -\sum_{r} \Gamma_{r,h} \, \pi_r, \qquad \beta^{lag}_{h,\ell} = \psi_{m(t),\ell} \, \pi^z_h + \sum_{i} \pi^{cut}_i \, \beta^{lag}_{i,h,\ell} \quad (\ell \le P^{\max})

Em um estágio que completa um período iniciado antes, as linhas de corte leem z^h\hat{z}_h por meio de ch z^hc_h \, \hat{z}_h, de modo que o termo dos cortes em πhz\pi^z_h é multiplicado por chc_h, a soma parcial Sh,tS_{h,t} é mantida fixa e os coeficientes de defasagem tomam a forma dada para um estágio que completa um período que começa nele:

πhz=−∑rΓr,h πr+ch∑iπicut βi,h,1lag\pi^z_h = -\sum_{r} \Gamma_{r,h} \, \pi_r + c_h \sum_{i} \pi^{cut}_i \, \beta^{lag}_{i,h,1}

O corte é exato apenas onde Sh,tS_{h,t} é a mesma em todos os caminhos (Estudos com múltiplas resoluções §2.1).

Idêntico em aritmética exata: o conjunto viável projetado nas colunas mantidas e em θ\theta; o valor ótimo QtQ_t; a face dual ótima nas linhas mantidas, em unidades sem escalonamento; portanto, o conjunto de cortes possíveis; os coeficientes de armazenamento, das parcelas de água em trânsito e das posições do anel em um dado vértice; e o termo independente dados os coeficientes. O coeficiente de defasagem que o PL expandido dá como custo reduzido difere do valor da regra da cadeia em ψm(t),ℓ\psi_{m(t),\ell} vezes o custo reduzido da coluna zhz_h, que o solver deixa dentro da sua tolerância dual; a regra da cadeia não carrega esse resíduo.

Não idêntico:

  • Em um ótimo degenerado, o simplex pode parar em outro vértice ótimo. O PL compacto é menor, e as linhas que leem a afluência perdem a entrada de zhz_h e podem receber outra escala de linha (Estrutura e escalonamento do PL §2), de modo que o caminho de pivoteamento muda. Outro vértice dá outro corte da mesma face ótima, e todas as iterações seguintes decorrem dele.
  • Todo valor calculado difere no nível do arredondamento.

Uma execução com o PL compacto e uma com o PL expandido concordam, portanto, no valor ótimo de cada resolução e nos cortes possíveis, mas não bit a bit.

A troca de flexibilidade. As duas formulações dividem o trabalho de formas diferentes:

  • Expandida. O próprio PL dá o corte de qualquer modelo de afluências cuja afluência realizada seja linear no estado: o modelo é escrito como linhas, e os custos reduzidos das colunas fixadas dão os coeficientes de defasagem sem nenhum passo específico do modelo.
  • Compacta. Cada modelo de afluências precisa da sua própria regra da cadeia, a derivada da afluência realizada e dos termos de defasagem do corte em relação a cada defasagem de entrada, e toda linha que lê a afluência realizada a lê por Γ\Gamma. Uma linha que a lesse de outra forma definiria outro PL, cujos cortes a regra não reproduziria.

O Novo Modelo resolve a formulação compacta: um PL menor em todo estágio, linhas de corte sem entradas de defasagem e um lado direito dos cortes que se divide em uma parte por estado visitado e uma parte por abertura. O preço é um método especializado na família PAR(p) (PAR(p) e PAR(p)-A, lineares nas defasagens por ψ\psi), cujas linhas precisam todas ler a afluência por um único caminho.