पिछले 50 वर्षों का Integer Linear Programming: हालिया व्यावहारिक प्रगति — Anubis सुरक्षा पेज प्रदर्शित

 (inria.hal.science)
1 पॉइंट द्वारा GN⁺ 2025-06-16 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • पेपर के मूल पाठ की जगह Anubis bot verification page दिखाई देता है, इसलिए उस URL पर वास्तविक पेपर सामग्री सीधे नहीं देखी जा सकती
  • सुरक्षा पेज बताता है कि AI कंपनियों की आक्रामक web scraping सर्वर downtime और resource access रुकने का कारण बन सकती है
  • Anubis, Hashcash जैसी proof of work मांगता है, ताकि सामान्य उपयोगकर्ताओं पर बोझ कम रहे लेकिन बड़े पैमाने की scraping पर कुल लागत बढ़े
  • यह तरीका एक अस्थायी समाधान है, और लंबे समय में फोकस font rendering जैसे संकेतों से headless browser की पहचान करने पर है
  • क्योंकि इसके लिए आधुनिक JavaScript फीचर्स चाहिए, अगर JShelter जैसे plugin चालू हों तो इस डोमेन पर पहुंच के लिए उन्हें बंद करना होगा

Anubis सुरक्षा पेज दिखाई दे रहा है

  • पेज का शीर्षक “Making sure you're not a bot!” है, और स्क्रीन पर calculating स्थिति दिखाई देती है
    • कठिनाई 4
    • गति 0kH/s
  • सर्वर व्यवस्थापक ने AI कंपनियों की आक्रामक scraping से सर्वर की सुरक्षा के लिए Anubis सेट किया है, इसलिए यह पेज दिखता है
  • बड़े पैमाने की scraping वेबसाइट downtime का कारण बन सकती है, और उसके परिणामस्वरूप सभी उपयोगकर्ता resources तक पहुंच खो सकते हैं

