Esta página foi traduzida pela API Cloud Translation.

Soluções avançadas de LP

Apesar da maturidade da tecnologia LP, alguns casos de uso exigem técnicas mais avançadas. Por exemplo, estão disponíveis vários algoritmos e implementações de LP diferentes, cada um com pontos fortes e fracos. Além disso, a instabilidade numérica pode fazer com que os solucionadores desacelerem ou deixem de resolver determinados modelos.

Este guia apresenta os conceitos e fornece exemplos para ajudar você a conseguir o máximo de desempenho e confiabilidade com os solucionadores de LP.

conceitos

Esta seção apresenta os principais conceitos para uso avançado dos solucionadores de LP. Presumimos que os leitores estejam familiarizados com o conceito de duplicação na LP.

Famílias de algoritmos de LP

As seguintes classes de algoritmos para LP podem ser acessadas em OR-Tools.

O algoritmo Simplex foi o primeiro algoritmo de LP prático e continua sendo o mais conhecido. O algoritmo caminha ao longo dos vértices (pontos de canto) da região viável, melhorando de forma iterativa o valor da função de objetivo até chegar a uma solução ideal. Há dois tipos de algoritmos simplex:
1. Primal simplex segue etapas ao longo dos vértices da região primária viável. Essa variante é particularmente eficaz para resolver uma sequência de problemas de LP com funções objetivas variadas, ou seja, em que a região principal viável é fixa.
2. O simplex duplo segue etapas ao longo dos vértices da região viável dual. Essa variante é particularmente eficaz para resolver uma sequência de problemas de LP em que a região dupla viável é fixa, por exemplo, quando apenas os limites de variáveis mudam. Por esse motivo, o simplex duplo é muito usado em solucionadores MIP.
Os métodos barreira ou ponto interno foram a segunda família prática de algoritmos para LP. Os métodos de barreira combinam garantias teóricas de convergência eficiente (tempo polinomial) com desempenho confiável na prática. Eles complementam o algoritmo simplex quando ele tem baixo desempenho. Por exemplo, alguns solucionadores oferecem a execução de simplex e barreira em paralelo, retornando a solução do algoritmo que termina primeiro.
Métodos de primeira ordem são uma família de algoritmos que usam exclusivamente informações de gradiente (ou seja, derivadas de primeira ordem) para orientar as iterações. O gradiente descendente é um exemplo bem conhecido. Esses métodos são muito usados na otimização não linear e no machine learning. Para LP, os métodos de primeira ordem podem ser dimensionados para problemas maiores do que simplex e barreira, e também podem ter requisitos de memória muito menores. Por outro lado, são mais sensíveis a problemas numéricos e podem ter dificuldades para conseguir soluções de alta precisão.

A tabela abaixo lista os solucionadores de LP disponíveis nas ferramentas OR e indica qual das três famílias de algoritmos é implementada em cada solucionador.

Solucionador	Simplex	Barrier	Primeiro pedido
clp	X	X
CPLEX^L	X	X
Glop^G	X
GLP	X	X
Gurobi^L	X	X
PDLP^G			X
Xpress^L	X	X

G indica que o solucionador é desenvolvido pelo Google. L indica que o solucionador exige uma licença emitida pelo respectivo desenvolvedor terceirizado.

Consulte a seção Recomendações para ver sugestões sobre quais solucionadores e algoritmos usar.

O que realmente significa resolver?

Para aproveitar ao máximo os solucionadores de LP, é importante entender o que está implícito quando um solucionador afirma ter encontrado uma solução. Nesta seção, abordamos os princípios básicos necessários para responder a essa pergunta, especialmente devido à imprecisão numérica e à não exclusividade das soluções.

Tolerâncias

Os solucionadores de LP quase sempre usam aritmética de ponto flutuante, o que torna as soluções sujeitas à imprecisão numérica. Para considerar isso e melhorar o desempenho evitando o esforço em soluções que já são boas o suficiente, os resolvedores aceitam soluções (e alegam ter resolvido um problema) quando elas atendem às condições até determinadas tolerâncias.

Considere o problema de programação linear

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

e o problema duplo correspondente

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

Esse par de problemas tem uma solução primária ideal exclusiva de $ x_1 = 1, x_2 = 0 $ e $ y = -2 $ de solução dupla. Quais soluções podem ser aceitas como ideais por um solucionador? Para responder a isso, definimos as seguintes quantidades:

A lacuna de duplicação é a diferença entre o valor primário e o valor do objetivo duplo, nesse caso, $ |(-2x_1 - x_2) - y| $.
As inviabilidades primitivas são as violações das restrições primitivas, neste caso, $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\}) $.
As ineficiências duplas são as violações das restrições duplas, nesse caso, $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $.

Um solucionador declara uma solução como ideal se a lacuna de dualidade, as inviabilidades primárias e as inviabilidades duplas forem menores que uma determinada tolerância.¹

