Programmation linéaire en nombres entiers au cours des 50 dernières années : progrès pratiques récents — affichage de la page de protection Anubis

• Au lieu du texte de l’article, une page de vérification anti-bot Anubis s’affiche, ce qui empêche de consulter directement le contenu réel de l’article à cette URL
• La page de protection indique que le web scraping agressif pratiqué par des entreprises d’IA peut entraîner des indisponibilités du serveur et bloquer l’accès aux ressources
• Anubis impose une preuve de travail similaire à Hashcash, conçue pour rester légère pour un utilisateur individuel tout en faisant augmenter le coût cumulé du scraping à grande échelle
• Cette approche est une solution temporaire, avec à long terme un objectif centré sur l’identification des navigateurs headless à l’aide d’indices comme le rendu des polices
• Des fonctionnalités JavaScript récentes sont nécessaires ; si un plugin comme JShelter est activé, il faut le désactiver pour ce domaine afin d’y accéder

---

La page de protection Anubis s’affiche

• Le titre de la page est « Making sure you're not a bot! », et l’écran affiche l’état calcul en cours
  • La difficulté est de 4
  • La vitesse est de 0kH/s
• L’administrateur du serveur a configuré Anubis pour protéger le serveur contre le scraping agressif d’entreprises d’IA, d’où l’affichage de cette page
• Le scraping à grande échelle peut provoquer l’indisponibilité d’un site web, ce qui peut ensuite empêcher tous les utilisateurs d’accéder aux ressources

Preuve de travail et contraintes d’accès

• Anubis utilise une preuve de travail de type Hashcash
  • La charge supplémentaire pour un utilisateur individuel est négligeable
  • Pour les scrapers à grande échelle, le coût cumulé augmente, ce qui renchérit le scraping
• L’approche actuelle s’apparente à une solution temporaire
  • L’objectif est de gagner du temps pour identifier les navigateurs headless à l’aide d’indices comme la manière dont les polices sont rendues
  • L’idée est de ne pas afficher la page de preuve de travail lorsqu’il est probable qu’il s’agisse d’un utilisateur légitime
• Anubis requiert des fonctionnalités JavaScript récentes
  • Des plugins comme JShelter peuvent désactiver les fonctionnalités nécessaires
  • Il faut désactiver JShelter ou un plugin similaire sur ce domaine

[GN⁺]

Commentaires Hacker News

• J’aimerais comprendre, dans les grandes lignes, pourquoi les solveurs de programmation linéaire en nombres entiers (ILP) commerciaux sont bien meilleurs que les alternatives gratuites/open source comme Gurobi
  Je me demande si c’est parce que l’ILP est intrinsèquement un problème tellement difficile que les meilleurs solveurs sont en pratique de vastes ensembles d’heuristiques spécialisées pour certains sous-problèmes, et qu’il n’existe tout simplement pas encore de bonne stratégie générale dans le domaine public

  • La raison principale, c’est qu’ils ont travaillé en collaboration très étroite avec leurs clients pour mettre en place des améliorations de vitesse spécifiques aux problèmes. Et ils font ça depuis 10 à 20 ans
    En programmation linéaire mixte en nombres entiers (MILP), il est crucial d’avoir des heuristiques pour trouver de bons points de départ pour le branch-and-bound et élaguer efficacement l’arbre, ainsi que des plans de coupe sur mesure qui éliminent les solutions fractionnaires pour améliorer la valeur de l’objectif et l’intégralité
    Quand des chercheurs en recherche opérationnelle s’attaquent à un problème précis, ils peuvent souvent écrire eux-mêmes des plans de coupe et des heuristiques, et dépasser assez facilement un solveur générique comme Gurobi. Les entreprises de solveurs emploient des équipes de docteurs et de chercheurs pour faire ce travail en continu, et suivent les améliorations comme les régressions sur des ensembles de problèmes clients
  • Les grands solveurs commerciaux ont les ressources et les clients partenaires qui leur permettent de passer beaucoup de temps à ajuster chaque étape de la résolution à de vrais problèmes. Les heuristiques n’en sont qu’une partie ; cela inclut aussi la reconnaissance de sous-problèmes plus simples ou d’approximation, puis la réintégration de cette information dans le problème global
    Les solveurs open source semblent freinés par plusieurs facteurs qui se cumulent. La barrière à l’entrée pour les développements récents en optimisation est très élevée, donc il y a peu de chercheurs/développeurs capables de contribuer de manière significative à la fois côté maths et côté programmation, et quand on a ce profil, les parcours rémunérateurs éloignent généralement des contributions open source. De plus, par nature, les projets open source ont moins de chances d’avoir des « clients » qui renvoient des exemples, des données de performance et du profiling utiles pour améliorer le solveur
    Il existe des exceptions, mais être hors du développement commercial traditionnel ne veut pas automatiquement dire open source. Par exemple, SNOPT, développé à Stanford, reste sous licence commerciale. Le travail académique sur les solveurs se fait aussi souvent dans un contexte applicatif spécifique, comme Clarabel, ce qui tend à réduire la variété des familles de problèmes
    Dans d’autres domaines, de grandes entreprises tech ont pu dépasser ce goulot d’étranglement en rachetant des projets commerciaux existants ou en finançant des projets open source pour contrer un concurrent. Il existe des exemples plus ciblés côté solveurs, comme Ceres, mais il est probable que l’investissement nécessaire pour développer toute une pile de solveur générique from scratch ait été jugé trop important
  • Les solveurs commerciaux disposent d’un vaste ensemble de techniques, ainsi que de bons mécanismes de détection de motifs pour identifier celles qui aideront sur le problème courant
    Si l’on connaît la structure du problème, on peut parfois exploiter cela pour dépasser les performances d’un solveur commercial. Mais sur un problème arbitraire, c’est très peu probable
  • Dire qu’un « solveur est un grand ensemble d’heuristiques pour certains sous-problèmes » me semble quasiment aller de soi pour des problèmes NP-difficiles comme l’ILP, équivalents à SAT
  • Le point clé, c’est l’échelle et la vitesse. Par exemple, la plupart des sociétés de trading quantitatif exécutent d’énormes optimisations aussi souvent que possible. Les solveurs open source sont souvent incapables de résoudre ce type de problèmes. Typiquement, ils tombent sur une exception de mémoire insuffisante

