Os últimos 50 anos da programação linear inteira: avanços práticos recentes — exibição da página de proteção do Anubis

 (inria.hal.science)
1 pontos por GN⁺ 2025-06-16 | 1 comentários | Compartilhar no WhatsApp
  • Em vez do texto do artigo, é exibida a página de verificação de bot do Anubis, então não é possível ver imediatamente o conteúdo real do artigo nesse URL
  • A página de proteção informa que o web scraping agressivo por empresas de IA pode levar a indisponibilidade do servidor e bloqueio de acesso a recursos
  • O Anubis exige uma prova de trabalho semelhante ao Hashcash, projetada para ter pouco custo para usuários individuais, mas um custo acumulado alto para scraping em massa
  • Essa abordagem é uma solução temporária e, no longo prazo, o foco é identificar navegadores headless por pistas como renderização de fontes
  • Como são necessários recursos modernos de JavaScript, se plugins como o JShelter estiverem ativados, será preciso desativá-los nesse domínio para conseguir acesso

A página de proteção do Anubis é exibida

  • O título da página é “Making sure you're not a bot!”, e a tela mostra o estado calculando
    • Dificuldade: 4
    • Velocidade: 0kH/s
  • O administrador do servidor configurou o Anubis para proteger o servidor contra scraping agressivo por empresas de IA, e por isso essa página é exibida
  • O scraping em massa pode causar indisponibilidade do site e, como resultado, todos os usuários podem ficar sem acesso aos recursos

Método de prova de trabalho e restrições de acesso

  • O Anubis usa um método de prova de trabalho da família do Hashcash
    • A carga adicional para usuários individuais é praticamente desprezível
    • Para scrapers em massa, o custo acumulado aumenta, elevando o custo do scraping
  • O método atual está mais próximo de uma solução temporária
    • O objetivo é ganhar tempo para identificar navegadores headless por pistas como a forma de renderização de fontes
    • A direção é deixar de exibir a página de prova de trabalho quando houver alta probabilidade de se tratar de um usuário legítimo
  • O Anubis exige recursos modernos de JavaScript
    • Plugins como o JShelter podem desativar os recursos necessários
    • Neste domínio, é preciso desativar o JShelter ou plugins semelhantes

Leituras relacionadas

