Pesquisa traz a primeira indicação teórica de que o algoritmo é garantidamente eficiente para muitos problemas de Programação Inteira
O artigo “Branch-and-Bound Solves Random Binary IPs in Polytime”, do professor do Departamento de Informática (DI) Marco Molinaro, foi publicado na conferência internacional Symposium on Discrete Algorithms (SODA) 2021, um dos eventos mais relevantes de computação do mundo e carro-chefe na área de algoritmos. A pesquisa, realizada em conjunto com o professor do Instituto de Tecnologia da Georgia (EUA) Santanu Dey e com o doutorando da mesma universidade Yatharth Dubey, traz a primeira indicação teórica de que o algoritmo Branch-and-Bound é garantidamente eficiente para muitos problemas de Programação Inteira (PI).
Molinaro e os demais co-autores começaram a trabalhar no tema há cerca de um ano e meio. “Levamos um tempo até formular uma questão concreta adequada para ser atacada, e mais um tempo até aprendermos as ferramentas técnicas que pareciam úteis, e finalmente chegamos à nossa análise teórica do Branch-and-Bound”, disse o professor do DI.
Entenda a pesquisa
Segundo Molinaro, o modelo de Programação Inteira (PI) pode ser utilizado para modelar os mais diversos problemas de otimização. Ele é muito usado para oferecer suporte de decisão na prática de áreas como logística, mineração, energia e esportes. “Como exemplo concreto, PI pode modelar o problema de decidir como uma frota de veículo deve realizar entregas a serem feitas de forma a minimizar o tempo de espera do cliente”, explicou.
Depois de modelar um problema como PI, é necessário utilizar um algoritmo para resolvê-lo. Nesse caso, o algoritmo utilizado na prática é o chamado Branch-and-Bound. “De uma forma ‘esperta’, o Branch-and-Bound enumera parcialmente o espaço de todas as soluções possíveis para encontrar a melhor.”
Ainda de acordo com o professor, existem exemplos de PI nos quais esse algoritmo é ineficiente, porque ele leva tempo exponencial até encontrar a melhor solução – e isso já é esperado, devido à generalidade de PIs.
Porém, em modelos encontrados na prática, Branch-and-Bound funciona surpreendentemente bem. Para grande parte dos problemas do tipo “empacotamento”, por exemplo, o algoritmo encontra a melhor solução em tempo polinomial.
“Uma consequência desse resultado é entendermos melhor em quais situações e/ou modelos o (essencialmente único) algoritmo disponível consegue encontrar a solução desejada em tempo hábil”, disse Molinaro. Para ele, a solução gera informações que ajudam a desenhar novos algoritmos que sejam mais eficientes nos lugares onde Branch-and-Bound deixa a desejar.
“Além disso, esse tipo de trabalho teórico nos força a entender os mecanismos de funcionamento do Branch-and-Bound, novamente importante para encontrar as fontes das suas limitações e gerar ideias de como melhorá-lo.”
Repercussão
Além da publicação na conferência SODA 2021, o artigo também foi selecionado para compor uma edição especial do periódico “ACM Transactions On Algorithms”, que reúne os melhores artigos do simpósio.
Molinaro também destaca a existência de novos trabalhos baseados no artigo, e espera que ele estimule ainda mais o progresso no entendimento de algoritmos eficientes para PI.
Por fim, os resultados divulgados no artigo também são de grande contribuição para a coletividade, podendo interferir diretamente no dia a dia das pessoas. “Algoritmos mais eficientes podem gerar grande impacto prático, pois podemos resolver modelos mais detalhados que levem à utilização mais eficiente dos recursos disponíveis na sociedade, desde recursos não renováveis, como combustíveis fósseis, ao próprio tempo das pessoas.”