- Programação linear inteira mista (MILP) se consolidou como uma ferramenta central em diversos setores industriais
- Graças às melhorias na eficiência computacional dos solucionadores mais recentes, problemas que antes eram difíceis de resolver agora podem encontrar a solução ótima rapidamente
- Este artigo explica os avanços práticos recentes nos métodos de solução de MILP e foca nas melhorias de desempenho computacional
- As principais metodologias apresentadas são branch-and-cut, decomposição de Dantzig-Wolfe e decomposição de Benders
- Também resume os desafios contínuos da área de MILP e as oportunidades para pesquisas futuras
Introdução
- Programação linear inteira mista (MILP) é uma ferramenta essencial em pesquisa operacional, sendo usada com sucesso em diversas áreas da indústria
- Os solucionadores modernos de MILP agora conseguem buscar a solução ótima de problemas de grande escala em segundos, algo que antes era impossível
- Com isso, a aplicação de MILP se expandiu para áreas como transporte, cadeia de suprimentos, gestão de receita, finanças, telecomunicações e manufatura
- Ainda assim, permanecem problemas não resolvidos e novos desafios, por isso a pesquisa em MILP continua ativa e constante
Visão geral do conteúdo principal
- Este artigo analisa os avanços recentes nos métodos de solução de MILP e as melhorias práticas de desempenho, com foco em como cada técnica contribuiu de fato para ganhos de performance computacional
- Entre a vasta literatura, dá prioridade a estudos baseados em experimentos computacionais reais
- A discussão é organizada em torno de três áreas centrais dos métodos de solução de MILP
- Método branch-and-cut: forma representativa de resolver MILP que combina técnicas de divisão de nós e planos de corte
- Decomposição de Dantzig-Wolfe: abordagem de decomposição que divide problemas de grande escala em subproblemas menores para tratá-los com mais eficiência
- Decomposição de Benders: método que reduz o custo computacional em estruturas complexas ao separar variáveis e restrições e resolvê-las de forma iterativa
Encerramento: desafios e perspectivas futuras
- A parte final do artigo examina os desafios ainda presentes no MILP e as oportunidades de pesquisa futura
- Problemas industriais reais cada vez mais complexos, expansão dos dados e limites de desempenho dos solucionadores serão temas centrais das próximas pesquisas
- No futuro, a área de MILP deve continuar crescendo com o avanço dos algoritmos, do hardware e da expansão para novos domínios de aplicação
1 comentários
Comentários no Hacker News
Alguém expressa curiosidade se alguém poderia explicar por que solvers comerciais de ILP, como o Gurobi, são muito superiores aos solvers gratuitos/open source, perguntando se isso se deve à dificuldade intrínseca do ILP ou se o melhor solver é, na prática, um grande conjunto de heurísticas para subproblemas específicos, e portanto estratégias geralmente “boas” ainda não estão em domínio público
Solvers comerciais costumam trabalhar em estreita colaboração com clientes para implementar técnicas de aceleração específicas para cada problema, acumulando know-how ao longo de 10 a 20 anos; destaca-se o uso, em MILP, de boas heurísticas (escolha do ponto de partida para branch-and-bound, poda eficaz da árvore) e de cortes customizados (para excluir soluções parciais de forma eficiente); também é mencionado que pesquisadores de OR, ao escolherem diretamente os problemas e escreverem cortes e heurísticas sob medida, muitas vezes obtêm resultados ainda melhores que os de solvers comerciais, mas as empresas de solvers contratam equipes de pesquisa com doutorado para implementar isso de forma consistente e acompanhar melhorias com enormes volumes de dados reais de clientes
Solvers comerciais conseguem investir enormes quantidades de tempo e recursos no ajuste do desempenho porque clientes reais se importam e ajudam; além de heurísticas, isso inclui reconhecer subproblemas simples ou aproximados e realimentar essas soluções no problema completo; solvers open source têm limitações porque (1) a barreira de entrada para desenvolver otimizadores de ponta é muito alta (há pouca gente realmente boa tanto em matemática quanto em programação), (2) quem tem esse nível de habilidade normalmente vai para carreiras que pagam muito, e (3) pela própria estrutura do open source, quase não há clientes fornecendo casos, dados de desempenho e profiling para orientar melhorias Como exceção, há casos como o SNOPT, que é comercial mas com um desenvolvimento comercial não tradicional; solvers acadêmicos tendem a focar em domínios de aplicação específicos e têm menor generalidade; em outras áreas, grandes empresas como o Google às vezes compram ou apoiam projetos para ampliar o ecossistema, mas no caso dos solvers o custo de investimento para construir toda a stack desde o início é alto demais
Solvers comerciais conseguem descobrir, por meio de uma grande variedade de truques e mecanismos de detecção de padrões, quais truques funcionarão para cada problema; se você conhece bem a estrutura do problema, pode até criar algo mais rápido que um solver comercial, mas para um problema aleatório quase não há chance
Há a afirmação de que “solver = conjunto de várias heurísticas para subproblemas especializados”, com a observação de que, em problemas NP-hard, praticamente tudo tem essa estrutura; ILP é equivalente a SAT, então o mesmo vale aqui
Há também a questão de escala comercial e velocidade: a maioria das empresas de trading quantitativo roda problemas de otimização muito grandes o mais frequentemente possível, e solvers open source muitas vezes nem conseguem resolver o problema ou estouram memória; a diferença é desse tamanho
Alguém relembra a experiência de criar uma ferramenta de alocação de recursos com a biblioteca ILOG MILP da IBM; se tivesse resolvido um problema parecido 20 anos atrás, ainda estaria esperando uma solução para algo que hoje leva 5 minutos; o hardware ficou mil vezes melhor e os algoritmos também melhoraram mil vezes, totalizando uma melhora de um milhão de vezes; um bom ponto para refletir ao fazer previsões sobre o futuro; e, por sinal, o “recurso” nesse caso eram diamantes
Surge a dúvida de como isso é usado na prática, com a pergunta se otimização numérica não acaba esbarrando nos limites gerais de sistemas baseados em dados (confiança, qualidade dos dados etc.), fazendo com que no fim uma pessoa importante decida no “feeling”
Em uma empresa, solvers são usados em toda a stack: para otimizar o agendamento de baterias residenciais e EVs, para otimizar a programação de um portfólio com centenas de milhares de residências e até para negociar esse portfólio; os preços spot de eletricidade da UE também são determinados pela execução de um único solver gigantesco chamado Euphemia; em áreas com objetivos de otimização claros e diretamente ligados a dinheiro, solvers são amplamente usados
Exemplo prático em uma empresa de FMCG: (1) planejamento de rotas de vendedores e entregas, (2) agendamento de máquinas, equipe e materiais para produção, (3) definição de níveis adequados de estoque em centros de distribuição; por causa da dificuldade de prever demanda, isso não é totalmente automatizado
Compartilhados links de estudos de caso como referência: Estudos de caso do Gurobi, Estudos de caso do CPLEX, Estudos de caso da Hexaly (antiga LocalSolver)
Alguém comenta que ouviu dizer que o Gurobi é bem caro e pergunta se alguém pode compartilhar informações reais de preço
Os preços exatos não são públicos, mas, para fins de estudo de MIP, recomenda-se não comprar um solver comercial como XPRESS/Gurobi/CPLEX e usar em vez disso uma licença estudantil gratuita ou um solver MIP open source gratuito para uso não comercial, como HiGHS ou SCIP
Pelo que se ouve, a precificação é no estilo “ligue para negociar”, e o valor cobrado seria ajustado com base em quanto dinheiro o cliente de fato ganha
Ressalta-se que ainda sai muito mais barato do que decisões lentas e subótimas; para problemas pequenos, solvers gratuitos como GLPK bastam, mas em problemas grandes do mundo dos negócios, obter uma resposta a tempo muitas vezes é quase impossível; por isso, solvers premium valem o preço
Há a lembrança de que, cerca de 10 anos atrás, uma licença para vários servidores custava algo como 100 mil dólares, embora a pessoa não recorde exatamente os limites de usuários ou servidores; menciona-se também que o setor considera isso plenamente justificável
O Gurobi também oferece um serviço em nuvem com cobrança por hora, e licenças não acadêmicas são muito caras
Alguém comenta que implementou diretamente hyperplanes de corte de Gomory nos anos 1990 e se impressiona com o quanto a área evoluiu; antes, um problema de LP levava dois meses para ser resolvido, agora leva 1 segundo; um trabalho de Bixby relata que, entre 1990 e 2020, CPLEX e Gurobi ficaram quase 4 milhões de vezes mais rápidos independentemente do desempenho das máquinas
Entre 1988 e 2004, o hardware ficou 1600 vezes mais rápido e os solvers de LP, 3300 vezes; já naquela época, o ganho acumulado passava de 5 milhões de vezes; entre 2001 e 2020, solvers comerciais de MILP também ficaram mais de 1000 vezes mais rápidos (50x pelos algoritmos, 20x pelos computadores); surge a curiosidade de reunir dados de avanço de velocidade em várias áreas, separando a contribuição de algoritmos e de hardware; na área de compiladores, por exemplo, existe algo como a “lei de Proebsting”, segundo a qual, a cada 18 anos, os compiladores avançam o equivalente a dobrar o poder computacional
Há a impressão de que abordagens baseadas em ML/AI não parecem ser muito usadas nesse tipo de problema; existem artigos tentando usar RL/GNN em problemas pequenos, mas no fim parece que comprar uma licença do Gurobi é o melhor caminho; quem trabalhou recentemente com otimização de escalonamento também viu casos com RL, mas o desempenho real foi fraco; para problemas grandes, algoritmos evolutivos parecem melhores, mas no fim, se você consegue formular bem o problema, a abordagem baseada em OR parece a mais eficiente
Isso depende do tipo de problema; por exemplo, decidir quando ligar ou desligar usinas (unit commitment) é extremamente complexo, mas um solver MILP pode encontrar rapidamente a solução ótima global; algoritmos genéticos não garantem escapar de mínimos locais e também podem ser lentos, e redes neurais sempre produzem soluções subótimas
SAT é um problema clássico de GOFAI, e dá para escrever um solver SAT em praticamente qualquer linguagem da família de ML; ou seja, uma abordagem “ML/AI” pode perfeitamente ser aplicada
Um comentário sugere que seria bom acrescentar a indicação de pdf no título
É respondido que o link em questão não aponta para um pdf, mas para o resumo
Também é compartilhada uma referência direta para o pdf do artigo: https://inria.hal.science/hal-04776866v1/document
Alguém opina que integer linear programming não parece algo tão complexo
Explica-se que 3-coloração de vértices em grafos (G3C) está em NP e é NP-hard, portanto é NP-complete; há resultados mostrando que, se você resolve ILP geral, também resolve G3C; SAT também é NP-complete, e se você resolve SAT, resolve G3C, então se consegue resolver G3C, também consegue fatoração inteira (FAC); FAC não é NP-complete, mas é extremamente importante no cenário computacional atual; logo, pode-se inferir que resolver ILP arbitrário permitiria quebrar algoritmos criptográficos importantes, o que mostra como ILP é um problema muito difícil; um ponto que muita gente confunde é que, em problemas NP-complete, instâncias aleatórias costumam ser fáceis de resolver, e a proporção de instâncias difíceis tende até a diminuir conforme o tamanho do problema aumenta
O problema do caixeiro-viajante (Travelling Salesperson Problem, TSP) também pode ser codificado como ILP, o que já indica bastante dificuldade
Você precisa encontrar os inteiros que melhor satisfazem as restrições; parece semelhante a trabalhar com números reais, mas na prática é algo fundamentalmente diferente; não existe uma solução geral, apenas heurísticas (muito boas) para casos especiais
É um problema bem mais difícil do que programação linear
Ou, talvez, um problema muito do mundo real mesmo