शोधकर्ताओं ने integer linear programming को तेज़ी से प्रोसेस करने का तरीका खोजा
(quantamagazine.org)- उत्पादन योजना, crew scheduling और vehicle routing जैसे optimization problems में, जहाँ integer-unit decisions की ज़रूरत होती है, Victor Reis और Thomas Rothvoss ने ILP runtime को काफी कम करने वाला नया algorithm पेश किया
- ILP सामान्य linear programming से ज़्यादा कठिन है, और 1980 के दशक के बाद से रिकॉर्ड-स्तर के सुधार लगभग नहीं हुए थे, इसलिए इस परिणाम को कई दशकों में बड़ी प्रगति माना जा रहा है
- नया approach lattice और convex body के intersection से जुड़े geometric tools को मिलाकर संभावित integer solutions की range को और मज़बूती से सीमित करता है
- मुख्य बात 2016 के lattice points से जुड़े result का उपयोग करके covering radius की upper bound को घटाना है, जिससे runtime ((\log n)^{O(n)}) स्तर तक कम हो जाता है
- यह अभी सीधे वास्तविक logistics systems में लागू नहीं हुआ है, लेकिन ILP की theoretical speed limit के लगभग नज़दीक परिणाम के रूप में practical solvers को बेहतर बनाने की लंबी अवधि की दिशा दिखाता है
integer constraints optimization को कठिन क्यों बनाते हैं
- traveling salesman problem कई शहरों से गुजरने वाला सबसे छोटा route खोजने की पुरानी computational problem है, और अगर सभी संभव routes की जाँच की जाए तो शहरों की संख्या थोड़ी भी बढ़ने पर यह संभालना मुश्किल हो जाता है
- linear programming equations और inequalities के ज़रिए संभावित combinations को व्यवस्थित रूप से संभालने वाला mathematical model है
- वास्तविक optimization problems में decimal answers अक्सर उपयोगी नहीं होते
- factory optimization plan में 500.7 सोफे बनाने का उत्तर व्यावहारिक decision के रूप में इस्तेमाल करना कठिन है
- integer linear programming (ILP) ऐसी integer constraints वाली linear programming की variant है, और production planning, airline crew scheduling, vehicle routing जैसे discrete decision problems में व्यापक रूप से इस्तेमाल होती है
- Santosh Vempala ILP को operations research में theory और practice दोनों के लिए एक core tool मानते हैं
1980 के दशक के बाद धीरे-धीरे सुधरी speed limit
- ILP को 60 से अधिक साल पहले formalize किए जाने के बाद कई algorithms आए, लेकिन आवश्यक steps की संख्या के हिसाब से यह अब भी धीमी मानी जाती थी
- सबसे सरल baseline वह case है जहाँ variables केवल 0 या 1 value ले सकते हैं, यानी binary variables
- 1 variable के लिए 2 संभावित combinations
- 2 variables के लिए 4
- 3 variables के लिए 8
- सामान्य रूप से runtime variables की संख्या, यानी dimension, के साथ exponentially बढ़ता है
- अगर variables 0 और 1 से आगे व्यापक integer values ले सकते हैं, तो runtime और भी बहुत लंबा हो जाता है
- researchers लंबे समय से यह खोज रहे थे कि क्या general ILP को इस सरल binary case की speed के और करीब लाया जा सकता है
- 1980 के दशक के records के बाद केवल incremental improvements ही जारी रहे
Lenstra द्वारा खोली गई geometric interpretation
- 1983 में Hendrik Lenstra ने साबित किया कि general ILP problems हल किए जा सकते हैं, और इसके लिए पहला algorithm पेश किया
- Lenstra ने ILP को geometric problem में बदलकर संभाला
- ILP की inequalities एक convex shape, यानी convex body के रूप में व्यक्त होती हैं
- shape का अंदरूनी हिस्सा उन सभी संभावित values से मेल खाता है जो inequalities को satisfy कर सकती हैं
- 2-variable problem plane polygon की तरह, और 3-variable problem 3D solid की तरह होती है; variables बढ़ने पर dimensions बढ़ते हैं
- सभी integers को mathematically lattice के points के रूप में देखा जा सकता है
- 2D में यह points के समुद्र जैसा दिखता है
- 3D में यह building steel frame के मिलन-बिंदुओं जैसी structure बन जाता है
- आखिरकार ILP हल करना convex body और lattice के intersection को, यानी वह जगह जहाँ संभावित solution integer point से मिलता है, खोजने की problem बन जाता है
- Lenstra का algorithm इस space को explore कर सकता था, लेकिन efficiency के लिए कभी-कभी problem को कम dimensions वाले pieces में बाँटना पड़ता था, और यह process runtime बढ़ा देता था
covering radius से बना 30 साल का bottleneck
- 1988 में Ravi Kannan और László Lovász ने error-correcting codes research से लिए गए covering radius concept के जरिए convex body और lattice के intersection को अधिक efficiently संभालने की कोशिश की
- covering radius उस size से जुड़ा है जो यह guarantee करता है कि convex body को lattice पर कहीं भी रखा जाए, उसमें कम से कम एक integer point शामिल होगा
- इस value का size तय करता है कि ILP problem कितनी efficiently हल हो सकती है
- ideal covering radius का size पता लगाना अपने आप में कठिन problem था
- Kannan और Lovász ने संभावित value को upper और lower bounds के जरिए संकुचित किया, और दिखाया कि upper bound dimension के साथ linearly बढ़ती है
- सिर्फ इस result से ILP runtime को बहुत घटाना पर्याप्त नहीं था, और अगले 30 वर्षों तक improvements सीमित रहे
Reis और Rothvoss का नया algorithm
- Victor Reis और Thomas Rothvoss ने lattice पर केंद्रित अलग mathematical result का उपयोग करके breakthrough बनाया
- 2016 में Oded Regev और Noah Stephens-Davidowitz ने दिखाया कि किसी specific shape के अंदर कितने lattice points आ सकते हैं
- Reis और Rothvoss ने इस result को दूसरे shapes पर लागू करके ILP के covering radius के भीतर शामिल lattice points की संख्या का बेहतर estimate लगाया
- इस estimate से upper bound घट गई, और पूरे ILP algorithm का runtime काफी कम हो गया
- नया runtime ((\log n)^{O(n)}) है, जहाँ (n) variables की संख्या है और (O(n)) (n) के साथ linearly proportional है
- इस expression को binary variable problem के runtime के “लगभग” समान स्तर का माना जाता है
theoretical achievement और practical application के बीच दूरी
- Noah Stephens-Davidowitz नए algorithm को लगभग 40 वर्षों में ILP solver का पहला major improvement मानते हैं
- Daniel Dadush इस result को mathematics, computer science और geometry के intersection से निकली उपलब्धि मानते हैं
- नया algorithm अभी वास्तविक logistics problems हल करने में इस्तेमाल नहीं हुआ है
- मौजूदा programs को इस method के अनुरूप update करने के लिए काफी काम करना होगा
- Rothvoss का मानना है कि इस result का focus fundamental applications वाली problem की theoretical understanding पर है
- ILP computation efficiency और बेहतर होने की संभावना बनी हुई है, लेकिन Vempala मानते हैं कि ideal runtime के और करीब जाने के लिए fundamentally नए ideas की ज़रूरत होगी
1 टिप्पणियां
Hacker News टिप्पणियाँ
किसी प्रमुख NP-पूर्ण समस्या के algorithmic upper bound को कम करना हमेशा बहुत दिलचस्प होता है, लेकिन इसका यह मतलब ज़रूरी नहीं कि वह समस्या वास्तविक implementation में भी तेज़ी से हल होगी
Mixed Integer Programming (MIP) solvers कई algorithms और बड़ी मात्रा में heuristics को साथ में इस्तेमाल करते हैं, और heuristics व strategy libraries का लगातार बढ़ना ही वह मुख्य कारण रहा है जिसकी वजह से MIP solvers में सुधार Moore’s law से भी आगे निकल गया
https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/6... के अनुसार 1990~2014 के बीच hardware में 6500x सुधार हुआ, जबकि software ने 870000x performance improvement में योगदान दिया
यह paper भी MIP solver performance improvement को आगे बढ़ाने वाला एक puzzle piece बन सकता है, लेकिन ऐसा होगा ही, इसकी गारंटी नहीं है
यह बात ठीक से समझ नहीं आती कि नए algorithm का अभी तक logistics problems सुलझाने में उपयोग न होने की वजह यह है कि “आजकल programs को update करने के लिए बहुत ज़्यादा काम चाहिए”
ज़्यादातर domain-specific models बड़े problems के लिए Gurobi, CPLEX, FICO solvers को call करते हैं, और छोटे problems के लिए SCIP जैसे open-source solvers का इस्तेमाल करते हैं
standard MPS format में इन solvers के बीच models को exchange किया जा सकता है, problem formulation बदलती नहीं है, और सिर्फ solver के अंदर solve करने का तरीका बदलना चाहिए — क्या बात बस इतनी नहीं है?
अगर मतलब यह है कि नई implementation चाहिए, तो implementation हो जाने पर दुनिया को मिलने वाला लाभ भी बहुत बड़ा लगता है
ये tools कई दशकों के incremental improvements से बने बेहद जटिल engineering products हैं, इसलिए इस नई खोज को ऐसे engines में integrate करने का तरीका समझने में ही काफ़ी research effort लग सकता है
यह सही है कि MPS जैसे formats के जरिए problem formulations exchange करने का standard तरीका है, और आजकल AMPL जैसी algebraic modeling languages शायद ज़्यादा इस्तेमाल होती हैं, लेकिन ऐसे formats सिर्फ standard mathematical formulation देते हैं
असली solving हर solver के लिए बहुत specialized होती है, और हर एक के अपने data structures, algorithms, और heuristic techniques होते हैं
ये एक-दूसरे के बदले सीधे इस्तेमाल नहीं किए जा सकते, इन्हें जानबूझकर public भी नहीं किया जाता, और solver code व पूरे process की जानकारी के बिना बीच में बाहर से कुछ numbers डालकर काम नहीं चल सकता
मैं बस यह गलतफ़हमी दूर करना चाहता था
जहाँ तक हो सके, लोग ऐसी चीज़ों में सीधे implementation करने से बचना चाहते हैं
फिर भी यह एक शानदार नतीजा है
theoretical computational complexity के नज़रिए से “integer linear programming” [2] के सबसे अच्छे algorithms lattice-based हैं, और worst case में उनकी big-O complexity सबसे बेहतर मानी जाती है
लेकिन मौजूदा implementations आम तौर पर (1) gmplib [3] जैसे arbitrary-size rational arithmetic की मांग करती हैं, जो memory बहुत खाती है और व्यवहार में भी धीमी होती है, और (2) LLL-type lattice reduction steps [4] की ज़रूरत होती है, लेकिन वे matrix sparsity का फायदा नहीं उठा पातीं
नतीजतन, ऐसे algorithms आम तौर पर memory में फिट ही नहीं होते, इसलिए 1000x1000 से बड़े matrix problems पर शुरू भी नहीं कर पाते, और अगर फिट हो भी जाएँ तो बहुत धीमे होते हैं
व्यावहारिक integer programming solvers इसके बजाय branch-and-bound पर आधारित होते हैं, जो SAT solving में इस्तेमाल होने वाले backtracking algorithms से मिलता-जुलता है, और हर iteration पर मूल problem में सभी variables को continuous variables में बदलकर एक “linear programming” problem हल करते हैं
हर linear programming problem को interior-point methods जैसे polynomial-time algorithms से हल किया जा सकता है, लेकिन व्यवहार में लोग simplex method का इस्तेमाल करते हैं, जो worst case में exponential time लेता है
वजह यह है कि जिन linear programming problems को हल करना होता है वे एक-दूसरे से बहुत मिलती-जुलती होती हैं, और simplex method व्यवहार में इस समानता का अच्छा फायदा उठा लेता है
इसके अलावा, संबंधित algorithms vectors और matrices की sparsity का भी बहुत लाभ उठाते हैं
इसलिए कुछ लोग millions of variables वाले integer programming problems भी कुछ दिनों, यहाँ तक कि कुछ घंटों में हल कर लेते हैं
solver implementers सैद्धांतिक रूप से बिल्कुल सबसे अच्छी complexity के पीछे नहीं भाग रहे होते, और कहा जा सकता है कि discrete optimization की theory और practice कुछ हद तक अलग रास्तों पर चली गई हैं
फिर भी Reis & Rothvoss का paper [1] गहरे गणितीय काम का परिणाम है, और discrete mathematics में रुचि रखने वालों के लिए अपने आप में बहुत प्रभावशाली है
इसने Dadush की 10 साल पुरानी conjecture को हल किया, और पिछले नवंबर में computer science theory की दो शीर्ष conferences में से एक FOCS में पेश किया गया
इसकी सीधी practical usefulness मुख्य बात नहीं है, और authors भी अनौपचारिक बातचीत में शायद यह मानेंगे
हाँ, grant proposal में वे शायद कुछ और कहें, लेकिन वह इस खेल का हिस्सा है
इसका मतलब यह नहीं कि यह बेकार है; सिर्फ mathematical knowledge को आगे बढ़ाना भी बहुत बड़ी value रखता है, और हो सकता है कि आने वाली कुछ पीढ़ियों के researchers इसी idea पर practical algorithms बनाएँ जो solver state of the art को आगे धकेल दें
आखिरकार, ये algorithms worst case में सभी exponential time ही हैं
theory में लोग worst-case complexity के exponent में मौजूद polynomial को थोड़ा कम करने की कोशिश करते हैं, लेकिन practitioners आम तौर पर ऐसे problem families में दिलचस्पी नहीं रखते जहाँ size n बढ़ता जाता है; वे अक्सर सिर्फ एक बड़ा optimization problem हल करना चाहते हैं
solving-time trendline की growth rate से ज़्यादा अहम यह है कि सामने रखा एक बड़ा instance हल होता है या नहीं, और उस instance में आम तौर पर ऐसी structure होती है जो उसे उसी size के worst case बनने से बचाती है
इसलिए engineering choices भी अलग होती हैं
[1] https://arxiv.org/abs/2303.14605
[2] min { c^T x : A x >= b, x in R^n, some components of x in Z }
[3] https://gmplib.org/
[4] https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.p...
सारांश ज़्यादा उपयोगी है: https://arxiv.org/abs/2303.14605
इसमें कहा गया है कि n variables वाली integer programming को हल करने के लिए (log(2n))^O(n) समय का randomized algorithm प्राप्त किया गया है
यानी यह काम एक सैद्धांतिक परिणाम है, जो R^n में convex bodies की संरचना और उन्हें integer lattice से कैसे कवर किया जाए, इसके विश्लेषण पर आधारित है, और पहले के सर्वश्रेष्ठ से बेहतर exponential-time algorithm प्रस्तुत करता है
ज़्यादातर practical ILP काम heuristic और branch-and-bound का उपयोग करते हैं, और किसी विशेष problem formulation की खास संरचना का फायदा उठाते हैं
यह शोध उन दोनों में से किसी एक के लिए मददगार होगा या नहीं, यह स्पष्ट नहीं है, और Gurobi जैसी जगह से कोई समझाए बिना केवल paper पढ़कर इसका अंदाज़ा लगाना कठिन लगता है
छोटी-सी टिप्पणी है, लेकिन शीर्षक में integer linear programming स्पष्ट रूप से लिखा होना चाहिए
क्योंकि यहाँ “integer” वाला हिस्सा बहुत बड़ा अंतर पैदा करता है
linear programming के लिए दशकों पहले से polynomial-time algorithms ज्ञात हैं, जबकि integer linear programming NP-hard है
continuous linear programming भी कठिन है
इसका मतलब NP-hard होना नहीं है, बल्कि यह कि efficient modern LP solvers बनाने के लिए algorithmic और engineering दोनों पहलुओं में बहुत काम लगता है
केवल numerical computation ही काफ़ी जटिल है
और कई integer linear programming solvers, continuous linear programming solvers पर आधारित होते हैं
अगर आप machine learning या algorithms में रुचि रखने वाले software engineer हैं, तो linear programming सीखना सार्थक हो सकता है
चौंकाने वाली संख्या में समस्याओं को linear optimization के रूप में formulate किया जा सकता है
उदाहरण के लिए, कॉलेज के समय मैंने industrial engineering पढ़ने वाले एक दोस्त से billiard balls को rack triangle के भीतर अनुमत शुरुआती स्थितियों में रखने के लिए आवश्यक औसत न्यूनतम swaps की संख्या पर बात की थी
हम दोनों ने इसे Monte Carlo sampling से हल करने वाला प्रोग्राम लिखा था; मेरा solution graph state space में BFS करता था, जबकि मेरे दोस्त का solution linear programming इस्तेमाल करता था
शायद मेरे दोस्त वाला ज़्यादा efficient रहा होगा
उदाहरण के लिए minimum spanning tree, bipartite या general graph matching, network flow, matroid intersection, submodular flow आदि
कुछ LP के vertex solutions में ऐसे रोचक गुण भी होते हैं जिनका उपयोग NP-complete problems के approximation algorithms डिज़ाइन करने में किया जा सकता है
उदाहरण के लिए, Steiner forest problem के vertex solutions में हमेशा कम-से-कम 1/2 मान वाला एक variable मौजूद होता है; इसलिए variables को बार-बार round करके और LP को फिर से solve करके 2-approximation algorithm प्राप्त किया जा सकता है
graduate school के समय यह इस problem के लिए ज्ञात एकमात्र 2-approximation algorithm था
एक और रोचक बात यह है कि यदि आपके पास polynomial-time separation oracle हो, तो constraints की संख्या exponential होने पर भी LP को solve किया जा सकता है
वह सचमुच बहुत मज़ेदार था और मैं इसकी सिफारिश करूँगा
अभी भी operations research में आश्चर्यजनक रूप से बहुत overlap है, लेकिन यह देखकर झटका लगता है कि industrial engineering graduates में इतने लोग हैं जो ठीक से programming नहीं कर पाते
यह सचमुच अफ़सोस की बात है
आमतौर पर केवल cents में integer amounts का ही trade किया जा सकता था, इसलिए याद पड़ता है कि integer हिस्सा काफ़ी महत्वपूर्ण था
छोटा है, लेकिन अच्छा लेख है
मैंने अभी तक गणित को गहराई से नहीं देखा है, लेकिन preprint शायद यही है: https://arxiv.org/pdf/2303.14605.pdf
यह symmetry या repetition को कम करके problem “space” को generalize और simplify करने के तरीके से space groups को सीधे देखता हुआ नहीं लगता, लेकिन यह देखना दिलचस्प होगा कि क्या ऐसी संरचना लागू हो सकती है
मैं ऐसा सॉफ़्टवेयर इस्तेमाल करता हूँ जो space groups लागू करता है और उनमें वितरित points या point sets के आसपास की Voronoi cells का वर्णन करता है, इसलिए प्रभावों के फैलने के “अजीब” तरीक़ों से मैं परिचित हूँ [1]
मैं mathematician नहीं हूँ, बस एक architect हूँ, इसलिए यह क्षेत्र मेरी विशेषज्ञता से बाहर है, लेकिन generated honeycomb structures के आर-पार paths को देखने वाले व्यक्ति के रूप में यह परिणाम आगे जाँचने लायक लगता है
[0] https://arxiv.org/pdf/2303.14605.pdf
[1] अगर आप ऐसे काम पर सहयोग कर सकने वाले किसी mathematician को जानते हों, तो संपर्क करने पर अच्छा लगेगा
यह काम प्रगति पर है, और जैसा मैंने कहा, गणितीय रूप से यह मेरी क्षमता के बाहर है, लेकिन मुझे कुछ ऐसे दिलचस्प गुण मिले हैं जिन्हें कोई वास्तविक विशेषज्ञ और गहराई से देखना चाहेगा
Traveling Salesman Problem के संदर्भ में Sapolsky की नई किताब Determined: A Science of Life without Free Will का एक उद्धरण दिलचस्प है
यह software developers के लिए कितना प्रासंगिक है, पता नहीं, लेकिन आकर्षक है
जब कोई चींटी आठ जगहों की जाँच करते हुए भोजन खोजती है, तो आदर्श रूप से उसे हर जगह केवल एक बार जाना चाहिए और 5,040 संभावित मार्गों, यानी 7!, में से सबसे छोटा मार्ग चुनना चाहिए
यह प्रसिद्ध Traveling Salesman Problem का एक रूप है, जिससे गणितज्ञ सदियों से जूझ रहे हैं, लेकिन इसका कोई सामान्य हल नहीं मिला है
एक रणनीति brute force है, जिसमें सभी संभावित मार्गों को देखकर और तुलना करके सबसे अच्छा मार्ग चुना जाता है, लेकिन केवल 10 ठिकानों पर ही संभावित तरीकों की संख्या 3.6 लाख से ऊपर चली जाती है, और 15 ठिकानों पर 80 अरब से अधिक हो जाती है
लेकिन अगर सामान्यतः किसी colony की लगभग 10,000 चींटियों को इस आठ-भोजन-बिंदु समस्या पर छोड़ दिया जाए, तो कोई भी चींटी अपने चले हुए रास्ते और दो नियमों से अधिक कुछ न जानते हुए भी brute force की तुलना में बहुत कम समय में 5,040 संभावनाओं में से लगभग सर्वोत्तम के क़रीब हल ढूँढ लेती है
कहा जाता है कि यह तरीका इतना अच्छा काम करता है कि computer scientists भी ऐसे प्रश्नों को “virtual ants” से हल करते हैं, और इसे अब swarm intelligence कहा जाता है
और इसका मानक जवाब होता है, “बहुत साधारण computer algorithms भी ऐसा करते हैं”
Traveling Salesman Problem में अगर Euclidean distance हो, यानी हर node के स्थिर coordinates हों और मार्ग की लागत दो बिंदुओं के बीच की Euclidean distance हो, तो optimal solution के ε-गुना के भीतर का मार्ग खोजने वाला polynomial-time algorithm भी दिया जा सकता है
हालांकि ε के संदर्भ में वह exponential होता है
उसकी प्रस्तावना में एक शानदार disclaimer भी है
“हम व्यक्तिगत रूप से मानते हैं कि इस क्षेत्र के साहित्य में marsupials कम और mathematics ज़्यादा होनी चाहिए, और एक समुदाय के रूप में हमें इस metaphor-समृद्ध दौर से आगे बढ़ना चाहिए; यह कुछ वैसा ही है जैसे chemistry ने alchemy को पीछे छोड़ा। फिर भी, यह सूची सूचीबद्ध शोध-पत्रों की वैज्ञानिक गुणवत्ता के बारे में कोई दावा नहीं करती।”
[1]: https://fcampelo.github.io/EC-Bestiary/
यह ऐसे चींटी-colony behavior को मॉडल करने वाला algorithm है
जैसा दूसरों ने कहा, यह tabú search, simulated annealing, genetic algorithms की तरह local optimum ढूँढने में अच्छा है
लेख में दिए गए “sofa production” जैसे ज़्यादातर business उद्देश्यों के लिए इतना काफ़ी होता है
लेकिन यह “general solution” खोजने से अलग बात है
Sapolsky का यह तुलना करना कि हम “general solution” खोजने में कमज़ोर हैं जबकि चींटियाँ local optimum ढूँढ सकती हैं, थोड़ा भ्रामक लगता है
इसका मतलब यह नहीं कि समस्या का सामान्य रूप NP-hard नहीं है, बल्कि यह कि अगर और जानकारी जोड़ दी जाए तो काफ़ी अच्छा approximation या optimal search संभालना संभव हो सकता है
यह दृष्टिकोण पहली AI “revolution” के दौरान ख़ास तौर पर प्रमुख था, जब AI को मानव ज्ञान से सशक्त किए गए search problem के रूप में देखना लोकप्रिय था
क्या किताब में जिस “swarm intelligence” की बात है, वह यही है?
कई discrete optimization समस्याओं को linear programming में बदला जा सकता है
SAT solvers की तरह, यह जानने लायक़ सचमुच शक्तिशाली tool है
developer के रूप में यह उन पलों में से एक था जब लगा, “मैंने अब तक इसे कैसे मिस कर दिया?”
शानदार परिणाम है, लेकिन शायद व्यावहारिक नहीं होगा
यह कुछ वैसा है जैसे linear programming में interior-point methods की theoretical complexity simplex method से बेहतर होती है, लेकिन वास्तविक दुनिया में अच्छी तरह tuned simplex लगभग हमेशा जीत जाता है
क्या इस बात के लिए कोई व्यापक रूप से स्वीकार किया गया “कारण” है कि interior-point methods व्यवहार में आम तौर पर धीमे होते हैं?
ऐसा लगता है कि boundary से बँधे रहने की बजाय interior से गुज़रना अच्छे हल तक तेज़ी से पहुँचना चाहिए, लेकिन शायद high dimensions में वह अंतर कम महत्वपूर्ण हो जाता है
यहाँ की भाषा थोड़ी भ्रमित करने वाली है
एक वाक्य है: “उनका सबसे अच्छा संस्करण, एक तरह की speed limit, उस तुच्छ मामले से आता है जहाँ समस्या के variables केवल binary values ले सकते हैं, यानी 0 या 1, जैसे कि salesman किसी शहर में जाता है या नहीं।” क्या यहाँ NP-complete problem को तुच्छ मामला कहा जा रहा है?
मेरी समझ थी कि सभी ILP को 01-ILP में reduce किया जा सकता है, और उल्टा भी
और फिर यह हिस्सा, “दुर्भाग्य से, जब variables 0 और 1 से आगे के मान ले सकते हैं, तो algorithm का running time बहुत लंबा हो जाता है। शोधकर्ता लंबे समय से सोचते रहे हैं कि क्या वे इस तुच्छ ideal के और क़रीब पहुँच सकते हैं।” इसे देखकर समझ नहीं आता कि यह शोध 01-ILP के lower bound को सुधारने वाला solver है, या फिर 01-ILP और सामान्य ILP के बीच की सीमा को और क़रीब लाने वाला algorithm है