Programación lineal entera en los últimos 50 años: avances prácticos recientes — Se muestra una página de protección de Anubis

 (inria.hal.science)
1 puntos por GN⁺ 2025-06-16 | 1 comentarios | Compartir por WhatsApp
  • En lugar del cuerpo del artículo, se muestra una página de verificación de bots de Anubis, por lo que no es posible consultar directamente el contenido real del artículo en esa URL
  • La página de protección advierte que el web scraping agresivo de empresas de IA puede provocar caídas del servidor y bloquear el acceso a recursos
  • Anubis exige una prueba de trabajo similar a Hashcash, diseñada para que la carga sea pequeña para usuarios individuales, pero que el costo acumulado aumente en el scraping masivo
  • Este método es una solución temporal y, a largo plazo, el foco está en identificar navegadores headless mediante señales como el renderizado de fuentes
  • Como requiere funciones modernas de JavaScript, si están activados plugins como JShelter, hay que desactivarlos en ese dominio para poder acceder

Se muestra una página de protección de Anubis

  • El título de la página es “Making sure you're not a bot!” y en pantalla aparece el estado calculando
    • La dificultad es 4
    • La velocidad es 0kH/s
  • El administrador del servidor configuró Anubis para protegerlo del scraping agresivo de empresas de IA, y por eso se muestra esta página
  • El scraping masivo puede provocar caídas del sitio web y, como consecuencia, impedir que todos los usuarios accedan a los recursos

Método de prueba de trabajo y restricciones de acceso

  • Anubis usa un método de prueba de trabajo de la familia de Hashcash
    • La carga adicional para usuarios individuales es insignificante
    • Para los scrapers masivos, el costo acumulado crece y encarece el scraping
  • El método actual se parece más a una solución temporal
    • El objetivo es ganar tiempo para identificar navegadores headless mediante señales como la forma de renderizar fuentes
    • La intención es no mostrar la página de prueba de trabajo cuando sea probable que se trate de usuarios legítimos
  • Anubis requiere funciones modernas de JavaScript
    • Plugins como JShelter pueden desactivar funciones necesarias
    • En este dominio hay que desactivar JShelter o plugins similares

Lecturas relacionadas

