Pesquisadores do MIT e ETH Zurich desenvolveram uma técnica baseada em aprendizado de máquina para acelerar o processo de otimização usado por empresas como a FedEx para roteamento de pacotes. Essa abordagem, que simplifica uma etapa fundamental nos solucionadores de programação linear inteira mista (MILP) e adapta o processo usando os dados da própria empresa, resultou em um aumento de 30 a 70% na velocidade sem sacrificar a precisão. Tem aplicações potenciais em vários setores que enfrentam problemas complexos de alocação de recursos.
Uma nova abordagem baseada em dados poderia levar a melhores soluções para problemas complicados de otimização, como roteamento global de pacotes ou operação da rede elétrica.
Pesquisadores de COM e a ETH Zurich desenvolveram uma nova técnica de aprendizagem automática baseada em dados que pode ser aplicada a muitos desafios logísticos complexos, como encaminhamento de pacotes, distribuição de vacinas e gestão da rede elétrica.
Embora o Papai Noel possa ter um trenó mágico e nove renas corajosas para ajudá-lo a entregar presentes, para empresas como a FedEx, o problema de otimização do roteamento eficiente de pacotes de férias é tão complicado que muitas vezes empregam software especializado para encontrar uma solução.
Este software, chamado de solucionador de programação linear inteira mista (MILP), divide um enorme problema de otimização em partes menores e usa algoritmos genéricos para tentar encontrar a melhor solução. No entanto, o solucionador pode levar horas — ou até dias — para chegar a uma solução.
O processo é tão oneroso que muitas vezes uma empresa tem que interromper o software no meio, aceitando uma solução que não é a ideal, mas a melhor que poderia ser gerada em um determinado período de tempo.
Pesquisadores do MIT e ETH Zurich usaram aprendizado de máquina para acelerar as coisas.
Eles identificaram uma etapa intermediária importante nos solucionadores MILP que tem tantas soluções potenciais que leva muito tempo para ser desvendada, o que retarda todo o processo. Os pesquisadores empregaram uma técnica de filtragem para simplificar esta etapa e, em seguida, usaram o aprendizado de máquina para encontrar a solução ideal para um tipo específico de problema.
Sua abordagem baseada em dados permite que uma empresa use seus próprios dados para adaptar um solucionador MILP de uso geral ao problema em questão.
Esta nova técnica acelerou os solucionadores MILP entre 30 e 70 por cento, sem qualquer queda na precisão. Poderíamos usar este método para obter uma solução ótima mais rapidamente ou, para problemas especialmente complexos, uma solução melhor em um período de tempo tratável.
Esta abordagem poderia ser usada onde quer que sejam empregados solucionadores de MILP, como por serviços de carona, operadores de redes elétricas, distribuidores de vacinação ou qualquer entidade que enfrente um problema espinhoso de alocação de recursos.
“Às vezes, em um campo como a otimização, é muito comum que as pessoas pensem em soluções como puramente de aprendizado de máquina ou puramente clássicas. Acredito firmemente que queremos obter o melhor dos dois mundos, e esta é uma instanciação realmente forte dessa abordagem híbrida”, diz a autora sênior Cathy Wu, Professora Assistente de Desenvolvimento de Carreira Gilbert W. Winslow em Engenharia Civil e Ambiental ( CEE) e membro do Laboratório de Sistemas de Informação e Decisão (LIDS) e do Instituto de Dados, Sistemas e Sociedade (IDSS).
Wu escreveu o papel com os co-autores principais Sirui Li, estudante de pós-graduação do IDSS, e Wenbin Ouyang, estudante de pós-graduação da CEE; bem como Max Paulus, estudante de pós-graduação da ETH Zurique. A pesquisa será apresentada na Conferência sobre Sistemas de Processamento de Informação Neural.
Difícil de resolver
Os problemas MILP têm um número exponencial de soluções potenciais. Por exemplo, digamos que um caixeiro-viajante queira encontrar o caminho mais curto para visitar várias cidades e depois retornar à sua cidade de origem. Se houver muitas cidades que possam ser visitadas em qualquer ordem, o número de soluções potenciais poderá ser maior que o número de átomos no universo.
“Esses problemas são chamados de NP-difíceis, o que significa que é muito improvável que exista um algoritmo eficiente para resolvê-los. Quando o problema é grande o suficiente, só podemos esperar alcançar um desempenho abaixo do ideal”, explica Wu.
Um solucionador MILP emprega uma série de técnicas e truques práticos que podem alcançar soluções razoáveis em um período de tempo tratável.
Um solucionador típico usa uma abordagem de dividir e conquistar, primeiro dividindo o espaço de soluções potenciais em pedaços menores com uma técnica chamada ramificação. Em seguida, o solucionador emprega uma técnica chamada corte para apertar esses pedaços menores para que possam ser pesquisados mais rapidamente.
O Cutting usa um conjunto de regras que restringem o espaço de busca sem remover quaisquer soluções viáveis. Essas regras são geradas por algumas dezenas de algoritmos, conhecidos como separadores, que foram criados para diferentes tipos de problemas de MILP.
Wu e sua equipe descobriram que o processo de identificação da combinação ideal de algoritmos separadores a serem usados é, por si só, um problema com um número exponencial de soluções.
“O gerenciamento de separadores é uma parte essencial de todo solucionador, mas é um aspecto subestimado do espaço do problema. Uma das contribuições deste trabalho é identificar o problema do gerenciamento de separadores como uma tarefa de aprendizado de máquina”, diz ela.
Reduzindo o espaço da solução
Ela e seus colaboradores desenvolveram um mecanismo de filtragem que reduz esse espaço de busca separador de mais de 130.000 combinações potenciais para cerca de 20 opções. Este mecanismo de filtragem baseia-se no princípio dos retornos marginais decrescentes, que afirma que o maior benefício viria de um pequeno conjunto de algoritmos, e adicionar algoritmos adicionais não traria muitas melhorias extras.
Em seguida, eles usam um modelo de aprendizado de máquina para escolher a melhor combinação de algoritmos entre as 20 opções restantes.
Este modelo é treinado com um conjunto de dados específico para o problema de otimização do usuário, para que ele aprenda a escolher os algoritmos que melhor se adequam à tarefa específica do usuário. Como uma empresa como a FedEx já resolveu problemas de roteamento muitas vezes, usar dados reais coletados de experiências anteriores deve levar a soluções melhores do que começar do zero todas as vezes.
O processo de aprendizagem iterativa do modelo, conhecido como bandidos contextuais, uma forma de aprendizagem por reforço, envolve escolher uma solução potencial, obter feedback sobre quão boa ela era e, em seguida, tentar novamente encontrar uma solução melhor.
Essa abordagem baseada em dados acelerou os solucionadores MILP entre 30 e 70 por cento, sem qualquer queda na precisão. Além disso, a aceleração foi semelhante quando aplicada a um solucionador mais simples e de código aberto e a um solucionador comercial mais poderoso.
No futuro, Wu e seus colaboradores querem aplicar esta abordagem a problemas MILP ainda mais complexos, onde a coleta de dados rotulados para treinar o modelo pode ser especialmente desafiadora. Talvez eles possam treinar o modelo em um conjunto de dados menor e depois ajustá-lo para resolver um problema de otimização muito maior, diz ela. Os pesquisadores também estão interessados em interpretar o modelo aprendido para compreender melhor a eficácia dos diferentes algoritmos separadores.
Referência: “Aprendendo a configurar separadores em ramificação e corte” por Sirui Li, Wenbin Ouyang, Max B. Paulus e Cathy Wu, 8 de novembro de 2023, Matemática > Otimização e Controle.
arXiv:2311.05650
Esta pesquisa é apoiada, em parte, pela Mathworks, pela National Science Foundation (NSF), pelo MIT Amazon Science Hub e pelo Comitê de Apoio à Pesquisa do MIT.
