Pular para o conteúdo

Aproveitamento de base do PL

Este capítulo descreve como o Novo Modelo reaproveita uma base de PL para acelerar as resoluções. São abordados dois mecanismos relacionados. O repositório de bases por (cenário, nó) guarda no máximo uma base por estado visitado por nó do grafo da política (policy graph), e as simulações forward e backward passam bases uma à outra por meio dele, de modo que uma base encontrada em uma resolução possa servir de ponto de partida para a próxima resolução do mesmo estado visitado no mesmo nó. A reconstrução da base sensível aos cortes por identidade de slot mapeia uma base armazenada em um conjunto de cortes cujo conjunto ativo foi alterado pela seleção de cortes, o que permite que uma base reaproveitada — seja capturada anteriormente na execução, seja carregada de uma política salva por uma execução de partida a quente (warm-start) ou de retomada — se alinhe ao PL corrente.

A simulação backward do Algoritmo da PDDE (SDDP) resolve, em cada estágio, um PL por abertura por estado visitado por iteração. Ao longo de uma execução de treinamento (training), esses PLs não são independentes: o PL do estágio tt na iteração k+1k+1 difere do PL do estágio tt na iteração kk apenas de duas formas — o conjunto de cortes ativos mudou (cresceu com os cortes adicionados durante a iteração kk e, possivelmente, foi alterado ainda pela seleção de cortes, que desativa e reativa cortes; §3), e o estado visitado pode ter se deslocado. As colunas da matriz de restrições, a função objetivo, os limites, exceto aqueles que fixam o estado de entrada, e a maioria das linhas de restrição são idênticos entre iterações consecutivas.

Uma partida a frio (cold start) descarta essa semelhança estrutural. O solver de PL começa do zero a cada vez, escolhendo uma base inicial por sua própria heurística (tipicamente a viabilidade primal da Fase I). Em um PL bem estruturado, isso desperdiça pivoteamentos do simplex cujo único propósito é redescobrir uma base que já era conhecida.

O aproveitamento de base (warm start) evita esse desperdício fornecendo ao solver a base de uma resolução anterior no mesmo estágio. O solver verifica se a base fornecida é primal viável, dual viável ou ambas para o novo PL; se for, pode passar imediatamente às iterações de otimalidade, em vez de reconstruir a viabilidade do zero. O ganho é proporcional à semelhança entre PLs consecutivos — e, na simulação backward da PDDE, resoluções consecutivas no mesmo estágio são muito semelhantes.

O Novo Modelo mantém um repositório de bases indexado por (scenario, node): o cenário identifica um estado visitado, e o nó é um nó do grafo da política; em uma cadeia de estágios (um nó por estágio), um nó é um estágio. O repositório guarda no máximo uma base capturada — a partição das variáveis e restrições em básicas e não básicas — para cada estado visitado em cada nó.

O uso do repositório como ponto de partida de uma resolução é definido por fase: a simulação forward, a simulação backward e a simulação final usam, cada uma, aproveitamento de base ou partida a frio (ver as notas de implementação). Uma resolução de uma fase com aproveitamento de base parte do slot do seu estado visitado quando o slot contém uma base; uma resolução de uma fase com partida a frio não parte de nenhuma base, nem de uma armazenada nem daquela que a resolução anterior deixou carregada. As capturas não dependem dessa configuração.

As simulações forward e backward de uma iteração passam bases uma à outra por meio do repositório. Uma resolução forward em um nó armazena sua base ótima no slot do seu estado visitado. A simulação backward é executada após a simulação forward da mesma iteração; quando resolve as aberturas desse nó a partir do estado de entrada do mesmo estado visitado, o slot contém a captura forward, que serve de ponto de partida para a primeira abertura resolvida quando a simulação backward usa aproveitamento de base, e a simulação backward armazena a base ótima dessa abertura em seu lugar. A resolução forward da iteração seguinte no nó parte dessa captura backward quando a simulação forward usa aproveitamento de base; uma resolução forward a frio não a lê e a substitui por sua própria captura. Em ambos os casos, o slot que a simulação backward lê nesse nó contém a captura forward da sua própria iteração. Uma opção de escalonamento da simulação backward lê a captura forward sem armazenar a sua; com uma simulação forward enumerada, a simulação backward não usa nenhuma base armazenada; e, enquanto o método dinâmico de seleção de cortes está ativo, nenhuma resolução usa o repositório (ver as notas de implementação).