A aplicação das tolerâncias varia por motivos naturais e idiossincráticos em solucionadores e algoritmos. Por exemplo, a lacuna de dualidade no algoritmo simplex é determinada apenas pela imprecisão numérica, enquanto as inviabilidades primitivas e duplas estão presentes mesmo na aritmética exata. Alguns métodos aplicam diretamente as restrições de limites $ x_1 \ge 0, x_2 \ge 0, $ e $ y \le 0 $, enquanto outros tratam as violações de restrições de limites de forma diferente das violações de restrições lineares, como $x_1 + x_2 \le 1$. Para alguns solucionadores, as tolerâncias são otlerâncias ideais\eficitárias, ou seja, há um parâmetro $ \epsilga e

Para ver um exemplo do efeito das tolerâncias, considere uma tolerância absoluta de $ \epsilon = \frac{1}{2} $ aplicada ao par primal-dual acima. A solução $ x_1 = 1,5, x_2 = 0, y = -3 $ tem lacuna de dualidade zero e inviabilidades menores ou iguais a $ \epsilon $.Por isso, um solucionador pode declarar essa solução como "ideal". No entanto, o valor objetivo (-3) difere em 1 do valor real do objetivo ideal de -2. Os valores padrão típicos de $ \epsilon $ são entre $10^{-6}$ e $10^{-8}$, o que torna esses exemplos extremos raros, mas não impossíveis.

Tipos de soluções

Os problemas de LP podem ter mais de uma solução ideal, ainda mais ao considerar as tolerâncias. Discutiremos brevemente as propriedades das soluções retornadas pelas três famílias diferentes de algoritmos de LP apresentadas acima.

Os algoritmos simplex sempre retornam vértices ou pontos dos cantos da região viável. Essas soluções são preferenciais em algumas situações porque tendem a ser mais esparsas.

Os métodos de barreira e de primeira ordem geralmente não retornam vértices. A teoria fornece caracterizações adicionais que estão além do escopo deste guia.

Por motivos históricos e como as soluções de vértice têm propriedades atraentes, os solucionadores muitas vezes, por padrão, aplicam um procedimento de crossover para mover para um vértice ideal de uma solução encontrada por um algoritmo de barreira. No momento, o Crossover não é oferecido para soluções encontradas por métodos de primeira ordem.

Recomendações

Fazemos as recomendações a seguir para o uso avançado de solucionadores de LP.

Dimensionamento dos dados do problema

Os solucionadores podem ter convergência lenta ou falhas nos modelos por causa de problemas numéricos. Esses problemas podem surgir por muitos motivos. Confira um exemplo.

É comum que constantes numéricas muito pequenas ou grandes apareçam em modelos de LP. Estendendo o exemplo acima, se $x_1$ e $x_2$ representarem a fração de clientes atribuídos ao "provedor 1" ou "provedor 2", e se quisermos maximizar o benefício de atender esses clientes, é possível escrever a seguinte função de objetivo:

$$ \min -c_1x_1 - c_2x_2 $$

onde:

$ c_1 $ é o benefício de atribuir clientes ao provedor 1
$ c_2 $ é o benefício de atribuir clientes ao provedor 2

Os pares que atendem às seguintes restrições são considerados viáveis com uma tolerância absoluta $ \epsilon $:

$ y \le -c_1 + \epsilon $,
$ y \le -c_2 + \epsilon $.

Se as unidades de benefício de $ c_1 $ e $ c_2 $ forem pequenos valores fracionários que estão na mesma escala que $ \epsilon $, as condições duplas de viabilidade ficarão fracas e, portanto, um primal muito abaixo do ideal poderá ser declarado como ideal.

Se, por outro lado, as unidades de benefício forem "microdólares" (1.000.000 de microdólares = 1 dólar), os valores absolutos muito grandes resultantes solicitarão uma precisão muito alta na solução, possivelmente alta demais, dado os limites dos números de ponto flutuante. Os solucionadores podem não convergir se o problema for formulado dessa forma. Como parte da formulação de um problema bem-posicionado, os modeladores avançados precisam considerar se os dados do problema são dimensionados de maneira consistente com as tolerâncias do solucionador.

Além de evitar falhas numéricas, as tolerâncias também podem ser ajustadas para melhorar o desempenho. Os métodos simplex e de barreira não são muito sensíveis a tolerâncias, mas às vezes podem se beneficiar de tolerâncias maiores se for observado um progresso parado no final da solução. Por outro lado, os métodos de primeira ordem costumam ser muito mais sensíveis. Os usuários de métodos de primeira ordem podem se beneficiar de soluções mais rápidas relaxando as tolerâncias, conforme o contexto permite.

