पिछले 50 वर्षों का Integer Linear Programming: हालिया व्यावहारिक प्रगति

 (inria.hal.science)
1 पॉइंट द्वारा GN⁺ 2025-06-16 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Integer Linear Programming (MILP) कई उद्योग क्षेत्रों में एक प्रमुख टूल के रूप में स्थापित हो चुका है
  • नवीनतम solvers की computational efficiency में सुधार की वजह से अब वे समस्याएँ भी तेज़ी से optimal solution तक पहुँच सकती हैं जिन्हें पहले हल करना कठिन था
  • यह लेख MILP समाधान विधियों में हालिया व्यावहारिक प्रगति और computing performance में सुधार पर केंद्रित होकर समझाता है
  • प्रमुख methodologies के रूप में branch-and-cut, Dantzig-Wolfe decomposition, Benders decomposition का परिचय दिया गया है
  • MILP क्षेत्र की निरंतर चुनौतियों और भविष्य के research opportunities का सार प्रस्तुत किया गया है

परिचय

  • Mixed Integer Linear Programming (MILP) operations research में एक अनिवार्य टूल है, और इसका विभिन्न उद्योग क्षेत्रों में सफलतापूर्वक उपयोग हो रहा है
  • आधुनिक MILP solvers अब उन बड़े पैमाने की समस्याओं के लिए भी कुछ ही सेकंड में optimal solution खोज सकते हैं जिन्हें पहले असंभव माना जाता था
  • इसके कारण transport, supply chain, revenue management, finance, telecommunications, manufacturing जैसे कई क्षेत्रों में MILP का उपयोग बढ़ा है
  • लेकिन अब भी अनसुलझी समस्याएँ और नई चुनौतियाँ मौजूद हैं, इसलिए MILP पर शोध लगातार सक्रिय बना हुआ है

मुख्य सामग्री का अवलोकन

  • यह शोधपत्र MILP समाधान विधियों के हालिया विकास और व्यावहारिक performance improvements पर केंद्रित है, और विश्लेषण करता है कि प्रत्येक तकनीक ने वास्तविक computing performance में किस तरह योगदान दिया है
  • विशाल साहित्य में से विशेष रूप से उन अध्ययनों को प्राथमिकता दी गई है जो वास्तविक computational experiments पर आधारित हैं
  • चर्चा को MILP समाधान की तीन मुख्य दिशाओं में व्यवस्थित किया गया है
    • Branch-and-Cut method: node branching techniques और cutting plane techniques को जोड़ने वाली एक प्रमुख MILP समाधान पद्धति
    • Dantzig-Wolfe decomposition: बड़े पैमाने की समस्याओं को छोटे subproblems में बाँटकर कुशलतापूर्वक हल करने का decomposition approach
    • Benders decomposition: variables और constraints को अलग करके उन्हें दोहरावदार तरीके से हल करने वाली विधि, जिससे जटिल संरचनाओं में computational burden कम होता है

समापन: चुनौतियाँ और भविष्य की दिशा

  • शोधपत्र के अंतिम भाग में अब भी मौजूद MILP की चुनौतियों और भविष्य के research opportunities पर दृष्टि डाली गई है
  • वास्तविक उद्योग समस्याओं की बढ़ती जटिलता, डेटा का विस्तार, और solver performance की सीमाएँ आगे के प्रमुख शोध विषय हैं
  • आगे चलकर MILP क्षेत्र के algorithmic advances, hardware improvements, और नए application domains के विस्तार के साथ लगातार बढ़ने की संभावना है

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