Simulação forwardBase armazenada(estado visitado, nó)Simulação backward pode servir de partida para a resoluçãoarmazena sua baseparte da primeira abertura resolvidaarmazena a base dessa aberturapode servir de partida na próxima iteração

Cada seta de partida se aplica quando a respectiva fase usa aproveitamento de base; cada seta de armazenamento se aplica quaisquer que sejam as fases que usam aproveitamento de base.

Em cada cadeia de aberturas que uma simulação backward com aproveitamento de base resolve em sequência, o repositório é lido no máximo uma vez, pela primeira abertura resolvida; as demais aberturas continuam a partir da base e da fatoração que a abertura anterior deixou carregadas, já que aberturas consecutivas diferem apenas em sua realização.

A base de partida de uma resolução depende, portanto, da ordem em que as aberturas da sua cadeia são resolvidas. Essa ordem é fixada de antemão e altera a base de partida, nunca a validade de um corte, pois toda base ótima do PL de uma abertura produz um corte válido; Determinismo e rastreabilidade §3 expõe como a ordem fixa mantém a execução reprodutível.

Uma execução de partida a quente ou de retomada inicializa o repositório com as bases salvas, uma por estado visitado em cada nó, de modo que, quando a simulação forward usa aproveitamento de base, as resoluções forward da sua primeira iteração nesses nós partem delas por meio da reconstrução do §4. Uma execução de retomada inicializa cada estado visitado com sua própria base salva e deixa a frio um estado visitado que não tenha base; uma execução de partida a quente inicializa um estado visitado sem base salva própria com a base salva do cenário de menor índice do nó. Uma base salva que não se ajusta ao PL do seu estágio é descartada, e um nó que fique sem nenhuma inicia sua primeira iteração a frio. Quando a simulação forward usa partida a frio, suas capturas substituem as bases inicializadas dos nós que ela visita antes que a simulação backward leia o repositório. Em uma cadeia de estágios, as bases salvas então não servem de partida para nenhuma resolução do treinamento; em um grafo com ramificações, servem de partida apenas para as resoluções backward com aproveitamento de base nos nós sucessores que a trajetória forward da primeira iteração de um estado visitado não visitou.

Uma base armazenada deixa de corresponder ao PL do estágio tt quando esse PL muda de forma. A mudança relevante é o crescimento do conjunto de cortes: cada iteração adiciona um novo corte por estado visitado em todos os estágios, exceto o último. O conjunto de cortes e o PL persistente do limite inferior são somente de acréscimo (append-only), enquanto o template de estágio de cada iteração contém apenas os cortes ativos (a desativação é tratada ao final desta seção; consulte Gerenciamento de cortes para a garantia de monotonicidade do conjunto somente de acréscimo). Um novo corte adiciona uma linha de restrição ao PL.

Acrescentar uma linha de corte a um PL já resolvido, com a folga da nova linha básica, mantém a base ótima desse PL dual viável: o dual da nova linha é zero porque sua folga é básica, de modo que nenhum custo reduzido se altera. Se o novo corte é satisfeito na solução primal anterior, a base permanece ótima. Se o corte é violado nela, a base é primal inviável, e o simplex dual, que preserva a viabilidade dual, restaura a viabilidade primal a partir dessa base, e não a partir de uma partida a frio.

Quando a seleção de cortes não altera o conjunto ativo, esse crescimento é puramente monótono: linhas são apenas adicionadas, nunca removidas ou reordenadas. A relação estrutural entre instâncias consecutivas do PL é então previsível — o novo PL é uma extensão própria do anterior, compartilhando todas as suas linhas —, de modo que os fatos sobre o acréscimo de linhas acima se aplicam a cada nova linha de corte. A seleção de cortes pode quebrar esse caso de acréscimo puro, tratado no parágrafo seguinte.

