कर्मकार का एल्गोरिथम

करमरकर का कलन विधि 1984 में रैखिक क्रमादेशन समस्याओं को हल करने के लिए नरेंद्र करमरकर द्वारा प्रस्तुत की गई किया गया एक कलन विधि है। यह पहला यथोचित कुशल कलन विधि थी जो बहुपद समय में इन समस्याओं को हल करता है। दीर्घवृत्ताभ विधि भी बहुपद समय है लेकिन व्यवहार में अक्षम सिद्ध हुई।

$n$ को चरों की संख्या और $L$ को कलन विधि में निविष्ट के बिट्स की संख्या के रूप में नकारते हुए, कर्मकर के कलन विधि को $O(n^{6}L)$ दीर्घवृत्त कलन विधि के लिए ऐसे संचालन की तुलना में $O(n^{3.5}L)$ संचालन की आवश्यकता होती है। करमरकर के कलन विधि का कार्यावधि इस प्रकार है

$O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L),$

शॉनहेज-स्ट्रैसन कलन विधि का उपयोग (बिग ओ नोटेशन देखें)।

करमरकर की कलन विधि आंतरिक-बिंदु विधियों की श्रेणी में आती है: समाधान के लिए वर्तमान अनुमान सरल विधि के रूप में व्यवहार्य सम्मुच्चय की सीमा का पालन नहीं करता है, लेकिन व्यवहार्य क्षेत्र के आंतरिक भाग के माध्यम से चलता है, इष्टतम समाधान के सन्निकटन में सुधार करता है। प्रत्येक पुनरावृत्ति के साथ एक निश्चित अंश द्वारा और तर्कसंगत आंकड़े के साथ एक इष्टतम समाधान में अभिसरण है।

कलन विधि

आव्यूह रूप में एक रैखिक क्रमादेशन समस्या पर विचार करें:

अधिकतम cTx
अधीन	Ax ≤ b.

करमरकर का कलन विधि इष्टतमता की ओर अगली व्यवहार्य दिशा निर्धारित करता है और एक कारक 0 < γ ≤ 1 द्वारा वापस मापता है। यह कई स्रोतों में वर्णित है। करमरकर ने भी पूर्णांक बाधाओं और गैर उत्तल समस्याओं के साथ समस्याओं को हल करने के लिए पद्धति का विस्तार किया है।

Algorithm Affine-Scaling

चूंकि वास्तविक एल्गोरिथम बल्कि जटिल है, शोधकर्ताओं ने इसके अधिक सहज संस्करण की तलाश की, और 1985 में affine स्केलिंग विकसित की, कर्मकर के एल्गोरिथ्म का एक संस्करण जो affine परिवर्तन का उपयोग करता है जहां कर्मकर ने प्रक्षेपी ज्यामिति का उपयोग किया, केवल चार साल बाद महसूस करने के लिए कि उनके पास था 1967 में सोवियत संघ के गणितज्ञ आई। आई। डिकिन द्वारा प्रकाशित एक एल्गोरिथम को फिर से खोजा। Affine-Scaling विधि को संक्षेप में निम्नानुसार वर्णित किया जा सकता है। एफ़िन-स्केलिंग एल्गोरिदम, जबकि छोटे पैमाने की समस्याओं पर लागू होता है, बहुपद समय एल्गोरिदम नहीं है।

Input:  A, b, c, $x^{0}$, रोक कसौटी, γ. 

$k\leftarrow 0$ do while stopping criterion not satisfied $v^{k}\leftarrow b-Ax^{k}$ $D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots ,v_{m}^{k})$ $h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c$ $h_{v}\leftarrow -Ah_{x}$ if $h_{v}\geq 0$ then

        असीमित वापसी
    अगर अंत     

$\alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}<0,\,i=1,\ldots ,m\}$ $x^{k+1}\leftarrow x^{k}+\alpha h_{x}$ $k\leftarrow k+1$

अंत करो

• "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.
• "return" terminates the algorithm and outputs the following value.