Para conhecer as tolerâncias de Glop, consulte primal_feasibility_tolerance, dual_feasibility_tolerance e solution_feasibility_tolerance em GlopParameters. Observe que primal_feasibility_tolerance e dual_feasibility_tolerance são usados no algoritmo, enquanto solution_feasibility_tolerance é verificado após a resolução para sinalizar problemas numéricos. Para PDLP, consulte eps_optimal_absolute e eps_optimal_relative.

Para ler mais sobre esses tipos de problemas, consulte as Diretrizes para problemas numéricos (em inglês) da Gurobi. Embora as diretrizes sejam escritas para usuários do Gurobi, muitos dos princípios se aplicam de maneira geral.

Opções de solucionadores e algoritmos

Começamos com um exemplo do tamanho do impacto da escolha de solucionadores e algoritmos e, em seguida, apresentamos um guia para a escolha de solucionadores de LP.

Variabilidade na prática

Ilustramos a variabilidade no desempenho nos algoritmos e solucionadores de LP comparando os tempos de solução em uma seleção de instâncias usadas por Hans Mittelmann para fazer comparativos de solucionadores de LP. As instâncias são explicitamente escolhidas para mostrar os extremos do desempenho relativo e não representam necessariamente o comportamento típico.

Os métodos primais e simplex duplos do Glop são comparados com o método de barreira de Gurobi (com e sem cruzamento, que encontra uma solução de vértice) e o PDLP, um método de primeira ordem, com alta e baixa precisão. A tabela abaixo informa tempos de resolução em segundos, com um limite de 20 minutos (1.200 segundos).

Instância	Glop Primal Simplex	Glop Dual Simplex	Barreira Gurobi com crossover	Barreira Gurobi sem crossover	PDLP Alta precisão	PDLP Baixa precisão
ex10	>1200	>1200	79.7	63.5	8.2	2.7
nug08-3o	>1200	252.8	144,6	3.2	1.1	0,9
savsched1	>1200	>1200	156.0	22.6	46.4	32.4
wide15	>1200	20,8	>1200	>1200	916,4	56.3
energia de construção	178.4	267.5	12.8	12.3	>1200	157.2
S250R10	12.1	520.6	15.2	16.4	>1200	>1200

Versão do solucionador	Ferramentas OR 9.3	Ferramentas OR 9.3	Gurobi 9.0	Gurobi 9.0	Ferramentas OR 9.3	Ferramentas OR 9.3
`solver_specific_parameters`	(padrões)	`use_dual_simplex: true`	`Method 2, Threads 1`	`Method 2, Crossover 0, Threads 1`	`termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 }`	`termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }`

A partir desses resultados, concluímos o seguinte.

O desempenho relativo dos algoritmos e solucionadores pode variar por ordens de magnitude em uma única instância.
Nenhum algoritmo e solucionador único é melhor que os outros de maneira uniforme.
O Crossover (ativado por padrão) aumenta o tempo de solução, às vezes de forma significativa.
O PDLP pode resolver o problema com precisão baixa, às vezes 10 vezes mais rápido do que com a alta precisão.

Um guia rápido para escolher solucionadores de LP

Como nenhum algoritmo ou solucionador de LP único é o melhor, recomendamos as etapas a seguir para descobrir o que é melhor para seu caso de uso. Comece com a primeira etapa e prossiga para a próxima se o desempenho não for suficiente.

Experimente o Glop. Motivo: o Glop é a implementação interna do Google dos métodos simplex primário e duplo. O Glop é de código aberto e confiável para as cargas de trabalho de produção do Google.
- Se a configuração padrão (simplex primário) não funcionar bem, tente alternar para simplex duplo usando use_dual_simplex: true.
Se uma licença estiver disponível, tente um solucionador comercial (CPLEX, Gurobi ou Xpress). Testar métodos simplex e de barreira. Motivo:esses solucionadores são padrão do setor e altamente otimizados. Além disso, os métodos de barreira complementam os algoritmos simplex oferecidos pelo Glop.
- Se estiver usando uma barreira, desative o "crossover" se não precisar de uma solução de vértice.
Teste o PDLP. Ajuste as tolerâncias de convergência para seu aplicativo. Motivo:o PDLP foi desenvolvido para os maiores problemas, em que os métodos simplex e de barreira atingem os limites de memória ou são muito lentos. O PDLP tem melhor desempenho quando uma solução aproximada, mas rápida, é preferível a uma solução exata, mas lenta.
Se você chegou até aqui, agora é um usuário avançado de LP! Consulte as opções de suporte das ferramentas OU para mais ajuda.

Geralmente é mais complexo do que isso. Os solucionadores geralmente verificam essas condições em uma versão transformada/simplificada do problema, chamada de problema resolvido. Em alguns casos, uma solução para o problema resolvido pode estar longe de uma solução para o problema de entrada. Essa situação pode levar a status incomuns, como OptimalInfeas do CPLEX ou IMPRECISE do Glop.↩