A desativação de cortes segue um caminho diferente na resolução da simulação backward. Um corte desativado é excluído do template congelado recomposto, em vez de permanecer com um limite relaxado: no nível do PL, sua linha é removida, e não apenas folgada, de modo que o conjunto de cortes ativos pode diminuir e ser reordenado de uma iteração para a outra, e não apenas crescer. O corte não se perde — seu slot estável é mantido no conjunto somente de acréscimo, e a reativação recompõe o corte nesse mesmo slot. Como o conjunto ativo pode mudar dessa forma, uma base armazenada não pode ser reaplicada por posição de linha; a reconstrução por identidade de slot do §4 a reconcilia com o conjunto ativo corrente, o que mantém o aproveitamento de base válido através da desativação e da reativação. Consulte Gerenciamento de cortes para o mecanismo completo de desativação, incluindo o caminho separado do PL persistente do limite inferior, que é somente de acréscimo — suas linhas de corte nunca são removidas, de modo que a desativação nada altera ali e o limite inferior permanece monótono.

4. Reconstrução da base sensível aos cortes por identidade de slot

Seção intitulada “4. Reconstrução da base sensível aos cortes por identidade de slot”

Entre resoluções, a seleção de cortes (ver Gerenciamento de cortes) desativa e reativa cortes, e a simulação backward acrescenta novos, de modo que o conjunto de linhas de corte ativas no PL do estágio se renova de uma iteração para a seguinte. Uma base armazenada registra um status para cada linha que continha; se esses status fossem reaplicados por posição de linha, um conjunto de cortes renovado de mesmo tamanho ficaria desalinhado — e o solver partiria de uma base corrompida ou recairia em uma partida a frio.

O Novo Modelo evita isso fazendo a reconciliação por identidade de slot, e não por posição. O conjunto de cortes atribui a cada corte um índice de slot estável (ver Gerenciamento de cortes §5), e uma base armazenada traz, para cada linha de corte que continha, o slot do conjunto que a gerou. Para reconstruir uma base para o PL corrente:

  • Os status das linhas que não são cortes (template) e os status de todas as colunas são copiados diretamente.
  • Cada linha de corte corrente é associada à base armazenada pelo seu slot. Se o slot estava presente na base armazenada, seu status salvo é reaproveitado; se o slot é novo — um corte que não estava no PL quando a base foi capturada —, a linha é definida como BASIC (folga), o padrão sob o qual a nova linha não altera nenhum custo reduzido (§3); se o corte for violado no ponto de partida, o simplex dual corrige a inviabilidade primal resultante.
  • Definir as novas linhas de corte como BASIC preserva, por construção, o invariante de contagem de básicas do solver (cada novo corte adiciona exatamente uma linha e uma entrada básica). Quando a seleção, ao contrário, remove um corte cuja linha era não básica (ativa na solução), a base reconstruída fica com uma entrada básica a mais para cada linha desse tipo, porque uma linha básica sai junto com sua folga básica, enquanto uma linha não básica não leva consigo nenhuma entrada básica; uma etapa final rebaixa o excesso final de linhas de corte básicas para não básicas até que o invariante seja satisfeito. Sob as premissas da reconstrução — uma base armazenada capturada para um PL de mesma forma —, a obrigação é unilateral: a reconstrução só pode deixar um excesso. Um déficit na contagem de básicas, portanto, prova que a base armazenada foi capturada para um PL de forma diferente; ela é rejeitada com um erro nomeado que reporta a aritmética da contagem de básicas, de forma idêntica em qualquer backend de solver — nunca corrigida, já que o rebaixamento não pode criar as básicas ausentes e a promoção fabricaria uma base que a armazenada jamais descreveu.

Esse mecanismo único trata os três casos de renovação — remoções, reordenações e adições — e atende tanto à reativação dentro de uma execução quanto à reconstrução do checkpoint entre execuções, usada na partida a quente (warm-start) da política e na retomada (§2).

O ganho do aproveitamento de base diminui com a magnitude da mudança no PL. A base armazenada é mais valiosa quando instâncias consecutivas do PL são quase idênticas. No início de uma execução de treinamento, quando o conjunto de cortes cresce rapidamente e cada novo corte pode deslocar substancialmente a face ativa da base ótima, o aproveitamento de base proporciona economias menores do que nas fases intermediária e final do treinamento, quando o conjunto de cortes já se estabilizou em grande parte e os novos cortes fazem apenas mudanças incrementais na geometria do PL.