1 comentarios

 
GN⁺ 2025-06-16
Opiniones en Hacker News

  • Me gustaría entender, a grandes rasgos, por qué los solvers comerciales de programación lineal entera (ILP) son mucho mejores que los gratuitos/open source, como Gurobi.
    Me pregunto si ILP es un problema intrínsecamente tan difícil que los mejores solvers son básicamente una gran colección de heurísticas para subproblemas específicos, y si en el dominio público todavía no existen buenas estrategias generales.

    • La razón principal es que han trabajado muy de cerca con clientes para implementar mejoras de velocidad específicas para cada problema. Y lo han hecho durante 10 a 20 años.
      En la programación lineal entera mixta (MILP), son importantes las heurísticas para encontrar buenos puntos de partida del método branch-and-bound y podar eficazmente el árbol, así como planos de corte personalizados que eliminan soluciones fraccionarias y mejoran el valor objetivo y la integralidad.
      Cuando investigadores de investigación de operaciones toman un problema específico, a veces pueden superar con bastante facilidad a un solver de propósito general como Gurobi escribiendo sus propios planos de corte y heurísticas. Las empresas de solvers contratan equipos de doctores e investigadores para hacer esto de forma continua, y monitorean mejoras y regresiones con conjuntos de problemas de clientes.
    • Los grandes solvers comerciales tienen los recursos y clientes colaboradores para dedicar mucho tiempo a ajustar todo el proceso de solución a problemas reales. Las heurísticas son parte de eso, y también incluye reconocer subproblemas más simples o aproximaciones y reincorporarlos al problema completo.
      Los solvers open source parecen verse frenados por una combinación de factores. La barrera de entrada para el desarrollo de optimización moderna es muy alta, así que para empezar hay pocos investigadores/desarrolladores que puedan contribuir de forma significativa tanto en matemáticas como en programación; si alguien tiene esas capacidades, las rutas que generan dinero tienden a alejarlo de contribuir a open source; y, por la naturaleza de los proyectos open source, es menos probable que los “clientes” devuelvan los ejemplos, datos de rendimiento y perfiles necesarios para mejorar el solver.
      Hay excepciones, pero estar fuera del desarrollo tradicional de solvers comerciales no implica que algo sea open source. Por ejemplo, SNOPT, desarrollado en Stanford, sigue teniendo licencia comercial. El trabajo académico en solvers a menudo se da en contextos de aplicación específicos, como Clarabel, por lo que el conjunto de problemas tiende a ser más estrecho.
      En otros campos, las grandes tecnológicas han superado cuellos de botella comprando proyectos comerciales existentes o financiando proyectos open source para contener a competidores. En solvers hay ejemplos más acotados como Ceres, pero probablemente se consideró que la inversión para desarrollar desde cero toda una pila de solvers de propósito general era demasiado grande.
    • Los solvers comerciales tienen una enorme colección de técnicas y buenos mecanismos de detección de patrones para identificar qué técnica puede ayudar con el problema actual.
      Si conoces la estructura del problema, puedes aprovecharla y hasta superar el rendimiento de un solver comercial. Pero si es un problema arbitrario, es muy poco probable.
    • Me parece casi evidente que la idea de que “un solver es un gran ensamble de heurísticas para subproblemas específicos” aplica a problemas NP-difíciles equivalentes a SAT, como ILP.
    • La clave es escala y velocidad. Por ejemplo, la mayoría de las firmas de trading cuantitativo ejecutan optimizaciones enormes con la mayor frecuencia posible. Los solvers open source a menudo ni siquiera pueden resolver esos problemas. Por ejemplo, terminan con excepciones por falta de memoria.

  • Recuerdo vagamente haber construido una herramienta de asignación de recursos con la biblioteca de programación lineal entera mixta “ILOG” de IBM. Me di cuenta de que, si el mismo problema que resolvíamos en 5 minutos se hubiera creado 20 años antes, todavía estaría ejecutándose.
    Recuerdo que la capacidad de cómputo bruta había aumentado unas 1000 veces, y los algoritmos habían mejorado en una magnitud similar, para una mejora total de alrededor de un millón de veces.
    Vale la pena tenerlo presente al hacer predicciones sobre el futuro. Por cierto, esos “recursos” eran diamantes.

  • Me da curiosidad cómo se usa esto en la práctica. Cuando implemento optimización numérica, me imagino que suele fallar por problemas comunes en enfoques basados en datos, como confianza y malos datos, y que al final alguien importante decide intuitivamente qué hacer.

    • En el trabajo usamos solvers en toda la pila. Hay un solver para programar de forma óptima baterías domésticas y autos eléctricos; un solver para programar de forma óptima un portafolio de cientos de miles de esas casas; y un solver para operar ese portafolio de forma óptima en el mercado.
      Los precios spot de electricidad en la UE se determinan cada día con una única ejecución gigantesca de un solver. Si buscas Euphemia, hay artículos sobre cómo funciona.
      La mayoría de los sectores con un objetivo claro que optimizar y dinero real en juego están llenos de solvers.
    • En empresas de FMCG, de hecho se usa para cosas así. Planificación de recorridos de vendedores y entregas, programación de recursos de maquinaria, personal y materiales para producción, y optimización de niveles de inventario en almacenes y centros de distribución.
      La parte de inventario no está totalmente automatizada porque la demanda es difícil de pronosticar.
    • Puedes leer casos de estudio.
      Casos de estudio de Gurobi: https://www.gurobi.com/case_studies/
      Algunos casos de estudio de CPLEX: https://www.ibm.com/products/ilog-cplex-optimization-studio/...
      Casos de estudio de Hexaly, antes LocalSolver: https://www.hexaly.com/customers

  • Escuché que Gurobi es bastante caro. Me pregunto si alguien puede compartir información de precios.

    • No puedo compartir información de precios porque es confidencial, pero si solo quieres jugar con MIP, no necesitas comprar uno de los tres solvers carísimos: XPRESS, Gurobi, CPLEX. Normalmente son gratuitos para estudiantes.
      Hay al menos dos buenos solvers MIP que son open source o gratuitos para uso no comercial.
      https://highs.dev/
      https://www.scipopt.org/
    • Según escuché, aunque por supuesto no puedo confirmarlo, básicamente tienen un solo nivel de precios: “contáctenos”; luego averiguan cuánto dinero estás ganando y te piden una parte.
    • No sé por qué creen que es un secreto tan profundamente oculto. Para una licencia con límite de núcleos, cuesta aproximadamente 10.000 dólares por asiento.
    • Es muchísimo más barato que tomar decisiones equivocadas lentamente. Solvers gratuitos como GLPK están bien para problemas pequeños, pero muchos problemas de negocio casi no pueden resolverse dentro del tiempo necesario si no pagas por un solver premium. Gurobi es el mejor de ellos.
    • La última vez que lo revisé, hace unos 10 años, una licencia completa para que varios usuarios la usaran en un servidor costaba alrededor de 100.000 dólares. No recuerdo el límite exacto de cantidad de asientos ni de servidores.
      Quisiera agregar que, para mucha gente de la industria, vale totalmente ese precio.

  • Recuerdo haber implementado alguna versión de los hiperplanos de corte de Gomory en Maple para aprender en los años 90. No era para uso real. Parece que el campo ha avanzado mucho.
    “Si a principios de los años 90 se necesitaban dos meses de tiempo de ejecución para resolver un LP, hoy no toma ni 1 segundo. Recientemente, Bixby comparó el rendimiento independiente de la máquina de dos solvers MILP, CPLEX y Gurobi, entre 1990 y 2020, y reportó una mejora de velocidad de casi 4×10^6 veces”.

  • Siento que faltan bastante enfoques basados en machine learning/inteligencia artificial para este tipo de problemas. He visto muchos papers de aprendizaje por refuerzo/redes neuronales de grafos que intentan resolver problemas pequeños, pero muchas veces parece que al final lo mejor es comprar una licencia de Gurobi y correrlo.
    Últimamente he trabajado en optimización de scheduling cercana al job shop scheduling, y aunque hay ejemplos que usan aprendizaje por refuerzo, no parecen suficientes. Para obtener soluciones razonables en problemas grandes terminé dependiendo de algoritmos evolutivos.
    No sé si, cuando se puede formular bien el problema, usar un enfoque de investigación de operaciones siempre resulta más eficiente.

    • Depende del problema. El problema de despacho de unidades con restricciones de seguridad consiste en decidir qué centrales eléctricas encender y cuándo; es increíblemente complejo, pero solvers MILP como Gurobi pueden encontrar rápidamente un óptimo global dentro del rango de brecha MIP.
      Se podría crear un algoritmo genético, pero no hay garantía de que dé una respuesta que no quede atrapada en mínimos locales. También habría que asumir que se puede hacer que se ejecute rápido. Una red neuronal también sería peor que el óptimo.
    • SAT es un problema estándar de inteligencia artificial simbólica (GOFAI) y, por supuesto, también se puede escribir un solver SAT en un lenguaje de programación del ecosistema de machine learning. En ese sentido, creo que los enfoques de machine learning/inteligencia artificial sí son bastante aplicables.

  • “De 1988 a 2004, el hardware se volvió 1600 veces más rápido y los solvers LP 3300 veces más rápidos, para un factor acumulado de mejora de velocidad de más de 5 × 10^6. ¡Y eso ya fue hace 20 años!”
    “Los autores observaron una mejora de velocidad de 1000 veces en solvers MILP comerciales entre 2001 y 2020. De eso, 50 veces se debió a algoritmos y 20 veces a computadoras más rápidas”.
    Me pregunto si sería posible recopilar estos factores de mejora de velocidad por subcampo de la computación y descomponerlos entre la contribución de las mejoras algorítmicas y la de computadoras más rápidas.
    En compiladores existe la “ley de Proebsting”: sostiene que los avances en compiladores duplican el rendimiento de cómputo cada 18 años.

  • Estaría bien agregar [pdf] [2024] al título.