• J’ai un vague souvenir d’avoir construit un outil d’allocation de ressources avec la bibliothèque ILOG de programmation linéaire mixte en nombres entiers d’IBM. Je me suis rendu compte que si nous avions créé exactement le même problème il y a 20 ans, il serait probablement encore en train de tourner aujourd’hui
  Si je me souviens bien, la puissance de calcul brute a augmenté d’environ 1000x, et les algorithmes se sont améliorés dans des proportions comparables, pour un gain total d’environ un facteur un million
  C’est une bonne chose à méditer quand on essaie de prévoir l’avenir. Au passage, cette « ressource », c’étaient des diamants

• Je me demande comment ce genre de chose est réellement utilisé. Quand on implémente de l’optimisation numérique, j’imagine que ça échoue souvent à cause de problèmes classiques des approches pilotées par les données, par exemple la confiance et les mauvaises données, et qu’au final quelqu’un d’important décide à l’instinct quoi faire

  • Au travail, on utilise des solveurs sur toute la stack. Il y a un solveur qui planifie de manière optimale les batteries domestiques et les véhicules électriques, un autre qui optimise la planification d’un portefeuille de centaines de milliers de maisons de ce type, et un autre encore qui négocie ce portefeuille de manière optimale
    Les prix spot de l’électricité dans l’UE sont déterminés chaque jour par une unique exécution d’un énorme solveur. Cherchez Euphemia, il existe des articles expliquant comment cela fonctionne
    Dans la plupart des domaines où il existe un objectif clair à optimiser et de l’argent réel en jeu, les solveurs sont partout
  • Dans les entreprises de FMCG, on l’utilise effectivement pour ce genre de choses. Par exemple, la planification des déplacements des commerciaux et des livraisons, l’ordonnancement des machines, des équipes et des matières premières pour la production, et l’optimisation des niveaux de stock dans les entrepôts et centres logistiques
    Sur la partie stock, ce n’est pas totalement automatisé, car la prévision de la demande reste difficile
  • Il suffit de lire des études de cas
    Études de cas Gurobi : https://www.gurobi.com/case_studies/
    Quelques études de cas CPLEX : https://www.ibm.com/products/ilog-cplex-optimization-studio/...
    Études de cas Hexaly, anciennement LocalSolver : https://www.hexaly.com/customers