Proof of work तरीका और access सीमाएँ

  • Anubis, Hashcash परिवार की proof of work पद्धति का उपयोग करता है
    • व्यक्तिगत उपयोगकर्ताओं पर पड़ने वाला अतिरिक्त बोझ नगण्य है
    • बड़े पैमाने के scrapers के लिए कुल लागत बढ़ती है, जिससे scraping महंगी हो जाती है
  • मौजूदा तरीका फिलहाल अस्थायी समाधान के करीब है
    • लक्ष्य यह है कि font rendering जैसे संकेतों से headless browser की पहचान करने के लिए समय मिल सके
    • जिन उपयोगकर्ताओं के वैध होने की संभावना अधिक है, उन्हें proof of work पेज न दिखाने की दिशा में काम है
  • Anubis को आधुनिक JavaScript फीचर्स चाहिए
    • JShelter जैसे plugin जरूरी फीचर्स को अक्षम कर सकते हैं
    • इस डोमेन पर JShelter या इसी तरह के plugin बंद करने होंगे

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-06-16
Hacker News टिप्पणियां

  • मैं बड़े स्तर पर समझना चाहता हूं कि commercial Integer Linear Programming (ILP) solvers जैसे Gurobi, free/open source solvers से इतने बेहतर क्यों हैं
    क्या ILP स्वभाव से ही इतना कठिन problem है कि best solvers दरअसल specific subproblems के लिए heuristics का एक बड़ा संग्रह हैं, और public domain में अभी तक आम तौर पर अच्छी strategies नहीं हैं?

    • मुख्य वजह यह है कि वे customers के साथ बहुत करीब से काम करते हुए problem-specific speed improvements implement करते आए हैं। और यह वे 10–20 साल से कर रहे हैं
      Mixed-Integer Linear Programming (MILP) में branch-and-bound के लिए अच्छा starting point ढूंढने और tree को प्रभावी ढंग से prune करने वाली heuristics, और fractional solutions को काटकर objective value व integrality सुधारने वाले custom cutting planes महत्वपूर्ण होते हैं
      Operations research researchers जब कोई specific problem पकड़ते हैं, तो वे खुद cutting planes और heuristics लिखकर Gurobi जैसे general-purpose solver को काफी आसानी से हरा भी देते हैं। Solver companies PhD और researchers की teams hire करके यह काम लगातार करती हैं, और customer problem sets पर improvements और regressions track करती हैं
    • बड़े commercial solvers के पास real-world problems के हिसाब से solving process की हर चीज़ tune करने में बहुत समय लगाने के लिए resources और collaborating customers होते हैं। Heuristics इसका एक हिस्सा हैं, और इसमें सरल subproblems या approximations को पहचानकर उन्हें पूरी problem में वापस reflect करना भी शामिल है
      Open source solvers कुछ चीज़ों के overlap से अटकते दिखते हैं। Modern optimization development में entry barrier बहुत ऊंचा है, इसलिए math और programming दोनों में meaningful contribution कर सकने वाले researchers/developers शुरू से ही कम हैं; और जिनके पास वह क्षमता है, उनके लिए पैसे कमाने वाले रास्ते open source contribution से दूर ले जाते हैं। साथ ही open source projects की प्रकृति के कारण “customers” द्वारा solver improvement के लिए जरूरी examples, performance data और profiling वापस देने की संभावना कम होती है
      exceptions भी हैं, लेकिन traditional commercial solver development के बाहर होना तुरंत open source होना नहीं है। उदाहरण के लिए Stanford में विकसित SNOPT अब भी commercial license पर है। Academic solver work अक्सर Clarabel जैसे specific application context में होता है, इसलिए problem families संकरी हो जाती हैं
      दूसरे क्षेत्रों में बड़ी tech companies ने existing commercial projects acquire किए, या competitors को रोकने के लिए open source projects को fund किया, और इस तरह bottleneck पार किया। Solvers में Ceres जैसे narrow examples हैं, लेकिन general-purpose solver stack को शुरू से develop करने का investment शायद बहुत बड़ा माना गया होगा
    • Commercial solvers के पास techniques का विशाल संग्रह और यह detect करने के लिए अच्छे pattern-detection mechanisms होते हैं कि current problem में कौन-सी technique मदद करेगी
      अगर आपको problem structure पता है, तो उसका उपयोग करके commercial solver performance से आगे भी जा सकते हैं। लेकिन arbitrary problem हो तो संभावना लगभग नहीं के बराबर है
    • मुझे लगता है कि “solver specific subproblem heuristics का बड़ा ensemble है” वाली बात ILP जैसे SAT के बराबर NP-hard problems पर तो लगभग स्पष्ट रूप से लागू होती है
    • असली बात scale और speed है। उदाहरण के लिए ज्यादातर quant trading firms जितनी बार संभव हो, विशाल optimizations चलाती हैं। Open source solvers कई बार ऐसी problems को हल ही नहीं कर पाते। जैसे out-of-memory exception वगैरह

  • मुझे धुंधली-सी याद है कि IBM की “ILOG” Mixed-Integer Linear Programming library से resource allocation tool बनाया था। हमें यह एहसास हुआ कि वही problem जिसे हम 5 मिनट में solve कर रहे थे, अगर 20 साल पहले बनाई होती तो वह अब भी चल रही होती
    मुझे याद है कि pure computing power करीब 1000 गुना बढ़ी, और algorithms भी लगभग उतने ही सुधरे, यानी कुल मिलाकर करीब दस लाख गुना improvement हुआ
    भविष्य का अनुमान लगाते समय इस पर सोचने लायक है। वैसे वे “resources” diamonds थे

  • मुझे जिज्ञासा है कि असल में ऐसी चीज़ें कैसे इस्तेमाल होती हैं। जब numerical optimization implement करते हैं, तो data-driven approaches में common issues, जैसे trust और bad data, के कारण वे अक्सर fail होती हैं, और आखिर में कोई important व्यक्ति gut feel से तय करता है कि क्या करना है—ऐसी तस्वीर दिमाग में आती है

    • काम पर हम पूरे stack में solvers इस्तेमाल करते हैं। घरों की batteries और EVs को optimally schedule करने वाला solver, ऐसे लाखों घरों को portfolio के रूप में optimally schedule करने वाला solver, और उस portfolio को optimally trade करने वाला solver है
      EU electricity spot prices रोज़ एक विशाल solver run से तय होते हैं। Euphemia खोजें तो उसके काम करने के तरीके पर लेख मिलेंगे
      जिन क्षेत्रों में optimize करने के लिए clear objective है और real money दांव पर है, उनमें से ज्यादातर solvers से भरे हुए हैं
    • FMCG company में इन्हें सचमुच ऐसे ही इस्तेमाल किया जाता है। Salespersons और delivery movement planning, production के लिए machines, labor और material resources की scheduling, और warehouse distribution centers में inventory levels का optimization शामिल है
      Inventory वाला हिस्सा demand forecasting की कठिनाई के कारण पूरी तरह automated नहीं हुआ है
    • Case studies पढ़ लें
      Gurobi case studies: https://www.gurobi.com/case_studies/
      CPLEX की कुछ case studies: https://www.ibm.com/products/ilog-cplex-optimization-studio/...
      Hexaly, पहले LocalSolver, case studies: https://www.hexaly.com/customers

  • मैंने सुना है कि Gurobi काफी महंगा है। क्या कोई pricing information share कर सकता है?

    • Pricing information confidential है, इसलिए share नहीं कर सकता, लेकिन अगर आप सिर्फ MIP से खेलना चाहते हैं तो बहुत महंगे top 3 solvers XPRESS, Gurobi, CPLEX खरीदने की जरूरत नहीं है। आम तौर पर students को ये free मिलते हैं
      कम से कम दो decent MIP solvers हैं जो open source हैं या non-commercial use के लिए free हैं
      https://highs.dev/
      https://www.scipopt.org/
    • जो मैंने सुना है—हालांकि confirm नहीं कर सकता—price tier असल में केवल “हमसे संपर्क करें” है, और फिर वे समझते हैं कि आप कितना पैसा कमा रहे हैं और उसका एक हिस्सा मांगते हैं
    • समझ नहीं आता कि लोग इसे इतना गहरा छिपा हुआ secret क्यों समझते हैं। Core-limited license के लिए यह प्रति seat लगभग 10,000 डॉलर है
    • धीमे तरीके से गलत decisions लेने की तुलना में यह बहुत सस्ता है। GLPK जैसे free solvers छोटी problems के लिए ठीक हैं, लेकिन बहुत-सी business problems premium solver के लिए पैसे दिए बिना required time में शायद ही solve हो पाती हैं। Gurobi उनमें सबसे अच्छा है
    • करीब 10 साल पहले जब आखिरी बार check किया था, server पर multiple users के लिए full license लगभग 100,000 डॉलर था। ठीक-ठीक seat count या server count limits याद नहीं हैं
      मैं यह भी जोड़ना चाहूंगा कि industry में बहुत लोगों के लिए यह कीमत पूरी तरह वसूल है

  • याद है कि 1990 के दशक में सीखने के लिए Maple में Gomory cutting hyperplane का कोई version implement किया था। वास्तविक उपयोग के लिए नहीं था। लगता है यह क्षेत्र काफी आगे बढ़ गया है
    “अगर 1990 के शुरुआती वर्षों में LP हल करने में दो महीने का runtime चाहिए होता, तो आज इसमें 1 सेकंड भी नहीं लगता। हाल ही में Bixby ने 1990 से 2020 तक CPLEX और Gurobi नाम के दो MILP solvers के machine-independent performance की तुलना की और लगभग 4×10^6 गुना speedup रिपोर्ट किया”

  • ऐसे problems के लिए machine learning/artificial intelligence आधारित approaches काफी कम लगती हैं। छोटे problems हल करने की कोशिश करने वाले reinforcement learning/graph neural network papers के कई उदाहरण देखे हैं, लेकिन अक्सर अंत में Gurobi license खरीदकर चलाना ही सबसे अच्छा लगता है
    हाल में मैं job-shop scheduling के करीब की scheduling optimization कर रहा था; reinforcement learning इस्तेमाल करने के उदाहरण तो हैं, लेकिन वे पर्याप्त नहीं लगते। बड़े problems में ठीक-ठाक समाधान पाने के लिए evolutionary algorithms पर निर्भर होना पड़ा
    अगर problem को अच्छी तरह formulate किया जा सके, तो शायद operations research वाला approach इस्तेमाल करना हमेशा ज्यादा efficient होता है

    • problem पर निर्भर करता है। Security-constrained unit commitment problem यह तय करने की समस्या है कि कौन-सा power plant कब चालू करना है; यह अविश्वसनीय रूप से complex है, लेकिन Gurobi जैसे MILP solvers MIP gap के दायरे में global optimum जल्दी खोज सकते हैं
      आप genetic algorithm बना सकते हैं, लेकिन यह guarantee नहीं होती कि वह local minimum में फंसे बिना जवाब देगा। यह assumption भी चाहिए कि उसे तेज चलने लायक बनाया जा सकता है। neural network भी शायद optimum से कमतर ही होगा
    • SAT एक standard symbolic artificial intelligence (GOFAI) problem है, और जाहिर है कि machine learning family की programming language में SAT solver भी लिखा जा सकता है। इस अर्थ में machine learning/artificial intelligence approach काफी लागू हो सकता है, ऐसा मुझे लगता है

  • “1988 से 2004 तक hardware 1600 गुना तेज हुआ, और LP solvers 3300 गुना तेज हुए, जिससे cumulative speedup factor 5 × 10^6 से ऊपर चला गया। और वह भी 20 साल पहले की बात है!”
    “लेखकों ने 2001 से 2020 के बीच commercial MILP solvers में 1000 गुना speedup देखा। इसमें से 50 गुना algorithms से और 20 गुना तेज computers से आया”
    सोचता हूं कि computing के subfields के हिसाब से ऐसे speedup factors इकट्ठे किए जा सकते हैं या नहीं, और उन्हें algorithmic improvements तथा faster computers के योगदान में तोड़कर देखा जा सकता है या नहीं
    compilers में “Proebsting's Law” है। यह नियम कहता है कि compiler progress हर 18 साल में computing performance को दोगुना कर देती है

  • title में [pdf] [2024] जोड़ना अच्छा रहेगा