1 comentários

 
GN⁺ 2025-06-16
Comentários do Hacker News

  • Gostaria de entender, em linhas gerais, por que solvers comerciais de programação linear inteira (ILP), como o Gurobi, são tão melhores que os gratuitos/open source
    Fico me perguntando se ILP é um problema intrinsecamente tão difícil que os melhores solvers são, na prática, grandes coleções de heurísticas para subproblemas específicos, e se ainda não há boas estratégias gerais no domínio público

    • O principal motivo é que eles vêm implementando melhorias de velocidade específicas por problema em colaboração muito próxima com os clientes. E fazem isso há 10 a 20 anos
      Em programação linear inteira mista (MILP), são importantes heurísticas para encontrar bons pontos de partida para branch-and-bound e podar a árvore de forma eficaz, além de planos de corte sob medida que eliminam soluções fracionárias e melhoram o valor da função objetivo e a integralidade
      Quando pesquisadores de pesquisa operacional pegam um problema específico, eles muitas vezes escrevem seus próprios planos de corte e heurísticas e conseguem superar com bastante facilidade um solver genérico como o Gurobi. As empresas de solvers contratam equipes de doutores e pesquisadores para fazer isso continuamente, e acompanham melhorias e regressões usando conjuntos de problemas de clientes
    • Grandes solvers comerciais têm recursos e clientes parceiros para investir muito tempo ajustando tudo no processo de solução a problemas reais. Heurísticas fazem parte disso, assim como reconhecer subproblemas mais simples ou aproximações e reincorporá-los ao problema completo
      Solvers open source parecem ser travados por uma combinação de fatores. A barreira de entrada para desenvolvimento moderno em otimização é muito alta, então há poucos pesquisadores/desenvolvedores capazes de contribuir de forma significativa tanto em matemática quanto em programação; quando alguém tem essa capacidade, os caminhos que dão dinheiro tendem a afastá-lo de contribuições open source; e, pela natureza de projetos open source, é menos provável que “clientes” devolvam exemplos, dados de desempenho e profiling necessários para melhorar o solver
      Há exceções, mas estar fora do desenvolvimento tradicional de solvers comerciais não significa necessariamente ser open source. Por exemplo, o SNOPT, desenvolvido em Stanford, ainda tem licença comercial. Trabalhos acadêmicos em solvers muitas vezes ocorrem em contextos de aplicação específicos, como o Clarabel, o que tende a restringir a família de problemas
      Em outras áreas, grandes empresas de tecnologia às vezes superaram gargalos comprando projetos comerciais existentes ou financiando projetos open source para conter concorrentes. Em solvers há exemplos mais estreitos, como o Ceres, mas é provável que o investimento para desenvolver do zero toda uma pilha de solvers de propósito geral tenha sido considerado grande demais
    • Solvers comerciais têm uma enorme coleção de técnicas e bons mecanismos de detecção de padrões para identificar quais técnicas podem ajudar no problema atual
      Se você conhece a estrutura do problema, também pode explorá-la para superar o desempenho de um solver comercial. Mas, para um problema arbitrário, isso é muito improvável
    • A afirmação de que “um solver é um grande ensemble de heurísticas para subproblemas específicos” parece se aplicar quase de forma óbvia a problemas NP-difíceis como ILP, equivalentes a SAT
    • O ponto central é escala e velocidade. Por exemplo, a maioria das empresas de trading quantitativo roda otimizações enormes com a maior frequência possível. Solvers open source muitas vezes nem conseguem resolver esses problemas. Algo como uma exceção por falta de memória

  • Tenho uma lembrança vaga de ter criado uma ferramenta de alocação de recursos usando a biblioteca programação linear inteira mista “ILOG”, da IBM. Percebemos que, se tivéssemos criado 20 anos antes o mesmo problema que resolvíamos em 5 minutos, ele ainda estaria rodando
    Lembro que o poder computacional bruto havia aumentado cerca de 1000 vezes, e os algoritmos tinham melhorado em grau parecido, resultando em uma melhora total de cerca de um milhão de vezes
    É algo a se considerar ao prever o futuro. A propósito, esses “recursos” eram diamantes

  • Fico curioso sobre como isso é usado na prática. Quando se implementa otimização numérica, imagino que ela falhe com frequência por problemas comuns em abordagens orientadas a dados, como confiança e dados ruins, e que, no fim, alguém importante decida no feeling o que fazer

    • No trabalho, usamos solvers em toda a stack. Temos um solver para agendar de forma ideal baterias domésticas e veículos elétricos, um solver para agendar de forma ideal centenas de milhares dessas casas como um portfólio, e um solver para negociar esse portfólio de forma ideal
      Os preços spot de eletricidade da UE são definidos diariamente por uma única execução gigantesca de solver. Procure por Euphemia; há textos sobre como ele funciona
      A maioria das áreas com um objetivo claro a otimizar e dinheiro real em jogo está cheia de solvers
    • Em empresas de FMCG, isso é realmente usado para esses fins. Há planejamento de deslocamentos de vendedores e entregas, escalonamento de recursos de máquinas, pessoal e materiais para produção, e otimização de níveis de estoque em centros logísticos de armazém
      A parte de estoque não é totalmente automatizada porque a previsão de demanda é difícil
    • Basta ler estudos de caso
      Estudos de caso da Gurobi: https://www.gurobi.com/case_studies/
      Alguns estudos de caso do CPLEX: https://www.ibm.com/products/ilog-cplex-optimization-studio/...
      Estudos de caso da Hexaly, antiga LocalSolver: https://www.hexaly.com/customers

  • Ouvi dizer que o Gurobi é bem caro. Gostaria de saber se alguém pode compartilhar informações de preço

    • As informações de preço são confidenciais, então não posso compartilhá-las, mas, se você só quer brincar com MIP, não precisa comprar os três solvers muito caros: XPRESS, Gurobi e CPLEX. Em geral, eles são gratuitos para estudantes
      Há pelo menos dois bons solvers MIP que são open source ou gratuitos para uso não comercial
      https://highs.dev/
      https://www.scipopt.org/
    • Pelo que ouvi, embora eu obviamente não possa confirmar, o nível de preço é basicamente apenas “entre em contato”, e então eles descobrem quanto dinheiro você ganha e pedem uma parte disso
    • Não entendo por que acham que isso é um segredo tão profundamente escondido. Para uma licença com limite de cores, é cerca de US$ 10 mil por assento
    • É muito mais barato do que tomar decisões erradas lentamente. Solvers gratuitos como o GLPK são bons para problemas pequenos, mas muitos problemas de negócios quase não conseguem ser resolvidos no tempo necessário se você não pagar por um solver premium. O Gurobi é o melhor deles
    • Da última vez que verifiquei, há cerca de 10 anos, uma licença completa para vários usuários em um servidor custava cerca de US$ 100 mil. Não me lembro dos limites exatos de número de assentos ou servidores
      Eu acrescentaria que, para muita gente no setor, ele vale bem esse preço

  • Lembro de ter implementado alguma versão do hiperplano de corte de Gomory no Maple nos anos 1990, para fins de aprendizado. Não era para uso real. Parece que a área avançou bastante
    “Se, no início dos anos 1990, resolver um LP exigia dois meses de tempo de execução, hoje não leva nem 1 segundo. Recentemente, Bixby comparou o desempenho independente de máquina de dois solvers MILP, CPLEX e Gurobi, de 1990 a 2020, e relatou uma aceleração de quase 4×10^6 vezes”

  • Tenho a impressão de que abordagens baseadas em aprendizado de máquina/inteligência artificial ainda são bem insuficientes para esse tipo de problema. Já vi muitos artigos com aprendizado por reforço/redes neurais de grafos tentando resolver problemas pequenos, mas muitas vezes parece que o melhor mesmo é comprar uma licença do Gurobi e rodar
    Tenho trabalhado recentemente com otimização de escalonamento próxima de job-shop scheduling; há exemplos usando aprendizado por reforço, mas eles não parecem suficientes. Acabei dependendo de algoritmos evolutivos para obter soluções plausíveis em problemas grandes
    Talvez, se for possível formular bem o problema, uma abordagem de pesquisa operacional seja sempre mais eficiente

    • Depende do problema. O problema de unit commitment com restrições de segurança decide quais usinas ligar e quando; é incrivelmente complexo, mas solvers MILP como o Gurobi conseguem encontrar rapidamente uma solução globalmente ótima dentro de uma faixa de gap MIP
      Você poderia criar um algoritmo genético, mas não há garantia de que ele dará uma resposta que não esteja presa em um mínimo local. Também é preciso assumir que será possível fazê-lo rodar rapidamente. Redes neurais também ficariam abaixo do ótimo
    • SAT é um problema padrão de inteligência artificial simbólica (GOFAI) e, naturalmente, também é possível escrever um solver SAT em uma linguagem de programação da família de aprendizado de máquina. Nesse sentido, acho que abordagens de aprendizado de máquina/inteligência artificial são bastante aplicáveis

  • “De 1988 a 2004, o hardware ficou 1600 vezes mais rápido, e os solvers LP ficaram 3300 vezes mais rápidos, resultando em um fator acumulado de aceleração superior a 5 × 10^6. E isso já foi há 20 anos!”
    “Os autores observaram uma aceleração de 1000 vezes em solvers MILP comerciais entre 2001 e 2020. Dessas, 50 vezes vieram de algoritmos, e 20 vezes de computadores mais rápidos”
    Fico curioso se seria possível reunir esses fatores de aceleração por subárea da computação e decompô-los nas contribuições de melhorias algorítmicas e de computadores mais rápidos
    Em compiladores existe a “Lei de Proebsting”: a evolução dos compiladores dobra o desempenho computacional a cada 18 anos

  • Seria bom acrescentar [pdf] [2024] ao título