Relação com a reconstrução sensível aos cortes. O repositório de bases e a reconstrução do §4 respondem a perguntas diferentes. O repositório responde “qual base armazenada deve servir de partida para a primeira resolução deste subproblema (scenario, node)?” — fornecendo uma base capturada para esse mesmo slot. A reconstrução responde à pergunta mais restrita que surge porque o conjunto de cortes ativos incorporado ao template corrente pode ter se renovado desde que essa base foi capturada: “quais status de linha armazenados ainda se aplicam, e que status devem assumir as linhas de corte novas neste PL?” O repositório fornece o ponto de partida; a reconstrução o reconcilia com o conjunto de cortes corrente por identidade de slot, atribuindo BASIC por padrão às linhas de corte sem slot armazenado.

A metodologia acima define o repositório de bases, a passagem de bases e a reconstrução; a aba abaixo mostra como as simulações de treinamento e a simulação final do Novo Modelo usam o repositório em tempo de execução.

Comportamento não normativo do software para o aproveitamento de base (warm-start da base) do PL — o que o Novo Modelo faz em tempo de execução, além da metodologia de Aproveitamento de base do PL. Esta aba remete ao corpo metodológico para a transferência e a reconstrução, em vez de reapresentá-las.

Toda fase captura as bases de suas resoluções no repositório de bases, mas o fato de uma resolução partir ou não da base que lhe é oferecida depende do backend do solver. Os perfis de fase do backend HiGHS definem use_warm_start como true para as simulações forward e backward, e como false para a simulação final; assim, por padrão, as resoluções do treinamento aproveitam a base e as resoluções da simulação final partem a frio. Com use_warm_start: false, o HiGHS ignora a base oferecida: ela não é instalada, não é validada e não é contabilizada em basis_offered. Uma fase que resolve a frio não monta nenhuma base para oferecer, de modo que nenhuma reconstrução de base é executada para ela; suas capturas continuam preenchendo o repositório. Uma resolução a frio no HiGHS também não continua a partir da base que a resolução anterior deixou no solver, de modo que toda resolução de uma fase a frio começa do zero. Os níveis de nova tentativa 5–11, que restauram as configurações padrão do HiGHS antes de aplicar as suas próprias, preservam o use_warm_start da fase. Antes de informar que uma resolução é ótima, o HiGHS refatora a base, de modo que a solução primal de uma resolução com aproveitamento de base atende a toda linha dentro da tolerância de viabilidade primal. O backend CLP não tem essa configuração e inicia a resolução a partir da base oferecida em todas as fases. Onde as seções abaixo afirmam que uma resolução parte de uma base armazenada, isso vale sob o CLP, ou sob o HiGHS quando o perfil daquela fase tem use_warm_start: true (ver Desativação do aproveitamento de base).

Uma resolução a frio pode terminar em um vértice ótimo diferente daquele de uma resolução com base aproveitada, com o mesmo valor ótimo (Determinismo e rastreabilidade §3), de modo que os estados visitados de uma execução, seus cortes, seu limite inferior final e suas variáveis duais simuladas podem diferir entre as duas configurações.

Esta seção descreve a simulação backward quando o método dinâmico de seleção de cortes está inativo; a seção seguinte trata do caso ativo. Uma unidade de trabalho backward resolve uma cadeia de aberturas em sequência para um estado visitado em um nó. Antes da cadeia, o worker reinicia a base e a fatoração retidas pelo solver, recarrega o modelo congelado do PL do nó e acrescenta os cortes que o conjunto de cortes do nó ganhou desde a construção do modelo. Quando a fase backward aproveita a base, a abertura resolvida primeiro na cadeia parte da posição do estado visitado no repositório de bases e as aberturas restantes continuam a partir da fatoração retida; a base dessa abertura é a única que a cadeia grava de volta na posição, qualquer que seja a configuração da fase. Em um grafo com ramificações, as aberturas de cada nó sucessor formam uma cadeia própria, pois cada sucessor carrega seu próprio PL.