1 टिप्पणियां

 
GN⁺ 2025-06-16
Hacker News राय

  • किसी ने जिज्ञासा जताई कि क्या कोई यह समझा सकता है कि Gurobi जैसे commercial ILP solvers मुफ्त/open source solvers से इतने बेहतर क्यों होते हैं; क्या यह ILP की अंतर्निहित कठिनाई की वजह से है, या इसलिए कि सबसे अच्छे solvers दरअसल खास subproblems के लिए विशाल heuristics का संग्रह होते हैं, और क्या आम तौर पर "अच्छी" रणनीतियाँ अभी तक public domain में नहीं आई हैं

    • commercial solvers अक्सर ग्राहकों के साथ बहुत करीबी से काम करके problem-specific acceleration techniques लागू करते हैं, और 10~20 साल का संचित know-how रखते हैं; MILP क्षेत्र में अच्छे heuristics (branch-and-bound की शुरुआती point चुनना, प्रभावी tree pruning) और custom cuts (partial solutions को कुशलता से बाहर करना) के उपयोग पर ज़ोर दिया गया; साथ ही, OR के शोधकर्ता अगर स्वयं problem चुनकर custom cuts और heuristics लिखें तो वे अक्सर commercial solvers से भी बेहतर नतीजे पा सकते हैं, लेकिन solver कंपनियाँ इसे लगातार लागू करने के लिए PhD-स्तर की research teams रखती हैं और अनेक ग्राहकों की वास्तविक problem data के आधार पर सुधार ट्रैक करती हैं

    • commercial solvers performance tuning में भारी समय और संसाधन लगा सकते हैं क्योंकि वास्तविक ग्राहक इसकी परवाह करते हैं और मदद भी करते हैं; इसमें heuristics के अलावा simple subproblems या approximate problems को पहचानकर उनके निष्कर्षों को पूरे problem में वापस feed करना भी शामिल है; open source solvers की सीमाएँ यह हैं कि (1) state-of-the-art optimizer बनाना बहुत ऊँचा entry barrier है और math व coding दोनों में दक्ष लोग कम हैं, (2) अगर किसी के पास इतनी क्षमता हो तो वह आम तौर पर ज़्यादा कमाई वाले career में चला जाता है, (3) open source संरचना में ग्राहक सुधार के लिए cases, performance data, profiling वगैरह लगभग नहीं देते, जिससे सीमाएँ सामने आती हैं अपवाद के रूप में SNOPT जैसे commercial-purpose लेकिन non-traditional commercial development वाले उदाहरण हैं, और academic solvers अक्सर किसी खास application domain पर केंद्रित होते हैं इसलिए उनकी generality कम होती है; दूसरे क्षेत्रों में Google जैसी बड़ी कंपनियाँ खरीदकर या support देकर ecosystem बढ़ाती हैं, लेकिन solver क्षेत्र में शुरुआत से full-stack बनाना निवेश की दृष्टि से बहुत भारी पड़ता है

    • commercial solvers में सचमुच बहुत तरह के tricks और pattern-detection mechanisms होते हैं, जिनसे वे यह पहचान लेते हैं कि किस problem पर कौन-सी trick असरदार होगी; अगर problem structure अच्छी तरह पता हो तो commercial solver से भी तेज़ बनाया जा सकता है, लेकिन random problems में जीतने की संभावना लगभग नहीं होती

    • यह दावा भी आया कि "solver = specialized subproblems के लिए विविध heuristics का संग्रह"; इस पर टिप्पणी हुई कि NP-Hard problems में लगभग सब कुछ ऐसा ही होता है, और ILP, SAT के समकक्ष है इसलिए वही बात वहाँ भी लागू होती है

    • commercial scale और speed भी मुद्दा हैं; अधिकांश quant trading कंपनियाँ बहुत बड़े optimization problems को जितनी बार संभव हो उतनी बार चलाती हैं, और open source solvers अक्सर या तो problem हल ही नहीं कर पाते या memory खत्म हो जाती है; इससे अंतर का पैमाना साफ़ दिखता है

  • IBM की ILOG MILP library से resource allocation tool बनाते समय का अनुभव याद किया गया; कहा गया कि अगर यही problem 20 साल पहले हल करनी होती तो जो काम अब 5 मिनट में होता है, वह तब शायद अभी भी चल रहा होता; computers हज़ार गुना तेज़ हुए हैं और algorithms भी हज़ार गुना बेहतर हुए हैं, यानी कुल मिलाकर लगभग दस लाख गुना सुधार; भविष्य की भविष्यवाणी करते समय सोचने लायक बात, और यहाँ "resource" का मतलब diamonds था

  • सवाल उठा कि यह वास्तव में कैसे इस्तेमाल होता है; क्या numerical optimization में data-आधारित सामान्य सीमाएँ (trust, data issues वगैरह) होने के कारण आखिर में कोई महत्वपूर्ण व्यक्ति "gut feel" से निर्णय नहीं लेता?

    • एक कंपनी में पूरे stack में solvers के उपयोग का उदाहरण दिया गया: home batteries और EV scheduling का optimization, लाखों नहीं बल्कि सैकड़ों हज़ार घरों के portfolio का optimal scheduling, और उस portfolio की trading तक solver से की जाती है; EU की electricity spot prices भी Euphemia नाम के एक single giant solver run से तय होती हैं; जहाँ स्पष्ट optimization objective सीधे पैसे से जुड़ा हो, वहाँ solvers व्यापक रूप से इस्तेमाल होते हैं

    • FMCG कंपनी का वास्तविक उपयोग उदाहरण: (1) salespeople और delivery routes की planning, (2) production के लिए machines, manpower और materials की scheduling, (3) warehouses/distribution centers के लिए उचित inventory level तय करना; हालाँकि demand forecasting की कठिनाई के कारण यह पूरी तरह automated नहीं है

    • संदर्भ के लिए case study links साझा किए गए: Gurobi case studies, CPLEX case studies, Hexaly(पूर्व LocalSolver) case studies

  • पूछा गया कि Gurobi काफ़ी महँगा बताया जाता है, तो क्या कोई वास्तविक pricing जानकारी साझा कर सकता है

    • कहा गया कि सटीक कीमतें सार्वजनिक नहीं हैं, लेकिन अगर उद्देश्य MIP सीखना या अभ्यास करना है तो XPRESS/Gurobi/CPLEX जैसे commercial solvers खरीदने की ज़रूरत नहीं; student free licenses या non-commercial free/open source MIP solvers का उपयोग करना चाहिए, जैसे HiGHS, SCIP

    • सुना यह गया कि pricing लगभग "फोन करके negotiate करो" स्तर की होती है, और ग्राहक वास्तव में कितना पैसा कमाता है, उसी के हिसाब से रकम तय की जाती है

    • इस बात पर ज़ोर दिया गया कि यह धीले और suboptimal decision-making से कहीं सस्ता पड़ता है; छोटे problems के लिए free solvers (GLPK आदि) पर्याप्त हैं, लेकिन business में बड़े problems के लिए समय पर answer पाना लगभग असंभव हो सकता है, इसलिए premium solvers अपनी कीमत वसूल करते हैं

    • लगभग 10 साल पहले कई servers के license के लिए करीब 100,000 डॉलर का खर्च याद बताया गया, हालाँकि users या servers की सटीक सीमा याद नहीं थी; साथ ही कहा गया कि industry में इसे उतनी value का माना जाता है

    • Gurobi hourly billing वाला cloud service भी देता है, और non-academic licenses बहुत महँगे होते हैं

  • 1990 के दशक में Gomory cutting hyperplanes को खुद implement करने का अनुभव साझा किया गया, और इस क्षेत्र की प्रगति पर आश्चर्य जताया गया; पहले LP problem हल करने में दो महीने लगते थे, अब 1 सेकंड काफ़ी है; Bixby के एक अध्ययन के अनुसार 1990 से 2020 के बीच CPLEX और Gurobi machine performance से स्वतंत्र रूप से लगभग 40 लाख गुना तेज़ हुए

  • 1988~2004 के बीच hardware 1600 गुना तेज़ हुआ और LP solvers 3300 गुना; उस समय तक कुल speedup 50 लाख गुना से अधिक था; 2001~2020 के दौरान commercial MILP solvers भी 1000 गुना से अधिक तेज़ हुए (algorithm 50, computer 20); यह जिज्ञासा भी व्यक्त हुई कि अलग-अलग क्षेत्रों के ऐसे speedup data को algorithm और computer योगदान में बाँटकर इकट्ठा किया जाए; compiler क्षेत्र में "Proebsting's law" जैसा निष्कर्ष भी है कि हर 18 साल में compiler प्रगति, computing power के 2x बढ़ने के बराबर असर देती है

  • यह भावना व्यक्त हुई कि ML/AI आधारित approaches आश्चर्यजनक रूप से इन problems में ज़्यादा उपयोग नहीं होतीं; RL/GNN के उपयोग पर छोटे problems के लिए papers हैं, लेकिन अंत में Gurobi license खरीदना ही सबसे अच्छा लगता है; हाल में scheduling optimization करते समय RL के उदाहरण देखे गए, पर वास्तविक performance कमज़ोर थी; बड़े problems के लिए evolutionary algorithms बेहतर हो सकते हैं, लेकिन यदि problem formulation अच्छी तरह की जा सके तो OR-आधारित approach सबसे कुशल लगती है

    • कहा गया कि यह problem type पर निर्भर करता है; उदाहरण के लिए power plants के ON/OFF decision यानी unit commitment अत्यंत जटिल है, लेकिन MILP solver global optimum को तेज़ी से खोज सकता है; genetic algorithms के बारे में कहा गया कि वे local minima से बाहर निकलने की गारंटी नहीं देते और धीमे भी हो सकते हैं; neural networks भी हमेशा suboptimal होते हैं

    • यह भी कहा गया कि SAT पारंपरिक GOFAI problem है, और ML family की किसी भी भाषा में SAT solver लिखा जा सकता है; यानी "ML/AI" approach लागू करना असंभव नहीं, बल्कि काफ़ी संभव है

  • शीर्षक में pdf संकेत जोड़ने का सुझाव दिया गया

    • जवाब में कहा गया कि वह link pdf नहीं बल्कि abstract पर जाता है

    • paper का सीधा pdf reference भी जोड़ा जा सकता है: https://inria.hal.science/hal-04776866v1/document

  • यह राय आई कि Integer linear programming इतना जटिल नहीं लगता

    • जवाब में कहा गया कि graph vertex 3-coloring (G3C) NP भी है और NP-Hard भी, इसलिए NPC है; और यह परिणाम मौजूद है कि अगर सामान्य ILP हल किया जा सके तो G3C भी हल किया जा सकता है; SAT भी NP-Complete है, और SAT हल हो जाए तो G3C भी हल हो सकता है, इसलिए अगर G3C हल हो जाए तो integer factorization (FAC) भी संभव हो सकता है; FAC NPC नहीं है, लेकिन मौजूदा computing environment में अत्यंत महत्वपूर्ण है; यानी arbitrary ILP हल कर पाना प्रमुख cryptographic algorithms को तोड़ सकने की दिशा में इशारा करता है, जिससे अनुमान होता है कि ILP बहुत कठिन problem है; कई लोग इस वजह से भ्रमित होते हैं कि NPC problems की random instances अक्सर अपेक्षाकृत आसानी से हल हो जाती हैं, और कठिन instances का अनुपात problem size बढ़ने पर उल्टा घटता जाता है

    • Travelling Salesperson Problem (TSP) को भी ILP में encode किया जा सकता है, जो इसकी कठिनाई का संकेत है

    • इसमें ऐसे integers खोजने होते हैं जो constraints को सबसे अच्छी तरह संतुष्ट करें; ऊपर से यह real-valued optimization जैसा दिख सकता है, लेकिन मूल रूप से पूरी तरह अलग है; इसका कोई general solution नहीं है, केवल special cases के लिए (बहुत अच्छे) heuristics हैं

    • यह linear programming से अधिक कठिन problem है

    • या फिर इसे बहुत ही वास्तविक दुनिया की problem भी माना जा सकता है