Ganzzahlige lineare Programmierung der letzten 50 Jahre: jüngste praktische Fortschritte — Anubis-Schutzseite wird angezeigt

 (inria.hal.science)
1 Punkte von GN⁺ 2025-06-16 | 1 Kommentare | Auf WhatsApp teilen
  • Statt des eigentlichen Papers wird eine Anubis-Bot-Prüfseite angezeigt, sodass der tatsächliche Inhalt des Papers unter dieser URL nicht direkt eingesehen werden kann
  • Die Schutzseite weist darauf hin, dass aggressives Web-Scraping durch AI-Unternehmen zu Server-Ausfällen und blockiertem Ressourcenzugriff führen kann
  • Anubis verlangt einen Proof of Work ähnlich wie Hashcash; für einzelne Nutzer ist der Aufwand gering, bei groß angelegtem Scraping steigen die kumulierten Kosten jedoch deutlich
  • Dieser Ansatz ist eine Übergangslösung; langfristig liegt der Fokus darauf, Headless-Browser anhand von Hinweisen wie Font-Rendering zu erkennen
  • Da moderne JavaScript-Funktionen erforderlich sind, muss ein Plugin wie JShelter auf dieser Domain deaktiviert werden, falls es aktiviert ist

Anubis-Schutzseite wird angezeigt

  • Der Seitentitel lautet „Making sure you're not a bot!“, und auf dem Bildschirm wird der Status Calculating angezeigt
    • Schwierigkeit: 4
    • Geschwindigkeit: 0kH/s
  • Der Server-Administrator hat Anubis eingerichtet, um den Server vor aggressivem Scraping durch AI-Unternehmen zu schützen; deshalb wird diese Seite angezeigt
  • Groß angelegtes Scraping kann zu Website-Ausfällen führen, sodass infolgedessen alle Nutzer möglicherweise keinen Zugriff auf die Ressourcen haben