O escalonador padrão by_scenario resolve as aberturas de um estado visitado em um nó sucessor como uma única cadeia. O escalonador by_node (training.parallelism.backward_scheduler; ver Escalonamento por nó) divide-as em blocos de aberturas e resolve cada bloco como uma cadeia própria. A abertura resolvida primeiro em cada bloco lê a base que a simulação forward capturou na posição (a captura forward). Com by_node, a simulação backward não grava nada, de modo que a posição mantém a captura forward, que é a base oferecida à resolução forward da iteração seguinte.

Entretanto, sob uma simulação forward enumerada (training.selection), a simulação forward resolve cada nó uma vez por iteração e grava a base dessa resolução em uma única posição para o nó, oferecida à resolução forward da iteração seguinte nesse nó. A simulação backward não lê nem grava bases armazenadas: a abertura resolvida primeiro em cada cadeia parte sem base armazenada, e as demais continuam a partir da fatoração retida. Com os perfis padrão do HiGHS, uma execução enumerada, portanto, inicia apenas as suas resoluções forward a partir do repositório.

Uma base armazenada inicializa uma resolução somente quando a fase da resolução aproveita a base e a base foi capturada no nó que está sendo resolvido: cada base registra o nó em que foi capturada, e uma base marcada com outro nó, ou uma posição vazia, faz a resolução partir a frio. Uma posição fica vazia até sua primeira captura; assim, em uma execução nova, as resoluções forward da primeira iteração partem a frio, qualquer que seja a configuração da fase. Uma resolução forward inviável limpa sua posição.

Enquanto o método dinâmico de seleção de cortes (Gerenciamento de cortes §8) está ativo, nenhuma resolução lê ou grava no repositório. A simulação forward deixa sua posição intacta, e o PL inicial de toda resolução parte sem base armazenada; em uma fase com aproveitamento de base, as aberturas posteriores de uma cadeia backward, e cada nova resolução após o método dinâmico acrescentar cortes violados, continuam a partir da base retida, enquanto em uma fase a frio elas também partem a frio. O repositório, portanto, mantém as bases capturadas nas iterações anteriores ao início do método dinâmico, e são essas as bases que o checkpoint de fim de treinamento (training) carrega.

Partida a quente, retomada e execuções somente de simulação

Seção intitulada “Partida a quente, retomada e execuções somente de simulação”

O checkpoint de fim de treinamento carrega uma base por estado visitado em cada nó: a base mantida na posição desse estado visitado ao término do treinamento, registrada com seu cenário e com a posição no conjunto de cortes de cada linha de corte. Uma execução com partida a quente (warm-start) ou de retomada inicializa a posição de cada estado visitado a partir do checkpoint antes de sua primeira iteração. Uma execução de retomada inicializa um estado visitado com sua própria base e deixa um estado visitado sem base própria partir a frio; uma execução com partida a quente inicializa um estado visitado sem base própria com a base de menor cenário do nó, já que a execução que gravou o checkpoint pode ter realizado menos simulações forward. Uma posição deixada vazia inicia sua primeira resolução a frio e depois reutiliza suas próprias capturas. Fora do método dinâmico, as resoluções inicializadas da primeira iteração em uma fase com aproveitamento de base partem por meio da reconstrução de §4; uma execução nova não tem o que inicializar. Com o perfil forward padrão do HiGHS, as resoluções forward aproveitam a base; assim, em uma cadeia de estágios, onde todo estado visitado passa por todos os nós, as bases do checkpoint inicializam as resoluções forward da primeira iteração, e cada captura forward substitui então a base inicializada do nó que visita antes que a simulação backward leia essa posição. Quando training.solver.forward define "use_warm_start": false, as resoluções forward partem a frio e, em uma cadeia de estágios, as bases do checkpoint não inicializam nenhuma resolução do treinamento. Em um grafo com ramificações, uma simulação backward que lê o repositório também parte delas nos nós sucessores que a trajetória forward da primeira iteração de um estado visitado não visitou.

Quando a fase de simulação final aproveita a base, e fora do método dinâmico, a simulação inicia a resolução de cada nó visitado a partir da base desse nó, obtida da execução de treinamento anterior ou, em uma execução somente de simulação, da base de checkpoint de menor cenário do nó, para todos os cenários (um nó sem base é resolvido sem base armazenada própria); sob o método dinâmico, as resoluções da simulação partem sem base armazenada. Com o perfil padrão de simulação do HiGHS, toda resolução da simulação parte a frio, de modo que uma execução somente de simulação só usa as bases do checkpoint quando simulation.solver define "use_warm_start": true.

