Pesquisadores descobrem uma forma de processar programação linear inteira mais rapidamente

Pesquisadores se aproximam de um novo limite de velocidade para a programação linear inteira

• A programação linear inteira (ILP) ajuda a encontrar soluções para diversos problemas do mundo real.
• Pesquisadores descobriram um novo método para executar ILP muito mais rapidamente.

Introdução ao problema do caixeiro-viajante

• O problema do caixeiro-viajante é um dos problemas computacionais mais antigos conhecidos e exige encontrar a rota ideal que passe por uma lista específica de cidades usando a menor quilometragem possível.
• Embora pareça simples, esse problema é notoriamente difícil, e a estratégia de força bruta de verificar todas as rotas possíveis se torna inviável quando o número de cidades passa de um pequeno conjunto.
• Em vez disso, aplica-se um modelo matemático rigoroso chamado programação linear para aproximar grosseiramente o problema como um conjunto de equações e verificar sistematicamente as combinações possíveis em busca da melhor solução.

A importância da programação linear inteira

• Às vezes, é necessário otimizar um problema usando números inteiros.
• A programação linear inteira (ILP) é popular em aplicações que envolvem decisões discretas, incluindo planejamento de produção, escalonamento de tripulações aéreas e roteamento de veículos.
• A ILP é central para a pesquisa operacional tanto na teoria quanto na prática, segundo o cientista da computação Santosh Vempala, do Georgia Institute of Technology.

Avanços nos algoritmos de ILP

• Ao longo de mais de 60 anos desde a formulação inicial da ILP, pesquisadores descobriram vários algoritmos para resolver problemas de ILP, mas todos exigiam um número relativamente lento de etapas.
• Um trabalho recente de Victor Reis e Thomas Rothvoss trouxe o maior salto em tempo de execução em décadas.
• Eles combinaram ferramentas geométricas para restringir as soluções possíveis e criaram um novo algoritmo mais rápido que resolve ILP em praticamente o mesmo tempo que o caso binário.

Como os problemas de ILP são resolvidos

• A ILP transforma um problema dado em uma série de equações lineares, e essas equações precisam satisfazer algumas desigualdades.
• Essas equações se baseiam nos detalhes do problema original, mas a estrutura básica dos problemas de ILP é a mesma, oferecendo aos pesquisadores um método único para atacar uma grande variedade de problemas.

Entendimento teórico dos algoritmos de ILP

• O novo algoritmo ainda não foi usado para resolver problemas logísticos reais, mas isso não diminui a importância de compreender essas questões teóricas.
• Os pesquisadores continuam esperançosos de que a eficiência computacional da ILP possa melhorar ainda mais, embora isso exija ideias fundamentalmente novas.

Opinião do GN⁺

• Esta pesquisa representa um avanço importante na interseção entre ciência da computação e matemática. Em especial, ela tem potencial para melhorar significativamente a eficiência da ILP usada na resolução de problemas logísticos complexos.
• Embora o novo algoritmo ainda exija muito trabalho antes de chegar a aplicações práticas, o avanço na compreensão teórica pode contribuir de forma importante para futuras melhorias algorítmicas e para o desenvolvimento de tecnologias relacionadas.
• Este artigo traz uma notícia interessante para pesquisadores da área de ciência da computação e para pessoas interessadas em resolução matemática de problemas, destacando a importância de novas abordagens para enfrentar desafios complexos.

[GN⁺]

Comentários do Hacker News

• Reduzir o limite superior algorítmico de problemas NP-completos é algo muito interessante, mas pode não estar diretamente relacionado a melhorar o tempo de execução na resolução de problemas reais.

  • Solvers de programação inteira mista (MIP) usam vários algoritmos e heurísticas.
  • A construção de uma biblioteca de heurísticas e estratégias é o motivo pelo qual as melhorias em solvers de MIP superam a Lei de Moore.
  • De 1990 a 2014, as melhorias de hardware foram de 6500 vezes, mas o software foi responsável por um ganho de desempenho de 870000 vezes.
  • O artigo citado pode ser mais uma peça do quebra-cabeça no avanço contínuo de desempenho dos solvers de MIP, mas isso não é certo.

• O novo algoritmo ainda não foi usado para resolver problemas logísticos reais.

  • Isso porque exigiria trabalho demais para atualizar os programas atuais.
  • Mas, segundo Rothvoss, trata-se de um entendimento teórico de um problema com aplicações fundamentais.

• O título "Integer Linear Programming" precisa explicitar isso porque a parte inteira é muito mais importante.

  • Algoritmos em tempo polinomial para programação linear são conhecidos há décadas, mas programação linear inteira é NP-difícil.

• Engenheiros de software deveriam aprender sobre programação linear.

  • Muitos problemas podem ser expressos como otimização linear.
  • Por exemplo, é possível resolver com programação linear o problema do número médio mínimo de trocas para posicionar corretamente as bolas de bilhar na configuração inicial triangular.

• Este artigo não analisa diretamente Space Groups, mas seria interessante investigar se ele pode ser usado para generalizar a simplificação do "espaço" do problema.

  • O autor, como arquiteto e não matemático, mas alguém que observa caminhos por colmeias geradas, sugere que esse resultado merece mais investigação.

• Um trecho do livro de Sapolsky sobre o problema do caixeiro-viajante, "Determined: A Science of Life without Free Will", pode não ser relevante para desenvolvedores de software, mas ainda assim é fascinante.

  • As formigas verificam oito locais em busca de alimento, o que é uma versão do famoso "problema do caixeiro-viajante".
  • Cientistas da computação podem usar "formigas virtuais" para resolver esse tipo de problema, algo hoje conhecido como inteligência de enxame.

• O autor estudou pesquisa operacional em Stanford em 1985/86 e teve aulas com George Dantzig, mas acabou se tornando engenheiro de software, não pesquisador de operações.

  • É interessante ver quanto se aprendeu sobre algoritmos de programação linear.

• Muitos problemas de otimização discreta podem ser convertidos em programas lineares.

  • É um conjunto de ferramentas extremamente poderoso, como os solvers SAT.

• A complexidade teórica sugere que métodos de ponto interior podem ser melhores para LP do que o simplex, mas, na prática, um simplex bem ajustado quase sempre vence.