Proof-of-Work-Verfahren und Zugriffsbeschränkungen

  • Anubis verwendet ein Proof-of-Work-Verfahren aus der Hashcash-Familie
    • Die zusätzliche Belastung für einzelne Nutzer ist vernachlässigbar
    • Für groß angelegte Scraper steigen die kumulierten Kosten, wodurch Scraping teurer wird
  • Der aktuelle Ansatz ist eher eine Übergangslösung
    • Ziel ist es, Zeit zu gewinnen, um Headless-Browser anhand von Hinweisen wie der Art des Font-Renderings zu erkennen
    • Wenn Nutzer mit hoher Wahrscheinlichkeit legitim sind, soll die Proof-of-Work-Seite nicht angezeigt werden
  • Anubis erfordert moderne JavaScript-Funktionen
    • Plugins wie JShelter können benötigte Funktionen deaktivieren
    • Auf dieser Domain muss JShelter oder ein ähnliches Plugin deaktiviert werden

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-06-16
Hacker-News-Kommentare

  • Ich würde gern das große Bild verstehen, warum kommerzielle Integer-Linear-Programming(ILP)-Solver wie Gurobi so viel besser sind als kostenlose/Open-Source-Alternativen.
    Ich frage mich, ob ILP im Kern ein so schwieriges Problem ist, dass die besten Solver im Wesentlichen große Sammlungen von Heuristiken für bestimmte Teilprobleme sind und es im öffentlichen Bereich noch keine allgemein guten Strategien gibt.

    • Der Hauptgrund ist, dass sie sehr eng mit Kunden zusammenarbeiten und problemspezifische Geschwindigkeitsverbesserungen implementiert haben. Und das seit 10 bis 20 Jahren.
      Bei Mixed-Integer Linear Programming (MILP) sind Heuristiken wichtig, die gute Startpunkte für Branch-and-Bound finden und den Baum effektiv beschneiden, ebenso wie maßgeschneiderte Schnittebenen, die fraktionale Lösungen abschneiden und Zielfunktionswert sowie Ganzzahligkeit verbessern.
      Wenn Operations-Research-Forscher sich ein bestimmtes Problem vornehmen, schreiben sie oft eigene Schnittebenen und Heuristiken und schlagen damit recht leicht einen General-Purpose-Solver wie Gurobi. Solver-Firmen beschäftigen Teams aus Promovierten und Forschern, die diese Arbeit kontinuierlich machen und Verbesserungen sowie Regressionen anhand von Bündeln von Kundenproblemen verfolgen.
    • Große kommerzielle Solver haben die Ressourcen und kooperierende Kunden, um viel Zeit darauf zu verwenden, alles am Lösungsprozess auf reale Probleme abzustimmen. Heuristiken sind ein Teil davon; dazu gehört auch, einfachere Teilprobleme oder Approximationen zu erkennen und wieder in das Gesamtproblem einzubringen.
      Open-Source-Solver scheinen durch mehrere zusammenwirkende Faktoren ausgebremst zu werden. Die Einstiegshürde in moderne Optimierungsentwicklung ist sehr hoch, sodass es von vornherein nur wenige Forscher/Entwickler gibt, die sowohl mathematisch als auch programmiertechnisch sinnvoll beitragen können. Wer diese Fähigkeiten hat, findet lukrative Wege, die ihn eher von Open-Source-Beiträgen wegführen. Und wegen der Natur von Open-Source-Projekten ist es weniger wahrscheinlich, dass „Kunden“ die Beispiele, Performance-Daten und Profiling-Ergebnisse zurückliefern, die zur Verbesserung eines Solvers nötig sind.
      Es gibt Ausnahmen, aber außerhalb der traditionellen kommerziellen Solver-Entwicklung zu sein, heißt nicht automatisch Open Source zu sein. SNOPT etwa, in Stanford entwickelt, steht weiterhin unter kommerzieller Lizenz. Akademische Solver-Arbeit findet oft in einem bestimmten Anwendungskontext statt, wie bei Clarabel, wodurch die Problemfamilien tendenziell enger werden.
      In anderen Bereichen wurden Engpässe manchmal überwunden, indem große Tech-Unternehmen bestehende kommerzielle Projekte übernommen oder Open-Source-Projekte finanziert haben, um Wettbewerber in Schach zu halten. Bei Solvern gibt es engere Beispiele wie Ceres, aber die Investition, einen kompletten General-Purpose-Solver-Stack von Grund auf zu entwickeln, wurde wahrscheinlich als zu groß angesehen.
    • Kommerzielle Solver haben eine riesige Sammlung von Techniken und gute Mechanismen zur Mustererkennung, um zu erkennen, welche Technik dem aktuellen Problem helfen könnte.
      Wenn man die Problemstruktur kennt, kann man sie nutzen und die Leistung kommerzieller Solver übertreffen. Bei einem beliebigen Problem ist das aber sehr unwahrscheinlich.
    • Ich denke, die Aussage „ein Solver ist ein großes Ensemble von Heuristiken für bestimmte Teilprobleme“ gilt für NP-schwere Probleme wie ILP, die SAT äquivalent sind, fast offensichtlich.
    • Entscheidend sind Skalierung und Geschwindigkeit. Die meisten Quant-Trading-Firmen lassen zum Beispiel so oft wie möglich riesige Optimierungen laufen. Open-Source-Solver können solche Probleme oft gar nicht lösen, etwa wegen Out-of-Memory-Ausnahmen.

  • Ich erinnere mich vage daran, mit IBMs „ILOG“-Bibliothek für Mixed-Integer Linear Programming ein Tool zur Ressourcenallokation gebaut zu haben. Mir wurde klar, dass dasselbe Problem, das wir in fünf Minuten lösten, noch immer laufen würde, wenn man es 20 Jahre früher gebaut hätte.
    Soweit ich mich erinnere, war die reine Rechenleistung um etwa den Faktor 1000 gestiegen, und die Algorithmen hatten sich in ähnlichem Maß verbessert, insgesamt also um etwa den Faktor eine Million.
    Das sollte man im Hinterkopf behalten, wenn man die Zukunft vorhersagt. Übrigens waren diese „Ressourcen“ Diamanten.

  • Ich frage mich, wie so etwas in der Praxis verwendet wird. Wenn man numerische Optimierung implementiert, stelle ich mir vor, dass sie wegen Problemen, die bei datengetriebenen Ansätzen häufig sind, etwa Vertrauen und schlechte Daten, oft scheitert und am Ende irgendeine wichtige Person aus dem Bauch heraus entscheidet, was zu tun ist.

    • Bei der Arbeit verwenden wir Solver im gesamten Stack. Es gibt einen Solver, der Batterien in Haushalten und Elektroautos optimal einplant, einen Solver, der Hunderttausende solcher Häuser als Portfolio optimal einplant, und einen Solver, der dieses Portfolio optimal handelt.
      Die EU-Strom-Spotpreise werden täglich durch einen einzigen riesigen Solver-Lauf bestimmt. Wenn man nach Euphemia sucht, findet man Artikel darüber, wie das funktioniert.
      Die meisten Bereiche, in denen es ein klares Optimierungsziel gibt und echtes Geld auf dem Spiel steht, sind voller Solver.
    • In FMCG-Unternehmen wird das tatsächlich für solche Zwecke genutzt: Planung von Vertriebs- und Lieferfahrten, Scheduling von Maschinen-, Personal- und Materialressourcen für die Produktion sowie Optimierung von Lagerbeständen in Warehouse- und Logistikzentren.
      Der Lagerbestandsteil ist wegen schwieriger Nachfrageprognosen nicht vollständig automatisiert.
    • Man kann Fallstudien lesen.
      Gurobi-Fallstudien: https://www.gurobi.com/case_studies/
      Einige CPLEX-Fallstudien: https://www.ibm.com/products/ilog-cplex-optimization-studio/...
      Hexaly, früher LocalSolver, Fallstudien: https://www.hexaly.com/customers

  • Ich habe gehört, dass Gurobi ziemlich teuer ist. Ich frage mich, ob jemand Preisinformationen teilen kann.

    • Preisinformationen sind vertraulich, daher kann ich sie nicht teilen. Aber wenn man nur mit MIP herumspielen will, muss man keinen der drei sehr teuren Solver XPRESS, Gurobi und CPLEX kaufen. Für Studierende sind sie normalerweise kostenlos.
      Es gibt mindestens zwei ordentliche MIP-Solver, die Open Source oder für nichtkommerzielle Nutzung kostenlos sind:
      https://highs.dev/
      https://www.scipopt.org/
    • Nach allem, was ich gehört habe – was ich natürlich nicht überprüfen kann –, gibt es faktisch nur eine Preisstufe: „Kontaktieren Sie uns“. Dann finden sie heraus, wie viel Geld man damit verdient, und verlangen einen Teil davon.
    • Ich weiß nicht, warum man denkt, das sei ein so tief gehütetes Geheimnis. Bei einer Lizenz mit Core-Beschränkung sind es ungefähr 10.000 Dollar pro Seat.
    • Das ist viel billiger, als langsam falsche Entscheidungen zu treffen. Kostenlose Solver wie GLPK sind für kleine Probleme okay, aber viele Geschäftsprobleme lassen sich in der benötigten Zeit praktisch nicht lösen, wenn man nicht für einen Premium-Solver zahlt. Gurobi ist der beste davon.
    • Als ich zuletzt vor etwa 10 Jahren nachgesehen habe, kostete eine Volllizenz für mehrere Benutzer auf einem Server etwa 100.000 Dollar. Ich erinnere mich nicht an die genaue Anzahl der Seats oder Serverlimits.
      Ich möchte hinzufügen, dass das für viele Leute in der Branche seinen Preis absolut wert ist.

  • Ich erinnere mich, dass ich in den 1990ern zu Lernzwecken eine Version der Gomory-Schnittebenen in Maple implementiert habe. Nicht für den praktischen Einsatz. Das Feld scheint sich stark weiterentwickelt zu haben.
    „Wenn man Anfang der 1990er Jahre zwei Monate Laufzeit brauchte, um ein LP zu lösen, dauert es heute nicht einmal eine Sekunde. Kürzlich verglich Bixby die maschinenunabhängige Performance zweier MILP-Solver, CPLEX und Gurobi, von 1990 bis 2020 und berichtete von einer Beschleunigung um fast 4×10^6“

  • Ich habe das Gefühl, dass es für solche Probleme ziemlich wenig Ansätze auf Basis von Machine Learning/künstlicher Intelligenz gibt. Ich habe viele Paper gesehen, in denen Reinforcement Learning/Graph Neural Networks kleine Probleme lösen sollen, aber am Ende wirkt es oft so, als sei es am besten, einfach eine Gurobi-Lizenz zu kaufen und laufen zu lassen.
    Ich habe zuletzt an einer Scheduling-Optimierung gearbeitet, die nah an Job-Shop-Scheduling liegt; es gibt zwar Beispiele mit Reinforcement Learning, aber sie wirken nicht ausreichend. Um bei großen Problemen plausible Lösungen zu erhalten, musste ich auf evolutionäre Algorithmen zurückgreifen.
    Vielleicht ist ein Operations-Research-Ansatz immer effizienter, wenn man das Problem gut formalisieren kann.

    • Das hängt vom Problem ab. Beim Security-Constrained Unit Commitment geht es darum zu entscheiden, welche Kraftwerke wann eingeschaltet werden; das ist unglaublich komplex, aber MILP-Solver wie Gurobi können innerhalb der MIP-Gap-Grenzen schnell ein globales Optimum finden.
      Man könnte auch einen genetischen Algorithmus bauen, aber es gibt keine Garantie, dass er eine Antwort liefert, die nicht in einem lokalen Minimum feststeckt. Außerdem müsste man annehmen, dass man ihn schnell genug zum Laufen bekommt. Auch ein neuronales Netz wäre wohl schlechter als das Optimum.
    • SAT ist ein klassisches Problem der symbolischen KI (GOFAI), und natürlich kann man auch in einer Programmiersprache aus dem Machine-Learning-Umfeld einen SAT-Solver schreiben. In diesem Sinne halte ich Machine-Learning/KI-Ansätze durchaus für anwendbar.

  • „Von 1988 bis 2004 wurde die Hardware um den Faktor 1600 schneller, und LP-Solver wurden um den Faktor 3300 schneller, was zusammen einen Beschleunigungsfaktor von über 5 × 10^6 ergab. Und das war schon vor 20 Jahren!“
    „Die Autoren beobachteten zwischen 2001 und 2020 bei kommerziellen MILP-Solvern eine Beschleunigung um den Faktor 1000. Davon entfielen 50× auf Algorithmen und 20× auf schnellere Computer.“
    Ich frage mich, ob man solche Beschleunigungsfaktoren für verschiedene Teilgebiete der Informatik sammeln und in Beiträge durch Algorithmusverbesserungen und schnellere Computer zerlegen könnte.
    Für Compiler gibt es „Proebstings Gesetz“: Danach verdoppeln Fortschritte bei Compilern alle 18 Jahre die Rechenleistung.

  • Es wäre gut, [pdf] [2024] an den Titel anzuhängen.