Uma base de checkpoint só é usada quando seu número de colunas é igual ao do PL do estágio atual do nó, seu número de linhas é igual às linhas do modelo do PL mais as linhas de corte registradas, seu número de variáveis básicas é igual ao número de linhas, e toda posição de linha de corte que ela registra contém um corte carregado. Uma base reprovada é descartada, e a carga informa quantas foram descartadas e por que a primeira foi reprovada (ver Validação de bases armazenadas). Uma base admitida mantém os status de suas linhas de corte registradas, associadas ao conjunto de cortes carregado pela posição; uma linha de corte atual que ela não registra parte como BASIC. Em ambos os casos, muda apenas a base a partir da qual o aproveitamento começa, nunca o valor ótimo do PL do estágio.

O aproveitamento de base não depende de um solver residente que mantenha o PL de cada nó durante toda a execução. Cada unidade de trabalho backward reinicia o estado retido do solver e recarrega o modelo congelado do PL do nó antes de resolver, de modo que o que transporta informação de uma resolução para a seguinte não é um solver ativo, mas duas estruturas de dados persistentes:

  • O repositório de bases, indexado por (scenario, node), que a abertura resolvida primeiro em uma cadeia lê e que uma captura atualiza.
  • Os modelos congelados por iteração, um por conjunto de cortes (um por estágio em uma cadeia de estágios), cada um incorporando o conjunto de cortes ativo no momento. Um modelo é construído uma vez por iteração e carregado novamente no solver para cada estado visitado que atende; dentro de uma cadeia, mudam então apenas os limites da realização.

Como o modelo é recarregado em vez de modificado no local, o estado estrutural do PL não se acumula silenciosamente dentro de um solver de longa duração. Os modelos congelados crescem ao longo da execução, pois o modelo de cada iteração incorpora mais cortes que o anterior, e cada base armazenada cresce junto, com um status por linha. Em um estudo com muitos nós e grande número de variáveis de estado, a ocupação combinada dos modelos e do repositório de bases pode ser significativa.

Quando a fase backward aproveita a base, como ocorre por padrão, uma resolução da simulação backward após a primeira iteração custa principalmente o trabalho do simplex dual que restaura a otimalidade a partir da base reutilizada, depois que essa base é reconciliada com o conjunto de cortes atual (§4), em vez do trabalho de viabilidade da Fase I de uma partida a frio.

O perfil de solver de cada fase — training.solver.backward, training.solver.forward e simulation.solver — aceita use_warm_start, que sobrescreve o padrão da fase (true para as simulações forward e backward, false para a simulação final). Defini-lo como false força todas as resoluções dessa fase a partir a frio, e defini-lo como true permite que resoluções da simulação final partam do repositório; fora do método dinâmico, as capturas preenchem o repositório de bases em ambos os casos. As configurações forward e backward são de diagnóstico, não opções de produção: comparar uma simulação a frio com outra com aproveitamento de base isola a contribuição do aproveitamento para o desempenho do treinamento. Sobrescritas de perfil por fase existem apenas no HiGHS; o backend CLP rejeita um campo definido já na inicialização; ver training.solver.

  • Gerenciamento de cortes — O ciclo de vida dos cortes, que é somente de acréscimo, com índices de slot estáveis, que determina as mudanças no conjunto de cortes e sustenta a reconstrução por identidade de slot; o mecanismo de desativação de cortes e as estratégias de seleção que determinam com que frequência o conjunto de cortes muda.
  • Algoritmo da PDDE — O laço de iterações em que as simulações forward e backward compartilham o repositório de bases; a estrutura das simulações forward e backward, como as aberturas de cada estágio são percorridas e as barreiras de sincronização que separam os estágios.
  • Grafos da política — Os nós que indexam o repositório de bases e os estágios a que correspondem.
  • Determinismo e rastreabilidade — A fixação determinística da ordem das cadeias descrita em Determinismo e rastreabilidade §3, que é o que mantém o aproveitamento de base compatível com a reprodutibilidade bit a bit entre execuções.