Pesquisadores abordam novo limite de velocidade para problema seminal | Revista Quanta

O problema do caixeiro viajante é uma das questões computacionais mais antigas conhecidas. Pede o percurso ideal através de uma determinada lista de cidades, minimizando a quilometragem. Apesar de parecer simples, o problema é notoriamente difícil. Embora você possa usar a força bruta para verificar todas as rotas possíveis até encontrar o caminho mais curto, tal estratégia se torna insustentável depois de apenas algumas cidades. Em vez disso, você pode aplicar um modelo matemático rigoroso chamado programação linear, que aproxima aproximadamente o problema de um conjunto de equações e verifica metodicamente as combinações possíveis para encontrar a melhor solução.

Mas às vezes é necessário otimizar problemas que envolvem valores de números inteiros. Para que serve um plano de otimização de fábrica que fabrica 500.7 sofás? Para isso, os pesquisadores recorrem frequentemente a uma variante da programação linear chamada programação linear inteira (ILP). É popular em aplicações que envolvem decisões discretas, incluindo planejamento de produção, programação de tripulações aéreas e roteamento de veículos. “Basicamente, a ILP é o pão com manteiga da pesquisa operacional, tanto na teoria quanto na prática”, disse Santosh Vempala, cientista da computação do Instituto de Tecnologia da Geórgia.

Desde que formularam o ILP pela primeira vez mais de 60 anos atrás, os pesquisadores descobriram vários algoritmos que resolvem problemas de PLI, mas todos eles têm sido relativamente lentos em termos do número de etapas necessárias. A melhor versão que conseguiram encontrar - uma espécie de limite de velocidade - vem do caso trivial em que as variáveis ​​do problema (como se um vendedor visita uma cidade ou não) só podem assumir valores binários (zero ou 1). Nesse caso, o ILP possui um tempo de execução que escala exponencialmente com o número de variáveis, também chamado de dimensão. (Se houver apenas uma variável, são necessários apenas dois passos para testar todas as combinações possíveis e resolver o problema; duas variáveis ​​significam quatro passos, três significam oito passos, e assim por diante.)

Infelizmente, uma vez que as variáveis ​​assumem um valor além de zero e 1, o tempo de execução do algoritmo aumenta muito mais. Os pesquisadores há muito se perguntam se conseguiriam chegar mais perto do ideal trivial. O progresso tem sido lento, com a registro definido na década de 1980 e apenas incremental melhorias feito desde então.

Mas recente trabalho by Victor Reis, atualmente no Instituto de Estudos Avançados, e Thomas Rothvoss, da Universidade de Washington, deu o maior salto no tempo de execução em décadas. Ao combinar ferramentas geométricas para limitar as soluções possíveis, eles criaram um algoritmo novo e mais rápido para resolver ILP quase ao mesmo tempo que o caso binário trivial. O resultado recebeu o prêmio de melhor artigo no 2023 Fundamentos da Ciência da Computação conferência.

“Este novo algoritmo é extremamente emocionante”, disse Noah Stephens-Davidowitz, matemático e cientista da computação da Universidade Cornell. “Isso representa a primeira [grande] melhoria nos solucionadores de ILP em quase 40 anos.”

O PLI funciona transformando um determinado problema em um conjunto de equações lineares que devem satisfazer algumas desigualdades. As equações específicas são baseadas nos detalhes do problema original. Mas embora estes detalhes possam diferir, a composição básica dos problemas de PLI permanece a mesma, dando aos investigadores uma forma única de atacar uma multiplicidade de problemas.

Isso não quer dizer que seja um trabalho fácil. Foi somente em 1983 que o matemático Hendrik Lenstra provou que o problema geral era até solucionável, fornecendo o primeiro algoritmo que poderia fazê-lo. Lenstra pensou na ILP de forma geométrica. Primeiro, ele transformou as desigualdades no cerne do ILP em uma forma convexa, como qualquer polígono regular. Esta forma representa as restrições do problema individual que você está resolvendo, seja a produção de sofás ou a programação de companhias aéreas, portanto o interior da forma corresponde a todos os valores possíveis que poderiam resolver as desigualdades e, portanto, o problema. Lenstra chamou essa forma de corpo convexo. A dimensão do problema influencia a dimensão desta forma: Com duas variáveis ​​assume a forma de um polígono plano; em três dimensões é um Sólido platônico, E assim por diante.