उदाहरण

उदाहरण समाधान

रैखिक कार्यक्रम पर विचार करें

${\begin{array}{lrclr}{\text{maximize}}&x_{1}+x_{2}\\{\text{subject to}}&2px_{1}+x_{2}&\leq &p^{2}+1,&p=0.0,0.1,0.2,\ldots ,0.9,1.0.\end{array}}$

अर्थात् 2 चर $x_{1},x_{2}$ और 11 बाधाओं के अलग-अलग मूल्यों $p$ के साथ जुड़े हैं। यह आंकड़ा कलन विधि के प्रत्येक पुनरावृत्ति को लाल वृत्त बिंदुओं के रूप में दिखाता है। बाधाओं को नीली रेखाओं के रूप में दिखाया गया है।

एकस्व अधिकार विवाद - क्या गणित का एकस्व अधिकार कराया जा सकता है?

जिस समय उन्होंने कलन विधि का आविष्कार किया, करमरकर को आईबीएम ने कैलिफोर्निया में आईबीएम सैन जोस अनुसंधान प्रयोगशाला में पोस्टडॉक्टोरल व्यक्ति के रूप में नियुक्त किया था। 11 अगस्त, 1983 को उन्होंने स्टैनफोर्ड विश्वविद्यालय में कलन विधि की व्याख्या करते हुए एक परिसंवाद दिया, जिसमें उनकी संबद्धता अभी भी आईबीएम के रूप में सूचीबद्ध है। 1983 के आते-आते करमरकर ने एटी एंड टी में काम करना प्रारम्भ कर दिया और 1984 एसीएम कम्प्यूटिंग के सिद्धांत पर संगोष्ठी (एसटीओसी, 30 अप्रैल - 2 मई, 1984 को आयोजित) में एटी एंड टी बेल प्रयोगशालाओं को अपनी संबद्धता बताते हुए अपना लेख जमा किया। एटी एंड टी के दूरभाष संजाल को अनुकूलित करने के लिए कलन विधि लागू करने के बाद, उन्होंने अनुभव किया कि उनका आविष्कार व्यावहारिक महत्व का हो सकता है। अप्रैल 1985 में, एटी एंड टी ने तुरंत अपने कलन विधि पर एकस्व अधिकार के लिए आवेदन किया।

सॉफ्टवेयर एकस्व अधिकार के विषय पर चल रहे विवाद के लिए एकस्व अधिकार अधिक उत्तेजक बन गया। इसने कई गणितज्ञों को असहज कर दिया, जैसे कि रोनाल्ड रिवेस्ट (स्वयं RSA (कलन विधि) कलन विधि पर एकस्व अधिकार धारकों में से एक), जिन्होंने यह राय व्यक्त की कि अनुसंधान इस आधार पर आगे बढ़ा कि कलन विधि मुक्त होना चाहिए। एकस्व अधिकार वास्तव में दिए जाने से पहले ही, यह तर्क दिया गया था कि हो सकता है कि कोई पूर्व कला हो जो लागू हो। फिलिप गिल और अन्य सहित संख्यात्मक विश्लेषण में विशेषज्ञता रखने वाले गणितज्ञों ने दावा किया कि यदि मापदंडों को उपयुक्त रूप से चुना जाता है, तो करमरकर का कलन विधि लघुगणकीय बाधा फलन के साथ अनुमानित न्यूटन बैरियर विधि के बराबर है। विधिक विद्वान एंड्रयू चिन की राय है कि गिल का तर्क त्रुटिपूर्ण था, क्योंकि वे जिस विधि का वर्णन करते हैं वह एक कलन विधि का गठन नहीं करती है, क्योंकि इसके लिए उन मापदंडों के विकल्पों की आवश्यकता होती है जो विधि के आंतरिक तर्क से पालन नहीं करते हैं, लेकिन बाहरी मार्गदर्शन, अनिवार्य रूप से करमरकर की कलन विधि पर निर्भर करते हैं। इसके अतिरिक्त, करमरकर के योगदान को सभी पूर्व कार्यों के आलोक में स्पष्ट नहीं माना जाता है, जिसमें फियाको-मैककॉर्मिक, गिल और अन्य सम्मिलित हैं, जिन्हें साल्ट्ज़मैन ने उद्धृत किया है। अमेरिकी सीनेट में एकस्व अधिकार पर चर्चा हुई थी और करमरकर के काम U.S. Patent 4,744,028: मई 1988 में "कुशल संसाधन आवंटन के लिए तरीके और उपकरण" को आवश्यक मौलिकता की पहचान के रूप में प्रदान किया गया।

