Pesquisadores descobrem uma forma de processar programação linear inteira mais rápido
(quantamagazine.org)- Em problemas de otimização que exigem decisões em unidades inteiras, como planejamento de produção, escala de tripulação e roteamento de veículos, Victor Reis e Thomas Rothvoss apresentaram um novo algoritmo que reduz significativamente o tempo de execução de ILP
- Como a ILP é mais difícil do que a programação linear comum, e quase não houve melhorias recordes desde os anos 1980, este resultado está sendo visto como um grande avanço em décadas
- A nova abordagem combina ferramentas geométricas para lidar com a interseção entre reticulados e corpos convexos, restringindo com mais força o intervalo de soluções inteiras possíveis
- O ponto central é o uso de um resultado de 2016 sobre pontos de reticulado para reduzir o limite superior do covering radius, levando o tempo de execução a cerca de ((\log n)^{O(n)})
- Ainda não foi aplicado diretamente a sistemas logísticos reais, mas o resultado chega muito perto do limite teórico de velocidade da ILP e indica uma direção de longo prazo para melhorar solvers usados na prática
Por que restrições inteiras tornam a otimização mais difícil
- O problema do caixeiro-viajante é um antigo problema computacional de encontrar a rota mais curta passando por várias cidades, e verificar todas as rotas possíveis se torna inviável mesmo com um pequeno aumento no número de cidades
- Programação linear é um modelo matemático que trata sistematicamente combinações possíveis por meio de equações e desigualdades
- Em problemas reais de otimização, muitas vezes respostas com casas decimais não são úteis
- Em um plano ótimo de fábrica, uma resposta mandando produzir 500,7 sofás é difícil de transformar em uma decisão real
- Programação linear inteira (ILP) é uma variação da programação linear com esse tipo de restrição de integralidade, e é amplamente usada em problemas de decisão discreta como planejamento de produção, escalas de tripulação aérea e definição de rotas de veículos
- Santosh Vempala vê a ILP como uma ferramenta central na pesquisa operacional, tanto na teoria quanto na prática
Limites de velocidade que melhoraram pouco desde os anos 1980
- Desde que a ILP foi formalizada, há mais de 60 anos, vários algoritmos foram propostos, mas ela continuou relativamente lenta em termos do número de etapas necessárias
- O ponto de referência mais simples é o caso de variáveis binárias, em que cada variável só pode assumir 0 ou 1
- 1 variável tem 2 combinações possíveis
- 2 variáveis têm 4
- 3 variáveis têm 8
- Em geral, o tempo de execução cresce exponencialmente com o número de variáveis, isto é, com a dimensão
- Quando as variáveis podem assumir valores inteiros mais amplos além de 0 e 1, o tempo de execução fica muito maior
- Há muito tempo os pesquisadores investigam se é possível aproximar a velocidade da ILP geral da velocidade desse caso binário mais simples
- Depois do recorde dos anos 1980, vieram apenas melhorias graduais
A interpretação geométrica aberta por Lenstra
- Em 1983, Hendrik Lenstra provou que o problema geral de ILP pode ser resolvido e apresentou o primeiro algoritmo para isso
- Lenstra reformulou a ILP como um problema geométrico
- As desigualdades de uma ILP são representadas por uma forma convexa, isto é, um corpo convexo (convex body)
- O interior da forma corresponde a todos os valores possíveis que podem satisfazer as desigualdades
- Um problema com 2 variáveis vira um polígono no plano; com 3 variáveis, um sólido tridimensional; e assim por diante conforme a dimensão aumenta
- Todo número inteiro pode ser visto matematicamente como um ponto de um reticulado (lattice)
- Em 2 dimensões, isso parece um mar de pontos
- Em 3 dimensões, vira uma estrutura parecida com os pontos de encontro de uma armação metálica
- No fim, resolver uma ILP passa a ser encontrar a interseção entre o corpo convexo e o reticulado, isto é, onde as soluções possíveis coincidem com pontos inteiros
- O algoritmo de Lenstra conseguia explorar esse espaço, mas às vezes precisava dividir o problema em partes de dimensão menor para ganhar eficiência, e esse processo aumentava o tempo de execução
Como o covering radius criou um gargalo de 30 anos
- Em 1988, Ravi Kannan e László Lovász tentaram tratar de forma mais eficiente a interseção entre corpos convexos e reticulados usando o conceito de covering radius, vindo da pesquisa em códigos de correção de erros
- O covering radius está relacionado ao tamanho necessário para garantir que, não importa onde um corpo convexo seja colocado sobre o reticulado, ele contenha pelo menos um ponto inteiro
- O tamanho desse valor determina quão eficientemente um problema de ILP pode ser resolvido
- Descobrir o covering radius ideal em si já era um problema difícil
- Kannan e Lovász restringiram os valores possíveis com limites superior e inferior, mostrando que o limite superior cresce linearmente com a dimensão
- Só isso não bastou para reduzir muito o tempo de execução da ILP, e as melhorias permaneceram limitadas pelos 30 anos seguintes
O novo algoritmo de Reis e Rothvoss
- Victor Reis e Thomas Rothvoss abriram caminho usando um resultado matemático separado, focado em reticulados
- Em 2016, Oded Regev e Noah Stephens-Davidowitz mostraram quantos pontos de reticulado podem caber dentro de certas formas
- Reis e Rothvoss aplicaram esse resultado a outras formas para estimar melhor quantos pontos de reticulado ficam dentro do covering radius da ILP
- Com essa estimativa, o limite superior caiu, e o tempo total de execução do algoritmo de ILP diminuiu bastante
- O novo tempo de execução é ((\log n)^{O(n)}), em que (n) é o número de variáveis e (O(n)) é proporcional linearmente a (n)
- Essa expressão é considerada “quase” do mesmo nível do tempo de execução do problema com variáveis binárias
A distância entre o avanço teórico e a aplicação prática
- Noah Stephens-Davidowitz vê o novo algoritmo como a primeira grande melhoria em solvers de ILP em quase 40 anos
- Daniel Dadush avalia o resultado como um feito surgido na interseção entre matemática, ciência da computação e geometria
- O novo algoritmo ainda não foi usado para resolver problemas logísticos reais
- Atualizar os programas atuais para se adequarem a essa abordagem exigiria muito trabalho
- Rothvoss considera que o foco deste resultado está na compreensão teórica de um problema com aplicações fundamentais
- Ainda existe a possibilidade de tornar os cálculos de ILP mais eficientes, mas Vempala acredita que, para chegar mais perto do tempo de execução ideal, serão necessárias ideias fundamentalmente novas
1 comentários
Comentários do Hacker News
Reduzir o limite superior algorítmico de um problema central NP-completo é sempre muito interessante, mas isso não necessariamente significa que o problema será resolvido mais rápido em implementações reais.
Solvers de programação inteira mista (MIP) usam muitos algoritmos em conjunto com uma grande quantidade de heurísticas, e o acúmulo de bibliotecas de heurísticas e estratégias é um dos principais motivos pelos quais as melhorias em solvers de MIP vêm superando a Lei de Moore.
Segundo https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/6..., entre 1990 e 2014, as melhorias de hardware foram de 6500 vezes, enquanto as melhorias de software contribuíram para um ganho de desempenho de 870000 vezes.
Este artigo também pode ser uma peça do quebra-cabeça que continuará melhorando o desempenho dos solvers de MIP, mas não há garantia de que isso aconteça.
Não entendo muito bem a explicação de que o novo algoritmo ainda não foi usado para resolver problemas de logística porque “atualizar os programas atuais exigiria trabalho demais”.
A maioria dos modelos específicos de domínio chama solvers como Gurobi, CPLEX e FICO para problemas grandes, e usa solvers open source como SCIP para problemas pequenos.
É possível trocar modelos entre esses solvers no formato MPS padrão, e a formulação do problema não muda; não bastaria mudar apenas o método interno de solução do solver?
Se a ideia é que uma nova implementação é necessária, então os benefícios para o mundo ao implementá-la também parecem enormes.
Essas ferramentas são produtos de engenharia extremamente complexos, acumulando décadas de melhorias incrementais, então descobrir como integrar essa nova descoberta a esses motores provavelmente exigiria um esforço considerável de pesquisa por si só.
É verdade que existem maneiras padronizadas de trocar formulações de problemas por meio de formatos como MPS, e hoje em dia parece que linguagens de modelagem algébrica como AMPL são mais usadas, mas o que esses formatos fornecem é apenas uma formulação matemática padronizada.
A solução em si é altamente específica de cada solver, com suas próprias estruturas de dados, algoritmos e técnicas heurísticas.
Eles não são intercambiáveis, nem são intencionalmente expostos, e não dá para simplesmente inserir alguns números externos no meio do processo sem conhecer o código do solver e todo o fluxo.
Queria esclarecer o mal-entendido.
Sempre que possível, eu evitaria implementar diretamente coisas nesses projetos.
Ainda assim, isso não muda o fato de ser um excelente resultado.
Do ponto de vista da complexidade computacional teórica, os melhores algoritmos para “programação linear inteira” [2] são baseados em reticulados e têm a melhor complexidade de pior caso em notação O grande.
Mas as implementações atuais geralmente (1) exigem aritmética racional de precisão arbitrária, como a gmplib [3], o que consome muita memória e também é lento na prática, e (2) exigem etapas de redução de reticulado do tipo LLL [4], que não conseguem aproveitar a esparsidade das matrizes.
Como resultado, esses algoritmos normalmente nem cabem na memória para problemas com matrizes maiores que 1000x1000 e, mesmo quando cabem, são lentos demais.
Solvers de programação inteira usados na prática, em vez disso, se baseiam em branch-and-bound, um algoritmo de retrocesso semelhante aos usados em solução SAT, e a cada iteração resolvem um problema de “programação linear” obtido a partir do problema original ao trocar todas as variáveis por variáveis contínuas.
Cada problema de programação linear pode ser resolvido por algoritmos de tempo polinomial, como métodos de pontos interiores, mas na prática usa-se o método simplex, que tem tempo exponencial no pior caso.
O motivo é que os problemas de programação linear a serem resolvidos são muito parecidos entre si, e o método simplex aproveita isso muito bem na prática.
Além disso, os algoritmos relacionados exploram fortemente a esparsidade de vetores e matrizes.
Por isso, algumas pessoas conseguem resolver problemas de programação inteira com milhões de variáveis em poucos dias, ou até em poucas horas.
Implementadores de solvers não estão perseguindo a complexidade teórica absolutamente melhor, e pode-se dizer que a teoria e a prática da otimização discreta se separaram em certa medida.
Ainda assim, o artigo de Reis & Rothvoss [1] é um trabalho matemático profundo e, para quem se interessa por matemática discreta, é muito impressionante por si só.
Ele resolveu uma conjectura de Dadush de 10 anos e foi apresentado em novembro do ano passado na FOCS, uma das duas principais conferências de teoria da ciência da computação.
A utilidade prática direta não é o ponto central, e os próprios autores provavelmente admitiriam isso em conversas informais.
Claro que em propostas de financiamento de pesquisa diriam outra coisa, mas isso faz parte do jogo.
Isso não quer dizer que seja inútil; só avançar o conhecimento matemático já tem grande valor, e pesquisadores de algumas gerações futuras talvez criem algoritmos práticos com base nessas ideias e empurrem o estado da arte dos solvers adiante.
No fim das contas, todos esses algoritmos têm tempo exponencial no pior caso.
Na teoria, tenta-se reduzir um pouco o polinômio que aparece no expoente da complexidade de pior caso, mas na prática normalmente se quer resolver um único grande problema de otimização, não uma família de problemas em que o tamanho n cresce.
Mais importante do que a taxa de crescimento da linha de tendência do tempo de solução é conseguir resolver aquela grande instância à sua frente, e essa instância normalmente tem uma estrutura que impede que ela seja um pior caso entre as de mesmo tamanho.
Por isso, as escolhas de engenharia também são diferentes.
[1] https://arxiv.org/abs/2303.14605
[2] min { c^T x : A x >= b, x in R^n, some components of x in Z }
[3] https://gmplib.org/
[4] https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.p...
O resumo é mais informativo: https://arxiv.org/abs/2303.14605
O conteúdo é que eles obtiveram um algoritmo aleatorizado em tempo (log(2n))^O(n) para resolver programação inteira com n variáveis
Ou seja, este trabalho é um resultado teórico que, com base na análise da estrutura de corpos convexos em R^n e de como cobri-los com uma malha inteira, apresenta um algoritmo de tempo exponencial melhor que o melhor anterior
A maioria dos trabalhos práticos de ILP usa heurísticas e branch-and-bound, e aproveita a estrutura especial da formulação específica do problema
Não está claro se esta pesquisa ajudará em qualquer uma dessas duas coisas, e acho que seria difícil julgar apenas lendo o artigo, a menos que alguém de um lugar como a Gurobi explique
É um detalhe pequeno, mas o título deveria especificar programação linear inteira
Porque aqui a parte “inteira” faz uma diferença muito maior
Para programação linear, algoritmos de tempo polinomial já são conhecidos há décadas, enquanto a programação linear inteira é NP-difícil
Programação linear contínua também é difícil
Não no sentido de ser NP-difícil, mas no sentido de que criar solvers de LP modernos e eficientes envolve muito de algoritmos e engenharia
Só a computação numérica já é suficientemente complexa
E muitos solvers de programação linear inteira são baseados em solvers de programação linear contínua
Se você é engenheiro de software interessado em machine learning ou algoritmos, vale a pena aprender programação linear
Uma quantidade surpreendente de problemas pode ser formulada como otimização linear
Por exemplo, na faculdade conversei com um amigo formado em engenharia industrial sobre o número mínimo médio de trocas necessário para colocar bolas de bilhar em posições iniciais válidas dentro do triângulo do rack
Nós dois escrevemos programas para resolver isso por amostragem de Monte Carlo; a minha solução fazia BFS no espaço de estados do grafo, e a dele usava programação linear
Provavelmente a solução dele era mais eficiente
Exemplos incluem árvore geradora mínima, emparelhamento em grafos bipartidos ou gerais, fluxo em redes, interseção de matroides, fluxos submodulares etc.
As soluções de vértice de certos LPs também têm propriedades interessantes que podem ser aproveitadas ao projetar algoritmos de aproximação para problemas NP-completos
Por exemplo, é possível provar que, em uma solução de vértice para o problema Steiner forest, sempre existe uma variável com valor de pelo menos 1/2; então, ao arredondar variáveis iterativamente e resolver o LP novamente, obtém-se um algoritmo de aproximação 2
Na pós-graduação, esse era o único algoritmo de aproximação 2 conhecido para esse problema
Outro ponto interessante é que, se você tiver apenas um oráculo de separação em tempo polinomial, consegue resolver um LP mesmo com um número exponencial de restrições
Foi muito divertido e eu recomendo
Mesmo hoje há uma sobreposição surpreendentemente grande com pesquisa operacional, mas é chocante como muitos formados em engenharia industrial não sabem programar direito
É realmente uma pena
Lembro que a parte inteira era bem importante, porque normalmente só se podia negociar em valores inteiros de centavos
É um texto curto, mas bom
Ainda não olhei a matemática a fundo, mas o preprint parece ser este: https://arxiv.org/pdf/2303.14605.pdf
Não parece que estejam olhando diretamente para grupos espaciais como uma forma de generalizar e simplificar o “espaço” do problema reduzindo simetrias ou repetições, mas seria interessante ver se esse tipo de estrutura poderia ser aplicado
Como alguém que usa software que aplica grupos espaciais e descreve as células de Voronoi ao redor de pontos, ou conjuntos de pontos, distribuídos dentro deles, estou acostumado com a forma “assustadora” como os efeitos se propagam [1]
Não sou matemático, sou apenas arquiteto, então essa área está fora da minha competência, mas, como alguém que observa caminhos atravessando estruturas de colmeia geradas, este resultado merece investigação adicional
[0] https://arxiv.org/pdf/2303.14605.pdf
[1] Se você conhece algum matemático que queira colaborar nesse tipo de trabalho, seria bom entrar em contato
É um trabalho em andamento e, como eu disse, matematicamente está fora da minha competência, mas encontrei propriedades interessantes que um verdadeiro especialista poderia examinar mais a fundo
Em relação ao problema do caixeiro-viajante, é interessante a citação do livro mais recente de Sapolsky, Determined: A Science of Life without Free Will
Não sei o quanto isso é relevante para desenvolvedores de software, mas é fascinante
Quando uma formiga verifica oito locais em busca de alimento, idealmente ela deveria visitar cada lugar apenas uma vez e escolher a rota mais curta entre os 5.040 caminhos possíveis, isto é, 7!
Isso é uma forma do famoso problema do caixeiro-viajante, no qual matemáticos vêm trabalhando há séculos sem encontrar uma solução geral
Uma estratégia é a força bruta: examinar e comparar todos os caminhos possíveis para escolher o melhor, mas, com apenas 10 pontos a visitar, já há mais de 360 mil possibilidades, e com 15 pontos são mais de 80 bilhões
No entanto, ao soltar cerca de 10 mil formigas, o tamanho típico de uma colônia, no problema dos oito pontos de comida, mesmo que nenhuma formiga saiba mais do que o caminho que percorreu e duas regras, elas encontram, entre as 5.040 possibilidades, uma solução quase ótima em muito menos tempo do que a força bruta
Esse método funciona tão bem que cientistas da computação também resolvem problemas desse tipo com “formigas virtuais”, algo hoje conhecido como inteligência de enxame
E a reação padrão é: “algoritmos de computador muito simples também fazem isso”
No problema do caixeiro-viajante com distância euclidiana, isto é, quando cada nó tem coordenadas fixas e o custo da rota é a distância euclidiana entre dois pontos, também é possível fornecer um algoritmo em tempo polinomial que encontra uma rota dentro de um fator ε da solução ótima
Só que ele é exponencial em relação a ε
O prefácio também traz uma excelente ressalva
“Pessoalmente, acreditamos que a literatura da área deveria ter menos marsupiais e mais matemática, e que, como comunidade, deveríamos superar esse período rico em metáforas, de modo semelhante a como a química superou a alquimia. No entanto, esta lista não faz nenhuma afirmação sobre a qualidade científica dos artigos listados.”
[1]: https://fcampelo.github.io/EC-Bestiary/
É um algoritmo modelado a partir desse tipo de comportamento de colônias de formigas
Como outros disseram, ele é bom para encontrar ótimos locais, assim como busca tabu, recozimento simulado e algoritmos genéticos
Para a maioria dos objetivos de negócio, como o exemplo da “produção de sofás” citado no artigo, isso é suficiente
Mas é diferente de encontrar uma “solução geral”
Parece um pouco enganoso Sapolsky comparar nossa dificuldade em encontrar “soluções gerais” com a capacidade das formigas de encontrar ótimos locais
Não significa que a forma geral do problema não seja NP-difícil; significa que, ao acrescentar mais informação, torna-se possível aproximar soluções boas o bastante ou tornar a busca ótima tratável
Essa perspectiva foi especialmente marcante durante a primeira “revolução” da IA, quando estava em voga ver a IA como um problema de busca reforçado por conhecimento humano
É essa a “inteligência de enxame” de que o livro está falando?
Muitos problemas de otimização discreta podem ser traduzidos para programação linear
Assim como solucionadores SAT, é uma ferramenta realmente poderosa para se conhecer
Como desenvolvedor, foi um daqueles momentos de “como eu deixei isso passar até agora?”
É um ótimo resultado, mas provavelmente não será prático
É parecido com o fato de que, em programação linear, os métodos de pontos interiores têm complexidade teórica melhor que o método simplex, mas, na prática, um simplex bem ajustado quase sempre vence
Existe uma “razão” amplamente aceita para os métodos de pontos interiores geralmente serem mais lentos na prática?
Parece que atravessar o interior deveria chegar mais rápido a uma boa solução do que ficar preso à fronteira, embora talvez essa diferença importe menos em dimensões altas
A formulação usada aqui é um pouco confusa
Há uma frase que diz: “a melhor versão que eles conseguiram imaginar, uma espécie de limite de velocidade, vem de um caso trivial em que as variáveis do problema só podem assumir valores binários, isto é, 0 ou 1, como no caso de o caixeiro-viajante visitar ou não uma cidade”; eles estão chamando um problema NP-completo de caso trivial?
Pelo que eu sabia, todo ILP pode ser reduzido a 01-ILP e vice-versa
E, pela parte “infelizmente, quando as variáveis assumem valores além de 0 e 1, o tempo de execução do algoritmo aumenta muito. Pesquisadores há muito se perguntam se seria possível chegar mais perto desse ideal trivial”, fico me perguntando se este trabalho é um solver que melhora o limite inferior de 01-ILP, ou um algoritmo que aproxima mais a fronteira entre 01-ILP e ILP geral