• J’ai entendu dire que Gurobi était assez cher. Je me demande si quelqu’un peut partager des informations sur les prix

  • Les prix sont confidentiels, donc je ne peux rien partager, mais si c’est juste pour jouer avec du MIP, il n’est pas nécessaire d’acheter l’un des trois solveurs très chers que sont XPRESS, Gurobi et CPLEX. Ils sont généralement gratuits pour les étudiants
    Il existe au moins deux solveurs MIP corrects qui sont open source ou gratuits pour un usage non commercial
    https://highs.dev/
    https://www.scipopt.org/
  • D’après ce que j’ai entendu, sans pouvoir le confirmer, il n’existe en pratique qu’un seul niveau tarifaire : « contactez-nous », puis ils évaluent combien vous gagnez et en demandent une partie
  • Je ne sais pas pourquoi vous pensez que c’est un secret si bien gardé. Sur la base d’une licence limitée en nombre de cœurs, on est à environ 10 000 dollars par siège
  • C’est bien moins cher que de prendre de mauvaises décisions trop lentement. Les solveurs gratuits comme GLPK conviennent pour de petits problèmes, mais beaucoup de problèmes métiers ne peuvent pratiquement pas être résolus dans les délais nécessaires sans payer pour un solveur premium. Gurobi est le meilleur du lot
  • La dernière fois que j’ai vérifié, il y a environ 10 ans, une licence complète pour plusieurs utilisateurs sur serveur coûtait autour de 100 000 dollars. Je ne me souviens plus du nombre exact de sièges ni des limites sur le nombre de serveurs
    Je voudrais ajouter que, pour beaucoup de gens dans le secteur, cela vaut largement le prix demandé

• Je me souviens avoir implémenté dans Maple, dans les années 1990, une certaine version des hyperplans de coupe de Gomory à des fins d’apprentissage. Ce n’était pas destiné à un usage pratique. Le domaine semble avoir beaucoup progressé.
  « Au début des années 1990, résoudre un LP demandait deux mois de temps d’exécution ; aujourd’hui, cela prend moins d’une seconde. Récemment, Bixby a comparé les performances, indépendantes de la machine, de deux solveurs MILP, CPLEX et Gurobi, de 1990 à 2020, et a rapporté une amélioration de vitesse de près de 4×10^6 »

• J’ai l’impression qu’il manque encore pas mal d’approches fondées sur le machine learning / l’IA pour ce type de problèmes. J’ai vu beaucoup d’articles utilisant l’apprentissage par renforcement ou des réseaux de neurones sur graphes pour résoudre de petits problèmes, mais au final, il semble souvent que le mieux reste d’acheter une licence Gurobi et de le faire tourner.
  J’ai récemment travaillé sur une optimisation d’ordonnancement proche de l’ordonnancement d’atelier ; il existe bien des exemples utilisant l’apprentissage par renforcement, mais cela ne semble pas suffisant. J’ai fini par devoir m’appuyer sur des algorithmes évolutionnaires pour obtenir des solutions plausibles sur de grands problèmes.
  Si l’on peut bien formaliser le problème, il est peut-être tout simplement toujours plus efficace d’utiliser une approche de recherche opérationnelle.

  • Cela dépend du problème. Le security-constrained unit commitment consiste à décider quelles centrales allumer et à quel moment ; c’est incroyablement complexe, mais des solveurs MILP comme Gurobi peuvent trouver rapidement l’optimum global dans la plage de gap MIP.
    On pourrait construire un algorithme génétique, mais rien ne garantit qu’il fournisse une réponse qui ne soit pas bloquée dans un minimum local. Il faut aussi supposer qu’on puisse le faire tourner rapidement. Un réseau neuronal serait lui aussi inférieur à l’optimum.
  • SAT est un problème standard d’IA symbolique (GOFAI), et bien sûr on peut écrire un solveur SAT dans un langage de programmation orienté machine learning. En ce sens, je pense que les approches machine learning / IA sont tout à fait applicables.

• « De 1988 à 2004, le matériel est devenu 1 600 fois plus rapide, et les solveurs LP 3 300 fois plus rapides, pour un facteur cumulé d’accélération dépassant 5 × 10^6. Et c’était déjà il y a 20 ans ! »
  « Les auteurs ont observé une accélération d’un facteur 1 000 dans les solveurs MILP commerciaux entre 2001 et 2020. Parmi cela, un facteur 50 vient des algorithmes et un facteur 20 d’ordinateurs plus rapides »
  Je me demande s’il serait possible de rassembler ce type de facteurs d’accélération par sous-domaines de l’informatique, puis de les décomposer entre l’amélioration des algorithmes et celle du matériel.
  Il existe en compilation la « loi de Proebsting », selon laquelle les progrès des compilateurs doublent les performances informatiques tous les 18 ans.

• Il vaudrait mieux ajouter [pdf] [2024] dans le titre.

  • Il suffit de mettre directement le lien vers l’article : https://inria.hal.science/hal-04776866v1/document
  • Le lien pointe vers un résumé, pas vers le PDF