एटी एंड टी ने विशेष रूप से करमरकर के कलन विधि को चलाने के लिए एक सदिश संसाधक बहु संसाधक कंप्यूटर प्रणाली तैयार करी, जो हार्डवेयर और सॉफ्टवेयर के परिणामी संयोजन को KORBX बुलाते हैं, और US$8.9 मिलियन की कीमत पर इस प्रणाली का विपणन किया। इसका पहला ग्राहक संयुक्त राज्य रक्षा विभाग था।

सॉफ्टवेयर एकस्व अधिकार के विरोधियों ने आगे तर्क दिया है कि एकस्व अधिकार ने सकारात्मक बातचीत चक्रों को बर्बाद कर दिया है जो पहले रैखिक क्रमादेशन और उद्योग में शोधकर्ताओं के बीच संबंधों की विशेषता थी, और विशेष रूप से इसने अपने क्षेत्र में गणितीय शोधकर्ताओं के संजाल से खुद को अलग कर लिया।

एकस्व अधिकार स्वयं अप्रैल 2006 में समाप्त हो गया, और कलन विधि वर्तमान में सार्वजनिक कार्यछेत्र में है।

संयुक्त राज्य अमेरिका के सर्वोच्च न्यायालय ने माना है कि गॉट्सचॉक बनाम बेन्सन में गणित का एकस्व अधिकार नहीं कराया जा सकता है, उस स्तिथि में, न्यायालय ने सबसे पहले यह देखा कि क्या कंप्यूटर कलन विधि को एकस्व अधिकार कराया जा सकता है और यह माना कि वे नहीं कर सकते क्योंकि एकस्व अधिकार प्रणाली विचारों और इसी तरह के सार की रक्षा नहीं करती है। डायमंड वी. डाइहर में, सुप्रीम कोर्ट ने कहा, एक गणितीय सूत्र को हमारे एकस्व अधिकार नियमों की सुरक्षा नहीं दी जाती है, और इस सिद्धांत को किसी विशेष तकनीकी वातावरण में सूत्र के उपयोग को सीमित करने का प्रयास करके दरकिनार नहीं किया जा सकता है। मेयो कोलैबोरेटिव सर्विसेज वी. प्रोमेथियस लैब्स., इंक. में, सर्वोच्च न्यायालय ने आगे समझाया कि केवल एक भौतिक यन्त्र, अर्थात् कंप्यूटर पर एक गणितीय सिद्धांत को लागू करना, [i] उस सिद्धांत का एकस्व अधिकार योग्य अनुप्रयोग नहीं है।

संदर्भ

• Adler, Ilan; Karmarkar, Narendra; Resende, Mauricio G.C.; Veiga, Geraldo (1989). "An Implementation of Karmarkar's Algorithm for Linear Programming". Mathematical Programming. 44 (1–3): 297–335. doi:10.1007/bf01587095. S2CID 12851754.
• Narendra Karmarkar (1984). "A New Polynomial Time Algorithm for Linear Programming", Combinatorica, Vol 4, nr. 4, p. 373–395.

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

• Evolutionary algorithm
• Hill climbing
• Local search
• Simulated annealing
• Tabu search

| below =

• Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

• पहाड़ी की चढ़ाई
• स्थानीय खोज
• तैयार किए हुयी धातु पे पानी चढाने की कला
• तब्बू खोज

| below =* सॉफ्टवेयर

}}