A seguir, Lenstra imaginou todos os inteiros como um conjunto infinito de pontos de grade, conhecido em matemática como rede. Uma versão bidimensional parece um mar de pontos, e em três dimensões parece os pontos onde as vigas de aço de um edifício se conectam. A dimensão da rede também depende da dimensão de um determinado problema.

Para resolver um determinado problema de ILP, Lenstra mostrou que basta procurar onde as soluções possíveis encontram o conjunto de inteiros: na intersecção do corpo convexo e da rede. E ele criou um algoritmo que poderia pesquisar esse espaço exaustivamente — mas, para ser eficaz, às vezes era necessário dividir o problema em partes de dimensões menores, acrescentando muitas etapas ao tempo de execução.

Nos anos seguintes, vários pesquisadores exploraram como fazer esse algoritmo funcionar mais rápido. Em 1988 Ravi Kannan e László Lovász introduziram um conceito chamado raio de cobertura emprestado do estudo de códigos de correção de erros, para ajudar o corpo convexo e a rede a se cruzarem com mais eficiência. Grosso modo, o raio de cobertura garante que o corpo convexo sempre contenha pelo menos um ponto inteiro, não importa onde você o coloque na rede. Como resultado, o tamanho do raio de cobertura também determina a eficiência com que você pode resolver o problema de ILP.

Então tudo se resumia a determinar o tamanho do raio de cobertura ideal. Infelizmente, isto provou ser um problema difícil por si só, e o melhor que Kannan e Lovász puderam fazer foi restringir um valor possível procurando os limites superior e inferior. Eles mostraram que o limite superior – o tamanho máximo do raio de cobertura – aumentou linearmente com a dimensão. Isso foi muito rápido, mas não o suficiente para acelerar significativamente o tempo de execução do ILP. Nos 30 anos seguintes, outros pesquisadores só conseguiram fazer um pouco melhor.

O que finalmente ajudou Reis e Rothvoss a avançar foi um resultado matemático não relacionado que se concentrou puramente em redes. Em 2016, Oded Regev e Stephens-Davidowitz mostrou, na verdade, quantos pontos da rede poderiam caber em uma forma específica. Reis e Rothvoss aplicaram isso a outras formas, o que lhes permitiu estimar melhor o número de pontos da rede contidos em um raio de cobertura do ILP, diminuindo o limite superior. “A última inovação veio com a constatação de que é possível criar outros tipos de formas”, disse Regev.

Este novo limite superior mais rígido foi uma grande melhoria, permitindo que Reis e Rothvoss alcançassem uma aceleração dramática do algoritmo ILP geral. O trabalho deles traz o tempo de execução para (log n)^O(n), Onde n é o número de variáveis ​​e O (n)significa que ele escala linearmente com n. (Esta expressão é considerada “quase” igual ao tempo de execução do problema binário.)

“É um triunfo na intersecção da matemática, ciência da computação e geometria”, disse Daniel Dadush do instituto nacional de pesquisa CWI na Holanda, que ajudou a criar o algoritmo que Reis e Rothvoss usaram para medir o tempo de execução do ILP.

Por enquanto, o novo algoritmo não foi realmente usado para resolver quaisquer problemas logísticos, uma vez que seria necessário muito trabalho para atualizar os programas atuais para utilizá-lo. Mas para Rothvoss isso não vem ao caso. “Trata-se da compreensão teórica de um problema que tem aplicações fundamentais”, disse ele.

Quanto à possibilidade de melhorar ainda mais a eficiência computacional do ILP, os pesquisadores ainda estão esperançosos de que continuarão se aproximando do tempo de execução ideal – mas não tão cedo. “Isso exigiria uma ideia fundamentalmente nova”, disse Vempala.