Graver basis
अनुप्रयुक्त गणित में, ग्रेवर आधार बहुपद समय में रैखिक और विभिन्न अरैखिक पूर्णांक प्रोग्रामिंग समस्याओं के पुनरावृत्ति समाधान को सक्षम करते हैं। उन्हें जैक ई. ग्रेवर द्वारा पेश किया गया था। ग्रोबनर आधारों के सिद्धांत के साथ उनके संबंध पर बर्न्ड स्टर्मफेल्स द्वारा चर्चा की गई थी। ग्रेवर आधारों के एल्गोरिथमिक सिद्धांत और पूर्णांक प्रोग्रामिंग के लिए इसके अनुप्रयोग का वर्णन श्मुएल ओन द्वारा किया गया है। औपचारिक परिभाषा एक m × n पूर्णांक मैट्रिक्स का ग्रेवर आधार एक अच्छी तरह से आंशिक क्रम के तहत सेट में न्यूनतम तत्वों का परिमित सेट है जिसे कब और सभी i के लिए परिभाषित किया गया है। उदाहरण के लिए, के ग्रेवर आधार में वैक्टर (2,-1,0), (0,-1,2), (1,0,-1), (1,-1,1) और उनके नकारात्मक शामिल हैं। ग्रेवर आधारों का उपयोग करके पूर्णांक प्रोग्रामिंग को हल करना पूर्णांक प्रोग्रामिंग रैखिक असमानताओं की एक प्रणाली को संतुष्ट करने वाले पूर्णांक बिंदुओं के सेट पर एक रैखिक या अरैखिक उद्देश्य फ़ंक्शन को अनुकूलित करने की समस्या है। औपचारिक रूप से, इसे मानक रूप में निम्नानुसार लिखा जा सकता हैः यह सबसे मौलिक असतत अनुकूलन समस्याओं में से एक है और इसमें बहुत व्यापक प्रतिरूपण शक्ति और विभिन्न क्षेत्रों में कई अनुप्रयोग हैं, लेकिन आमतौर पर बहुत कठिन कम्प्यूटेशनल है जैसा कि नीचे उल्लेख किया गया है। हालाँकि, ग्रेवर आधार को देखते हुए, रैखिक और विभिन्न अरैखिक उद्देश्य कार्यों के साथ समस्या को बहुपद समय में हल किया जा सकता है जैसा कि आगे बताया गया है। रैखिक पूर्णांक प्रोग्रामिंग सबसे अधिक अध्ययन किया गया मामला, जिसे अच्छी तरह से माना जाता है, रैखिक पूर्णांक प्रोग्रामिंग का है, यह माना जा सकता है कि सभी चर नीचे और ऊपर से बंधे हैंः ऐसी सीमाएं या तो हाथ में अनुप्रयोग में स्वाभाविक रूप से दिखाई देती हैं, या किसी भी इष्टतम समाधान को खोए बिना लागू की जा सकती हैं। लेकिन, रैखिक उद्देश्य कार्यों के साथ भी समस्या एन. पी.-कठिन है और इसलिए संभवतः बहुपद समय में हल नहीं किया जा सकता है। हालाँकि, के ग्रेवर आधार में निम्नलिखित गुण हैं। प्रत्येक संभव बिंदु x के लिएः या तो x इष्टतम है (यानी, बाधाओं को देखते हुए कम करता है); या एक वेक्टर g मौजूद है, जैसे कि x + g संभव है और (यानी, x को इसमें ग्रेवर आधार का एक तत्व जोड़कर सुधार किया जा सकता है)। इसलिए, ग्रेवर आधार को देखते हुए, आईएलपी को निम्नलिखित सरल पुनरावृत्ति एल्गोरिदम का उपयोग करके बहुपद समय में हल किया जा सकता है। पहले मान लीजिए कि कुछ प्रारंभिक व्यवहार्य बिंदु x दिया गया है। जब भी संभव हो, निम्नलिखित पुनरावृत्ति को दोहराएंः सकारात्मक पूर्णांक q और तत्व g को ऐसे खोजें कि x + qg सीमाओं का उल्लंघन न करे और सर्वोत्तम संभव सुधार दे; x: = x + qg को अद्यतन करें और अगले पुनरावृत्ति के लिए आगे बढ़ें। अंतिम बिंदु x इष्टतम है और पुनरावृत्तियों की संख्या बहुपद है। एक प्रारंभिक व्यवहार्य बिंदु खोजने के लिए, एक उपयुक्त सहायक कार्यक्रम स्थापित किया जा सकता है और इसी तरह से हल किया जा सकता है। गैर-रैखिक पूर्णांक प्रोग्रामिंग सामान्य वस्तुनिष्ठ फलन f के मामले की ओर मुड़ते हुए, यदि चर असीमित हैं तो समस्या वास्तव में अकल्पनीय हो सकती हैः यह हिल्बर्ट की 10वीं समस्या के समाधान से मिलता है (देखें) कि कोई एल्गोरिथ्म मौजूद नहीं है, जो 58 चर में डिग्री 8 के पूर्णांक बहुपद f को देखते हुए, यह तय करता है कि सभी 58-आयामी पूर्णांक वैक्टरों पर f का न्यूनतम मान 0 है या नहीं। हालांकि, जब चर बंधे होते हैं, तो कई अरैखिक वस्तुनिष्ठ कार्यों के लिए बहुपद समय में ग्रेवर आधार का उपयोग करके समस्या को हल किया जा सकता है, जिसमें शामिल हैंः रूप के पृथक्कृत-उत्तल कार्य; विशेष रूप से प्रत्येक सकारात्मक पूर्णांक p के लिए p-मानक; समग्र-संघटक कार्य f (x) = g (Wx), जहां W निश्चित d के साथ एक d × n पूर्णांक मैट्रिक्स है, और जहां g एक d-चर अवतल कार्य है; निश्चित (in)-निश्चित द्विघात और उच्च डिग्री बहुपद कार्य। कुछ अनुप्रयोग बहु-आयामी तालिकाएँ गैर-ऋणात्मक पूर्णांकों (जिनका अधिकतम मान ऊपर से सभी चरों को निहित रूप से सीमित करता है) के साथ निर्धारित पंक्ति योग के साथ त्रि-आयामी तालिकाओं पर निम्नलिखित अनुकूलन समस्या पर विचार करें। इस प्रणाली के परिभाषित मैट्रिक्स को (lm + ln + mn) × (lmn) से निरूपित करें। ध्यान दें कि यह मैट्रिक्स आम तौर पर पूरी तरह से यूनिमॉड्यूलर नहीं है। फिर भी, यह दिखाया गया था कि प्रत्येक निश्चित l और m के लिए, इसके ग्रेवर आधार की गणना समय में की जा सकती है जो n में बहुपद है। ऊपर बताए गए परिणाम इस समस्या को निश्चित l और m और चर n के लिए बहुपद समय में हल करने की अनुमति देते हैं। ध्यान दें कि यदि तालिका का केवल एक पक्ष l निश्चित है (यहां तक कि l = 3 के साथ भी) जबकि m और n दोनों चर हैं, तो समस्या NP कठिन है, जैसा कि दिखाया गया है। अधिक आम तौर पर, उच्च-आयामी तालिका समस्याओं के लिए समान सकारात्मक परिणाम होते हैंः प्रत्येक निश्चित डी के लिए और, चर एन और निर्धारित मार्जिन के साथ तालिकाओं पर (गैर)-रैखिक अनुकूलन बहुपद समय में किया जा सकता है। सांख्यिकीय डेटाबेस में सुरक्षा समस्याओं और गोपनीयता को दर्ज करने के लिए इसके और अनुप्रयोग हैं। बहु-वस्तु प्रवाह आपूर्ति, खपत और क्षमता की बाधाओं के अधीन m आपूर्तिकर्ताओं से n उपभोक्ताओं तक k प्रकार की पूर्णांक वस्तुओं को रूट करने की पूर्णांक बहु-वस्तु प्रवाह समस्या पर विचार करें, ताकि चाप पर रैखिक या भीड़-भाड़-निर्भर उत्तल लागतों के योग को कम किया जा सके। फिर प्रत्येक निश्चित k और m के लिए, परिभाषित प्रणाली के ग्रेवर आधार की गणना की जा सकती है और परिणामस्वरूप पृथक्कृत-उत्तल वस्तुनिष्ठ कार्य को समय में न्यूनतम किया जा सकता है जो उपभोक्ताओं की चर संख्या n में बहुपद है और शेष डेटा में। अन्य अनुप्रयोग ग्रेवर आधारों के एल्गोरिथमिक सिद्धांत के कई अनुप्रयोगों में शामिल हैंः यादृच्छिक पूर्णांक प्रोग्रामिंग, एन-गुना पूर्णांक प्रोग्रामिंग, एन-गुना 4-ब्लॉक अपघटनीय पूर्णांक प्रोग्रामिंग, क्लस्टरिंग, सांख्यिकीय डेटाबेस में प्रकटीकरण नियंत्रण, और अविभाज्य वस्तुओं का उचित आवंटन। इनमें से कुछ अनुप्रयोगों में प्रासंगिक ग्रेवर आधार की गणना बहुपद समय में नहीं की जा सकती है, लेकिन इसे अप्रत्यक्ष तरीके से प्राप्त किया जा सकता है जो इसे बहुपद समय में उपयोग करने की अनुमति देता है। सार्वभौमिकता और परिमाणीकरण यह दिखाया गया था कि प्रत्येक (सीमित) पूर्णांक प्रोग्रामिंग समस्या कुछ m और n और कुछ पंक्ति योगों के लिए ऊपर चर्चा की गई 3 × m × n तालिका समस्या के बराबर है। इस प्रकार, ऐसी 3 × m × n तालिका समस्याएं पूर्णांक प्रोग्रामिंग के लिए सार्वभौमिक हैं। इसके अलावा, प्रत्येक निश्चित m के लिए, पूर्णांक कार्यक्रमों के परिणामी वर्ग को ऊपर वर्णित पुनरावृत्ति ग्रेवर आधार विधि द्वारा बहुपद समय में हल किया जा सकता है। इसलिए तालिका की चौड़ाई m सभी पूर्णांक प्रोग्रामिंग समस्याओं का एक मापदंड प्रदान करती है। पूर्णांक प्रोग्रामिंग के लिए सन्निकटन का पदानुक्रम मैट्रिक्स के ग्रेवर आधार द्वारा दर्शाया जाता है जो ऊपर चर्चा की गई सार्वभौमिक 3 × m × n तालिका समस्या को परिभाषित करता है। के तत्व 3 × m × n तालिकाएँ हैं जिनमें सभी रेखा योग 0 के बराबर हैं। इस तरह की तालिका का प्रकार इसकी गैर-शून्य 3 × m परतों की संख्या है। यह पता चला है कि एक परिमित ग्रेवर जटिलता फलन g (m) ऐसा है कि किसी भी n के लिए, ग्रेवर आधार के किसी भी तत्व का प्रकार अधिकतम g (m) है। यह इस प्रकार है कि ग्रेवर आधार ग्रेवर आधार की उपयुक्त रूप से एम्बेडेड प्रतियों का संयोजन है। व्यवहार में एक मनमाने पूर्णांक प्रोग्रामिंग समस्या को लगभग हल करने के लिए, निम्नानुसार आगे बढ़ें। पहले इसे एक उपयुक्त 3 × m × n तालिका समस्या में एम्बेड करें जैसा कि ऊपर उल्लिखित सार्वभौमिकता द्वारा सक्षम किया गया है। अब के सन्निकटन के निम्नलिखित पदानुक्रम को लागू करें। इस पदानुक्रम के स्तर k पर, अधिकतम k पर केवल उन प्रकार के तत्वों को शामिल करने का सबसेट होने दें; 3 × m × n तालिका समस्या में अंतर्निहित पूर्णांक प्रोग्रामिंग समस्या के लिए यथासंभव संभव बिंदु प्राप्त करने के लिए यथासंभव लंबे समय तक पुनरावृत्ति एल्गोरिथ्म में इस सन्निकटन का उपयोग करें; यदि इस बिंदु का वस्तुनिष्ठ कार्य मूल्य संतोषजनक है (मान लीजिए, रैखिक प्रोग्रामिंग छूट के मूल्य की तुलना में), तो इस बिंदु का उपयोग करें; अन्यथा k को बढ़ाएं और पदानुक्रम के अगले स्तर पर आगे बढ़ें। यह दिखाया जा सकता है कि किसी भी निश्चित स्तर k के लिए, ग्रेवर आधार के सन्निकटन में बहुपद कार्डिनलिटी होती है और उसी समय में गणना की जा सकती है। स्थिर पैरामीटर ट्रैक्टेबिलिटीः बहुपद से घन समय जटिलता ऊपर चर्चा किए गए कुछ अनुप्रयोगों को हल करने की समय जटिलता, जैसे कि बहु-आयामी तालिका समस्याएं, बहु-समायोजन प्रवाह समस्याएं और एन-गुना पूर्णांक प्रोग्रामिंग समस्याएं, प्रासंगिक ग्रेवर आधार की कार्डिनलिटी पर हावी हैं, जो आमतौर पर बड़ी डिग्री जी के साथ एक बहुपद है जो सिस्टम की एक उपयुक्त ग्रेवर जटिलता है। एक बहुत तेज एल्गोरिथ्म में प्रस्तुत किया जाता है, जो प्रत्येक पुनरावृत्ति पर प्रणाली की परवाह किए बिना घन समय में स्पष्ट रूप से ग्रेवर आधार का निर्माण किए बिना q सकारात्मक पूर्णांक और g तत्व के साथ x + qg में सबसे अच्छा सुधार पाता है। मानकीकृत जटिलता की शब्दावली में, इसका तात्पर्य है कि ये सभी समस्याएं उपयुक्त रूप से मानकीकृत हैं, और विशेष रूप से l × m × n तालिका समस्याओं को l और m द्वारा मानकीकृत किया गया है, जो निश्चित मानकीकृत हैं। गोर्डन का लेम्मा भी देखें-पूर्णांक मैट्रिक्स के शून्य सेट से संबंधित एक अन्य उपकरण। संदर्भ रैखिक प्रोग्रामिंग