Folding do PAR(p)
Objetivo
Seção intitulada “Objetivo”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).
1. Duas formulações do mesmo PL
Seção intitulada “1. Duas formulações do mesmo PL”A formulação expandida escreve o modelo de afluências dentro do PL do estágio. Para cada usina hidrelétrica , ela tem:
- uma coluna por defasagem de afluência de entrada , , fixada no valor visitado por seus limites de coluna;
- uma coluna livre e de custo nulo para a afluência realizada, definida pela linha ;
- a coluna 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 e o coeficiente da defasagem sobre ; 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,
em que é nulo para uma defasagem que o modelo da usina não usa. O PL compacto não tem coluna de defasagem, nem coluna nem linha de afluência realizada. 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 e , 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.
O PL compacto é o PL expandido com cada coluna fixada em 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 na função objetivo, de modo que o valor ótimo de cada resolução é o mesmo nas duas formulações. Com usinas hidrelétricas, o PL compacto tem colunas e 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.
2. A afluência realizada fora do PL
Seção intitulada “2. A afluência realizada fora do PL”A afluência realizada se divide em uma parte fixada pelo estado visitado e uma parte fixada pela abertura:
- é calculada uma vez por estado visitado, e uma vez por resolução. Os termos são somados em uma ordem fixa (a base, os termos de defasagem em crescente e, por fim, o termo do ruído), de modo que tem os mesmos bits qualquer que seja o reaproveitamento das suas partes.
- 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 o coeficiente da afluência realizada da usina na linha do PL expandido, e onde a linha não a lê:
- na linha de balanço hídrico de em um estágio paralelo, e na linha do patamar em um estágio cronológico (Formulação do PL §4); para uma usina em pré-enchimento, nas linhas da primeira usina a jusante que não esteja em pré-enchimento (Formulação do PL — Repasse em pré-enchimento);
- o coeficiente de cada termo de restrição genérica que lê a afluência de (Formulação do PL — Afluência das usinas hidrelétricas).
No PL compacto, cada limite finito da linha passa a ser
é o único caminho pelo qual uma linha do PL compacto lê a afluência realizada, e nenhum coeficiente da matriz depende de 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 é a afluência realizada em todo o restante da resolução:
- o montante de truncamento que limita a folga de não negatividade da afluência (Métodos de tratamento de afluências negativas §2);
- o estado de saída das defasagens de afluência, que a acumulação das defasagens forma a partir de e das defasagens de entrada (Estudos com múltiplas resoluções §2), enquanto o armazenamento, as parcelas de água em trânsito e as posições do anel de saída são lidos da solução do PL (Aumento do espaço de estados §3);
- a afluência realizada que a simulação informa.
3. O lado direito dos cortes
Seção intitulada “3. O lado direito dos cortes”O corte do PL do estágio limita , cujas defasagens de entrada são as defasagens de saída do estágio : em um estágio que completa um período de defasagem que começa nele, a afluência realizada do estágio (defasagem ) e as defasagens de entrada do estágio deslocadas de uma posição (defasagem ) (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
em que 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:
- 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: .
A figura mostra o reaproveitamento em um estado visitado da simulação backward.
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 é , 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 , com
de modo que seu termo põe na parte do estado e na parte do ruído. depende do estado visitado pela soma parcial, e 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 depende da defasagem de entrada por dois caminhos:
- por , com derivada , e, a partir de , pelos limites deslocados das linhas (§2) e pelos termos da defasagem 1 das linhas de corte (§3);
- pelo termo da defasagem de cada linha de corte, que avalia o corte sucessor em .
Com a variável dual da linha e a variável dual da linha de corte , o valor da afluência realizada da usina é
e os coeficientes de defasagem do corte novo são
é igual à variável dual da linha de definição da afluência realizada de no PL expandido. 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.
- 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, 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 não acrescenta termo na defasagem , 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 é um limite de coluna calculado a partir de , 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 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ê , e cada linha de corte avalia o corte sucessor na defasagem sobre a própria :
Em um estágio que completa um período iniciado antes, as linhas de corte leem por meio de , de modo que o termo dos cortes em é multiplicado por , a soma parcial é mantida fixa e os coeficientes de defasagem tomam a forma dada para um estágio que completa um período que começa nele:
O corte é exato apenas onde é a mesma em todos os caminhos (Estudos com múltiplas resoluções §2.1).
5. Exatidão e limites
Seção intitulada “5. Exatidão e limites”Idêntico em aritmética exata: o conjunto viável projetado nas colunas mantidas e em ; o valor ótimo ; 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 vezes o custo reduzido da coluna , 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 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 . 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 ), cujas linhas precisam todas ler a afluência por um único caminho.
Referências cruzadas
Seção intitulada “Referências cruzadas”- Modelo de afluências PAR(p) — o modelo de afluências cuja realização o PL compacto recebe como número
- Formulação do PL — as linhas que leem a afluência realizada e as linhas de corte do PL do estágio
- Estrutura e escalonamento do PL — a estrutura de colunas e linhas do PL compacto e as escalas das linhas que leem a afluência
- Aumento do espaço de estados — o vetor de estado, sua fixação por limites de coluna e o estado de saída
- Gerenciamento de cortes — a definição do corte, a extração dos demais coeficientes pelos custos reduzidos e a agregação
- Métodos de tratamento de afluências negativas — a folga de afluência limitada pelo montante de truncamento de
- Estudos com múltiplas resoluções — a acumulação das defasagens que forma as defasagens de saída a partir de
- Determinismo e rastreabilidade — resultados idênticos bit a bit em qualquer número de threads e de processos MPI, com ou sem o reaproveitamento da §3