रैखिक प्रोग्रामिंग छूट: Difference between revisions

Latest revision as of 19:29, 17 May 2023

ए (सामान्य) पूर्णांक फलन और इसकी एलपी-छूट

गणित में, मिश्रित पूर्णांक रैखिक प्रोग्रामिंग में कमी प्रॉब्लम के रूप में है, जो प्रत्येक चर के अभिन्नता प्रतिबंध को हटाकर उत्पन्न होती है।

उदाहरण के लिए, 0-1 पूर्णांक फलन में सभी बाधाएँ प्रपत्र के रूप में होती हैं

x_{i}\in \{0,1\}

.

इसके अतिरिक्त मूल पूर्णांक फलन की छूट रैखिक बाधाओं के संग्रह का उपयोग करती है

0\leq x_{i}\leq 1.

परिणामी रिलैक्सेशन एक रेखीय फलन के रूप में होता है, इसलिए इसका यह नाम है। यह रिलैक्सेशन प्रोद्योगिकीय संबंधित प्रॉब्लम में एनपी हार्ड ऑप्टिमाइज़ेशन प्रॉब्लम पूर्णांक प्रोग्रामिंग को रूपान्तरित करती है, जो कि बहुपद के समय रैखिक प्रोग्रामिंग में समझने योग्य होती है और इस प्रकार सुगम रैखिक फलन के समाधान का प्रयोग मूल पूर्णांक प्रोग्राम के समाधान के बारे में जानकारी प्राप्त करने के लिए किया जा सकता है।

उदाहरण

समुच्चय कवर प्रॉब्लम पर विचार करते है, जिसके रेखीय प्रोग्रामिंग रिलैक्सेशन पर सबसे पहले विचार किया गया था जिसे लोवाज़ (1975) ने पहले माना था। इस प्रॉब्लम में, एक इनपुट के रूप में समुच्चय F = {S₀, S₁, ...}; (गणित) के समूह को दिया जाता है इस कार्य को जितना संभव हो उतना कम समुच्चय के साथ एक उप समूह के रूप में ढूंढना होता है और इस प्रकार एफ के रूप में एक ही संघ (समुच्चय सिद्धांत) के रूप में होने चाहिए।

इसे 0-1 पूर्णांक फलन के रूप में तैयार करने के लिए संकेतक चर x_i के रूप में बनाएं जाते है और प्रत्येक समुच्चय के लिएS_i, जिसका मान 1 होता है जब S_i चुने हुए उपसमूह से संबंधित है और 0 जब ऐसा नहीं होता है। फिर बाधाओं को संतुष्ट करने वाले संकेतक चर के मूल्यों के असाइनमेंट द्वारा एक वैध कवर का वर्णन इस प्रकार से किया जा सकता है।

\textstyle x_{i}\in \{0,1\}

अर्थात, केवल निर्दिष्ट सूचक चर मानों की अनुमति होती है और प्रत्येक तत्व के लिए F के संघ e_j के रूप में होता है।

\textstyle \sum _{\{i\mid e_{j}\in S_{i}\}}x_{i}\geq 1

अर्थात, प्रत्येक तत्व को कवर किया गया है। न्यूनतम समुच्चय कवर इन बाधाओं को संतुष्ट करने वाले संकेतक चर के असाइनमेंट से मेल खाता है और रैखिक वस्तुनिष्ठ फलन को कम करता है

\textstyle \min \sum _{i}x_{i}.

रैखिक प्रोग्रामिंग प्रॉब्लम में छूट एक भिन्नात्मक कवर को वर्णित करता है जिसमें इनपुट समुच्चय का सेट भार नियत किया जाता है और इस प्रकार जैसे कि प्रत्येक अवयव युक्त समुच्चय का कुल वजन कम से कम होता है और सभी समुच्चयो का कुल वजन कम किया जाता है।

समुच्चय कवर प्रॉब्लम के विशिष्ट उदाहरण के रूप में, F = {{a, b}, {b, c}, {a, c}} पर विचार करते है और इस प्रकार तीन इष्टतम समुच्चय कवर होते हैं, जिनमें से प्रत्येक में दिए गए तीन समुच्चयो में से दो सम्मलित रूप में होते है। इस प्रकार, संबंधित 0-1 पूर्णांक फलन के उद्देश्य फलन का इष्टतम मूल्य 2 है और इस प्रकार इष्टतम कवर में समुच्चय की संख्या चूँकि भिन्नात्मक समाधान के रूप में होती है, जिसमें प्रत्येक समुच्चय को 1/2 भार दिया गया है और जिसके लिए उद्देश्य फलन का कुल मान 3/2 होता है। इस प्रकार इस उदाहरण में, रैखिक प्रोग्रामिंग रिलैक्सेशन का मूल्य असंबद्ध 0–1 पूर्णांक फलन से भिन्न होता है।

रिलैक्स्ड और मूल फलनो की समाधान गुणवत्ता

किसी भी मानक रैखिक प्रोग्रामिंग प्रोद्योगिकीय का उपयोग करके पूर्णांक फलन की रैखिक प्रोग्रामिंग छूट को हल किया जा सकता है। यदि रैखिक फलन के इष्टतम समाधान में सभी चर या तो 0 या 1 होते हैं, तो यह मूल पूर्णांक फलन का इष्टतम समाधान के रूप में होता है। चूंकि, यह सामान्यतः सच नहीं है कुछ विशेष स्थितियों को छोड़कर जैसे,पूरी तरह से यूनिमॉड्यूलर आव्यूह विनिर्देशों के साथ समस्याएं होती है।

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

ऊपर वर्णित समुच्चय कवर प्रॉब्लम के उदाहरण में, जिसमें रिलैक्सेशन का इष्टतम समाधान मान 3/2 के रूप में होता है, हम यह निष्कर्ष निकाल सकते हैं कि असंबद्ध पूर्णांक फलन का इष्टतम समाधान मान कम से कम उतना ही बड़ा होता है। चूंकि निर्धारित कवर प्रॉब्लम के मान, उप-कुल में चुने गए समुच्चय की संख्या के पूर्णांक मान होते हैं और इस प्रकार इष्टतम समाधान गुणवत्ता कम से कम अगली बड़ी पूर्णांक संख्या 2 जितनी बड़ी होनी चाहिए। इस प्रकार इस उदाहरण में असंबद्ध प्रॉब्लम से भिन्न मूल्य होने के अतिरिक्त रैखिक प्रोग्रामिंग छूट हमें मूल प्रॉब्लम के समाधान की गुणवत्ता पर एक कम निम्नतर सीमा प्रदान करती है।

सन्निकटन और अभिन्नता अंतर

रैखिक प्रोग्रामिंग छूट कठिन अनुकूलन समस्याओं के लिए सन्निकटन कलन विधि डिजाइन करने के लिए एक मानक प्रोद्योगिकीय के रूप में है। इस अनुप्रयोग में, महत्वपूर्ण अवधारणा अभिन्नता अंतर होता है, जो पूर्णांक फलन की समाधान गुणवत्ता और इसकी छूट के बीच अधिकतम अनुपात के रूप में होता है और इस प्रकार न्यूनतम प्रॉब्लम के उदाहरण में यदि वास्तविक न्यूनतम पूर्णांक प्रॉब्लम का न्यूनतम $M_{\text{int}}$ है और रिलैक्स्ड से न्यूनतम रैखिक प्रोग्रामिंग छूट का न्यूनतम $M_{\text{frac}}$ है, तो उस उदाहरण का समाकलन अतर इस रूप में $IG={\frac {M_{\text{int}}}{M_{\text{frac}}}}$ होगा और एक अधिकतमकरण प्रॉब्लम में अंश उलटा होता है। पूर्णात्मकता अतर अधिकांशता कम से कम 1 होता है। उदाहरण में, F = {{a, b}, {b, c}, {a, c}} का समाकलन अतर 4/3 के रूप में दिखाता है।

सामान्यतः , समाकलन अतर सन्निकटन कलन विधि के सन्निकटन अनुपात में बदल जाता है। ऐसा इसलिए है क्योंकि एक सन्निकटन कलन विधि कुछ घूर्णन रणनीति पर निर्भर करता है जो आकार के हर रिलैक्स्ड समाधान के लिए $M_{\text{frac}}$ के रूप में होता है और अधिकतम आकार का पूर्णांक समाधान $RR\cdot M_{\text{frac}}$ के रूप में होता है, जहां आरआर गोलाई अनुपात है। यदि समाकलन अतर IG के साथ उदाहरण है, तो प्रत्येक घूर्णन रणनीति कम से कम आकार का गोल समाधान $M_{\text{int}}=IG\cdot M_{\text{frac}}$ .के रूप में वापस आ जाएगी इसलिए अनिवार्य रूप से $RR\geq IG$ . घूर्णन अनुपात आरआर सन्निकटन अनुपात पर केवल ऊपरी परिबद्ध होता है, इसलिए सिद्धांत रूप में वास्तविक सन्निकटन अनुपात आईजी से कम हो सकता है, लेकिन यह सिद्ध करना कठिन हो सकता है। इस प्रकार व्यवहार में, एक बड़े IG का सामान्यतः तात्पर्य है कि रैखिक प्रोग्रामिंग छूट में सन्निकटन अनुपात खराब हो सकता है और उस प्रॉब्लम के लिए अन्य सन्निकटन योजनाओं को देखना बेहतर हो सकता है।

समुच्चय कवर प्रॉब्लम के लिए, लोवाज़ ने सिद्ध किया कि n तत्वों के साथ उदाहरण के लिए अभिन्नता अंतर H_n और nth हार्मोनिक संख्या के रूप में है। इस प्रॉब्लम के लिए रैखिक प्रोग्रामिंग रिलैक्सेशन को यादृच्छिक घूर्णन राघवन और टोम्पसन 1987 की प्रोद्योगिकीय के माध्यम से मूल असंबद्ध समुच्चय के आवरण उदाहरण के एक अनुमानित समाधान में परिवर्तित किया जा सकता है। एक भिन्नात्मक आवरण दिया गया है, जिसमें प्रत्येक समुच्चय S_i वजन w_i है और इस प्रकार यादृच्छिक रूप से प्रत्येक 0–1 सूचक चर x_i के रूप में चुनते है प्रायिकता w_i × (ln n +1) के साथ 1 और 0 अन्य,के रूप में होता है। तब कोई तत्व 1/(e×n) खुले रहने की संभावना से कम है, इसलिए निरंतर संभावना के साथ सभी तत्व के रूप में सम्मलित हैं। इस प्रोद्योगिकीय द्वारा उत्पन्न कवर का कुल आकार उच्च संभावना के साथ, (1+o(1))(ln n)W है, जहां W भिन्नात्मक समाधान का कुल वजन है। इस प्रकार, यह प्रोद्योगिकीय यादृच्छिक कलन विधि सन्निकटन कलन विधि की ओर ले जाती है जो इष्टतम के लघुगणक कारक के भीतर एक समुच्चय कवर ढूंढती है। जैसा यंग (1995) ने दिखाया, इस कलन विधि के यादृच्छिक भाग और रैखिक प्रोग्रामिंग छूट के लिए स्पष्ट समाधान बनाने की आवश्यकता को सशर्त संभावनाओं की विधि का उपयोग करके समाप्त किया जा सकता है, जिससे समुच्चय कवर के लिए एक नियतात्मक ग्रीडी कलन विधि हो जाता है, जो पहले से ही लोवाज़ के लिए जाना जाता है और इस प्रकार बार-बार उस समुच्चय का चयन करता है जो शेष खुले तत्वों की सबसे बड़ी संभावित संख्या को कवर करता है। यह ग्रीडी कलन विधि समुच्चय कवर को उसी H_n के भीतर अनुमानित करता है और लोवाज़ ने समुच्चय कवर के लिए समाकलन अतर के रूप में सिद्ध किया। यह मानने के लिए मजबूत जटिलता-सैद्धांतिक कारण हैं कि कोई बहुपद समय सन्निकटन कलन विधि महत्वपूर्ण रूप से अपेक्षाकृत अधिक सन्निकटन अनुपात (फीज 1998).प्राप्त नहीं कर सकता है।

राघवन, टॉमपसन और यंग द्वारा वर्णित कई अन्य समस्याओं के लिए सन्निकटन कलन विधि विकसित करने के लिए इसी तरह की यादृच्छिक घूर्णन प्रोद्योगिकीय और डेरांडोमाइज्ड सन्निकटन कलन विधि का उपयोग रैखिक प्रोग्रामिंग छूट के संयोजन के साथ किया जा सकता है।

शाखा और यथार्थ समाधान के लिए बाध्य

सन्निकटन में इसके उपयोग के साथ-साथ रैखिक प्रोग्रामिंग कठिन अनुकूलन समस्याओं के सही इष्टतम समाधान की गणना के लिए शाखा और बाध्य कलन विधि में महत्वपूर्ण भूमिका निभाती है।

यदि इष्टतम समाधान में कुछ चर के भिन्नात्मक मान हैं, तो हम एक शाखा और बाउंड प्रकार की प्रक्रिया प्रारंभ कर सकते हैं, जिसमें हम पुनरावर्ती रूप से उप-समस्याओं को हल करते हैं जिसमें कुछ भिन्नात्मक चर के मान शून्य या एक के लिए तय होते हैं। इस प्रकार के कलन विधि के प्रत्येक चरण में मूल 0-1 पूर्णांक प्रोग्राम की एक उप प्रॉब्लम पर विचार करते हैं, जिसमें कुछ चरों को उनके लिए निर्दिष्ट मान दिए गए हैं और इस प्रकार या तो 0 या 1 और शेष चर अभी भी या तो लेने के लिए स्वतंत्र हैं कीमत। उप प्रॉब्लम i में मान लीजिए V_i शेष चर के समुच्चय को निरूपित करता है। यह प्रक्रिया एक उप- प्रॉब्लम पर विचार करके प्रारंभ होती है जिसमें कोई चर मान निर्दिष्ट नहीं किया गया है और जिसमें V₀ मूल प्रॉब्लम के चरों का संपूर्ण समुच्चय है। फिर, प्रत्येक उप प्रॉब्लम i के लिए यह निम्नलिखित चरणों का पालन करता है।

वर्तमान उप- प्रॉब्लम के रैखिक प्रोग्रामिंग छूट के इष्टतम समाधान की गणना करते है। अर्थात्, प्रत्येक चर x_j के लिए V_i, में उस बाधा को प्रतिस्थापित करते हैं जो x_j रिलैक्स्ड की बाधा में 0 या 1 के रूप में हो कि यह अंतराल [0,1] होते है; चूँकि जिन चरों को पहले से ही मान निर्दिष्ट किए जा चुके हैं, उन्हें रिलैक्स्ड नहीं दिया जाता है।
यदि वर्तमान उप- प्रॉब्लम का रिलैक्स्ड समाधान अब तक मिले सर्वोत्तम पूर्णांक समाधान से भी बदतर है, तो पुनरावर्ती खोज की इस शाखा से पीछे हट जाते है।
यदि रिलैक्स्ड से समाधान में सभी चर 0 या 1 पर समुच्चय हैं, तो अब तक मिले सर्वोत्तम पूर्णांक समाधान के विरुद्ध इसका परीक्षण करते है और दोनों में से जो भी समाधान सबसे अच्छा हो, उसे रखते है।
अन्यथा माना x_j कोई भी चर हैं, जो रिलैक्स्ड से समाधान में भिन्नात्मक मान पर समुच्चय हो तो दो उपसमस्याएँ बनाती है, जिसमें x_j 0 पर समुच्चय है और दूसरा जिसमें x_j1 पर समुच्चय है; दोनों उपसमस्याओं में कुछ चरों के मानों के उपस्थित असाइनमेंट अभी भी उपयोग किए जाते हैं, इसलिए शेष चरों का समुच्चय V_i \ {x_j}. बन जाता है, जो दोनों उप-समस्याओं को पुनरावर्ती रूप से खोजते है।

चूंकि इस प्रकार के कलन विधि के प्रदर्शन पर सैद्धांतिक सीमा को सिद्ध करना कठिन है और इस प्रकार वे व्यवहार में बहुत प्रभावी हो सकते हैं।

समतल विधि काटना

दो 0-1 पूर्णांक फलन जो समतुल्य हैं, जिनमें समान वस्तुनिष्ठ फलन और व्यावहारिक समाधान के समान समुच्चय में बहुत भिन्न रैखिक प्रोग्रामिंग छूट हो सकती है, रैखिक प्रोग्रामिंग छूट को उत्तल पॉलीटॉप के रूप में देखा जा सकता है, जिसमें सभी व्यवहार्य समाधान के रूप में सम्मलित होते हैं और व्यवहार्य समाधान और अन्य सभी 0–1 सदिश को भी इसमें सम्मिलित नहीं किया जाता है और यह गुण अनंत रूप से विभिन्न पॉलीटोप्स में पाया जाता है। आदर्श रूप में, कोई व्यवहार्य समाधान के उत्तल पतवार को रिलैक्सेशन के रूप में उपयोग करना चाहिए; इस पॉलीटोप पर रैखिक प्रोग्रामिंग से मूल पूर्णांक प्रोग्राम का सही समाधान स्वतः ही उत्पन्न हो जाता है। चूंकि, सामान्यतः रूप से इस पॉलीटॉप में घातीय रूप से कई (गणित) पहलू होते है और अनेक पहलुओं को तीव्रता से उभारना कठिन होता है। इस प्रकार विशिष्ट छूट जैसे कि पहले चर्चा की गई समुच्चय कवर प्रॉब्लम की छूट पॉलीटॉप बनाती है जिसमें उत्तल पतवार को सख्ती से सम्मलित किया जाता है और इसमें 0–1 सदिश के अतिरिक्त अन्य शीर्ष होते हैं, जो असंतुलित प्रॉब्लम को हल करते हैं।

0-1 पूर्णांक प्रोग्राम को हल करने के लिए कटिंग-तल विधि, पहली बार ट्रैवलिंग सेल्समैन की प्रॉब्लम के लिए डेंटज़िग, फुलकर्सन & एंड जॉनसन (1954) द्वारा प्रारंभ की गई थी और अन्य पूर्णांक फलनो के लिए सामान्यीकृत गमरी (1958), छूट के अनुक्रम को ढूंढकर संभावित छूट की इस बहुलता का लाभ उठाता है जो अंत में एक पूर्णांक समाधान प्राप्त होने तक समाधान स्थान को अधिक मजबूती से बाधित करता है। यह विधि दिए गए प्रोग्राम की किसी भी छूट से प्रारंभ होती है और एक रैखिक प्रोग्रामिंग सॉल्वर का उपयोग करके इष्टतम समाधान ढूंढती है। यदि समाधान सभी चरों के लिए पूर्णांक मान निर्दिष्ट करता है, तो यह असंबद्ध प्रॉब्लम का इष्टतम समाधान के रूप में भी है। अन्यथा, एक अतिरिक्त रैखिक बाधा जो परिणामतः भिन्नक भिन्नात्मक विलयन को पूर्णांक समाधानों के उत्तल पतवार से अलग करता है और इस नई विधि से अधिक कसकर विवश प्रॉब्लम पर दोहराता है।

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

संबंधित शाखा और कट पद्धति में कटाई तल और शाखा तथा बाध्य पद्धति का संयोजन होता है। किसी भी उप- प्रॉब्लम में यह कटिंग तल पद्धति को तब तक चलाता है, जब तक कि कोई और कटिंग तल नहीं मिल जाता है और उसके बाद किसी शेष खंड चर पर शाखाएं न मिल जायें।

यह भी देखें

भिन्नात्मक रंग, ग्राफ रंग की रेखीय प्रोग्रामिंग रिलैक्सेशन के रूप में होता है।
रैंडमाइज्ड घूर्णन, मूल प्रॉब्लम के समाधान से लेकर रिलैक्सेशन तक का समाधान प्राप्त करने के लिए होता है।

संदर्भ

Aardal, Karen; Weismantel, Robert (1997), "Polyhedral combinatorics: An annotated bibliography", Annotated Bibliographies in Combinatorial Optimization (PDF), Wiley.
Agmon, Shmuel (1954), "The relaxation method for linear inequalities", Canadian Journal of Mathematics, 6: 382–392, doi:10.4153/CJM-1954-037-2.
Dantzig, George; Fulkerson, D. R.; Johnson, Selmer (1954), "Solution of a large-scale traveling-salesman problem", Journal of the Operations Research Society of America, 2 (4): 393–410, doi:10.1287/opre.2.4.393.
Feige, Uriel (1998), "A threshold of ln n for approximating set cover", Journal of the ACM, 45 (4): 634–652, CiteSeerX 10.1.1.70.5014, doi:10.1145/285055.285059.
Gomory, Ralph E. (1958), "Outline of an algorithm for integer solutions to linear programs", Bulletin of the American Mathematical Society, 64 (5): 275–279, doi:10.1090/S0002-9904-1958-10224-4.
Lovász, László (1975), "On the ratio of optimal integral and fractional covers", Discrete Mathematics, 13 (4): 383–390, doi:10.1016/0012-365X(75)90058-8.
Motzkin, T. S.; Schoenberg, I. J. (1954), "The relaxation method for linear inequalities", Canadian Journal of Mathematics, 6: 393–404, doi:10.4153/CJM-1954-038-x.
Raghavan, Prabhakar; Thompson, Clark D. (1987), "Randomized rounding: A technique for provably good algorithms and algorithmic proofs", Combinatorica, 7 (4): 365–374, doi:10.1007/BF02579324.
Young, Neal E. (1995), "Randomized rounding without solving the linear program", Proc. 6th ACM-SIAM Symp. Discrete Algorithms (SODA), Soda '95, pp. 170–178, ISBN 9780898713497.

@@ Line 1: / Line 1: @@
-[[File:IP_polytope_with_LP_relaxation.svg|right|thumb|300px|ए (सामान्य) [[पूर्णांक कार्यक्रम]] और इसकी एलपी-छूट]]गणित में, एक [[मिश्रित पूर्णांक रैखिक प्रोग्रामिंग]] | (मिश्रित) पूर्णांक रैखिक कार्यक्रम की छूट वह समस्या है जो प्रत्येक चर की अभिन्नता बाधा को दूर करने से उत्पन्न होती है।
+[[File:IP_polytope_with_LP_relaxation.svg|right|thumb|300px|ए (सामान्य) [[पूर्णांक कार्यक्रम|पूर्णांक]] फलन और इसकी एलपी-छूट]]गणित में, [[मिश्रित पूर्णांक रैखिक प्रोग्रामिंग]] में कमी प्रॉब्लम के रूप में है, जो प्रत्येक चर के अभिन्नता प्रतिबंध को हटाकर उत्पन्न होती है।
-उदाहरण के लिए, 0-1 पूर्णांक कार्यक्रम में, सभी बाधाएँ प्रपत्र की होती हैं
+उदाहरण के लिए, 0-1 पूर्णांक फलन में सभी बाधाएँ प्रपत्र के रूप में होती हैं
 :<math>x_i\in\{0,1\}</math>.
-इसके बजाय मूल पूर्णांक कार्यक्रम की छूट रैखिक बाधाओं के संग्रह का उपयोग करती है
+इसके अतिरिक्त मूल पूर्णांक फलन की छूट रैखिक बाधाओं के संग्रह का उपयोग करती है
 :<math>0 \le x_i \le 1.</math>
-परिणामी विश्राम एक रेखीय कार्यक्रम है, इसलिए यह नाम है। यह [[विश्राम तकनीक (गणित)]] एक [[ एनपी कठिन ]] अनुकूलन समस्या (पूर्णांक प्रोग्रामिंग) को एक संबंधित समस्या में बदल देती है जो बहुपद समय (रैखिक प्रोग्रामिंग) में हल करने योग्य है; मूल पूर्णांक कार्यक्रम के समाधान के बारे में जानकारी प्राप्त करने के लिए आराम से [[रैखिक कार्यक्रम]] के समाधान का उपयोग किया जा सकता है।
+परिणामी रिलैक्सेशन एक रेखीय फलन के रूप में होता है, इसलिए इसका यह नाम है। यह [[विश्राम तकनीक (गणित)|रिलैक्सेशन प्रोद्योगिकीय]] संबंधित प्रॉब्लम में [[ एनपी कठिन |एनपी]] हार्ड ऑप्टिमाइज़ेशन प्रॉब्लम पूर्णांक प्रोग्रामिंग को रूपान्तरित करती है, जो कि बहुपद के समय रैखिक प्रोग्रामिंग में समझने योग्य होती है और इस प्रकार सुगम [[रैखिक कार्यक्रम|रैखिक]] फलन के समाधान का प्रयोग मूल पूर्णांक प्रोग्राम के समाधान के बारे में जानकारी प्राप्त करने के लिए किया जा सकता है।
 == उदाहरण ==
-सेट कवर समस्या पर विचार करें, जिसके लीनियर प्रोग्रामिंग रिलैक्सेशन पर सबसे पहले विचार किया गया था {{harvtxt|Lovász|1975}}. इस समस्या में, एक इनपुट के रूप में समुच्चय (गणित) के एक परिवार F = {S दिया जाता है<sub>0</sub>, एस<sub>1</sub>, ...}; कार्य एक सबफ़ैमिली को ढूंढना है, जितना संभव हो उतना कुछ सेट, एफ के समान [[संघ (सेट सिद्धांत)]] होने के साथ।
+समुच्चय कवर प्रॉब्लम पर विचार करते है, जिसके रेखीय प्रोग्रामिंग रिलैक्सेशन पर सबसे पहले विचार किया गया था जिसे {{harvtxt|लोवाज़|1975}} ने पहले माना था। इस प्रॉब्लम में, एक इनपुट के रूप में समुच्चय ''F'' = {''S''<sub>0</sub>, ''S''<sub>1</sub>, ...}; (गणित) के समूह को दिया जाता है इस कार्य को जितना संभव हो उतना कम समुच्चय के साथ एक उप समूह के रूप में ढूंढना होता है और इस प्रकार एफ के रूप में एक ही [[संघ (सेट सिद्धांत)|संघ (समुच्चय सिद्धांत)]] के रूप में होने चाहिए।
-इसे 0-1 पूर्णांक कार्यक्रम के रूप में तैयार करने के लिए, एक संकेतक चर x बनाएं<sub>i</sub>प्रत्येक सेट के लिए एस<sub>i</sub>, जिसका मान 1 होता है जब S<sub>i</sub>चुने हुए सबफ़ैमिली से संबंधित है और 0 जब ऐसा नहीं होता है। फिर बाधाओं को संतुष्ट करने वाले संकेतक चर के मूल्यों के असाइनमेंट द्वारा एक वैध कवर का वर्णन किया जा सकता है
+इसे 0-1 पूर्णांक फलन के रूप में तैयार करने के लिए संकेतक चर x<sub>i</sub> के रूप में बनाएं जाते है और प्रत्येक समुच्चय के लिएS<sub>i</sub>, जिसका मान 1 होता है जब S<sub>i</sub> चुने हुए उपसमूह से संबंधित है और 0 जब ऐसा नहीं होता है। फिर बाधाओं को संतुष्ट करने वाले संकेतक चर के मूल्यों के असाइनमेंट द्वारा एक वैध कवर का वर्णन इस प्रकार से किया जा सकता है।
 :<math>\textstyle x_i\in\{0,1\}</math>
-(यानी, केवल निर्दिष्ट सूचक चर मानों की अनुमति है) और, प्रत्येक तत्व के लिए ई<sub>j</sub>F के मिलन का,
+अर्थात, केवल निर्दिष्ट सूचक चर मानों की अनुमति होती है और प्रत्येक तत्व के लिए F के संघ ''e<sub>j</sub>'' के रूप में होता है।
 :<math>\textstyle \sum_{\{i\mid e_j\in S_i\}} x_i \ge 1</math>
-(अर्थात, प्रत्येक तत्व को कवर किया गया है)। न्यूनतम सेट कवर इन बाधाओं को संतुष्ट करने वाले संकेतक चर के असाइनमेंट से मेल खाता है और रैखिक उद्देश्य समारोह को कम करता है
+अर्थात, प्रत्येक तत्व को कवर किया गया है। न्यूनतम समुच्चय कवर इन बाधाओं को संतुष्ट करने वाले संकेतक चर के असाइनमेंट से मेल खाता है और रैखिक वस्तुनिष्ठ फलन को कम करता है
 :<math>\textstyle \min \sum_i x_i.</math>
-सेट कवर समस्या की रैखिक प्रोग्रामिंग छूट एक भिन्नात्मक कवर का वर्णन करती है जिसमें इनपुट सेट को वज़न दिया जाता है जैसे कि प्रत्येक तत्व वाले सेट का कुल वजन कम से कम एक होता है और सभी सेटों का कुल वजन कम से कम होता है।
-सेट कवर समस्या के विशिष्ट उदाहरण के रूप में, उदाहरण F = पर विचार करें {{''a'', ''b''}, {''b'', ''c''}, {''a'', ''c''}}. तीन इष्टतम सेट कवर हैं, जिनमें से प्रत्येक में दिए गए तीन सेटों में से दो शामिल हैं। इस प्रकार, संबंधित 0-1 पूर्णांक कार्यक्रम के उद्देश्य समारोह का इष्टतम मूल्य 2 है, इष्टतम कवर में सेट की संख्या। हालाँकि, एक भिन्नात्मक समाधान है जिसमें प्रत्येक सेट को 1/2 भार दिया गया है, और जिसके लिए उद्देश्य फ़ंक्शन का कुल मान 3/2 है। इस प्रकार, इस उदाहरण में, रैखिक प्रोग्रामिंग विश्राम का मूल्य असंबद्ध 0–1 पूर्णांक कार्यक्रम से भिन्न है।
-== आराम से और मूल कार्यक्रमों की समाधान गुणवत्ता ==
-किसी भी मानक रैखिक प्रोग्रामिंग तकनीक का उपयोग करके एक पूर्णांक कार्यक्रम की रैखिक प्रोग्रामिंग छूट को हल किया जा सकता है। यदि रैखिक कार्यक्रम के इष्टतम समाधान में सभी चर या तो 0 या 1 होते हैं, तो यह मूल पूर्णांक कार्यक्रम का इष्टतम समाधान भी होगा। हालांकि, यह आम तौर पर सच नहीं है, कुछ विशेष मामलों को छोड़कर (जैसे,
-पूरी तरह से यूनिमॉड्यूलर मैट्रिक्स विनिर्देशों के साथ समस्याएं।)
-हालांकि, सभी मामलों में, रैखिक कार्यक्रम की समाधान गुणवत्ता कम से कम पूर्णांक कार्यक्रम जितनी अच्छी है, क्योंकि कोई भी पूर्णांक कार्यक्रम समाधान भी एक वैध रैखिक कार्यक्रम समाधान होगा। यही है, एक अधिकतमकरण समस्या में, आराम से कार्यक्रम का मूल्य मूल कार्यक्रम से अधिक या उसके बराबर होता है, जबकि एक न्यूनतम समस्या में जैसे कि सेट कवर समस्या में आराम से कार्यक्रम का मूल्य उससे कम या उसके बराबर होता है। मूल कार्यक्रम। इस प्रकार, विश्राम पूर्णांक कार्यक्रम के समाधान पर एक आशावादी सीमा प्रदान करता है।
+रैखिक प्रोग्रामिंग प्रॉब्लम में छूट एक भिन्नात्मक कवर को वर्णित करता है जिसमें इनपुट समुच्चय का सेट भार नियत किया जाता है और इस प्रकार जैसे कि प्रत्येक अवयव युक्त समुच्चय का कुल वजन कम से कम होता है और सभी समुच्चयो का कुल वजन कम किया जाता है।
-ऊपर वर्णित सेट कवर समस्या के उदाहरण उदाहरण में, जिसमें विश्राम का इष्टतम समाधान मान 3/2 है, हम यह निष्कर्ष निकाल सकते हैं कि असंबद्ध पूर्णांक कार्यक्रम का इष्टतम समाधान मान कम से कम उतना ही बड़ा है। चूंकि सेट कवर समस्या में समाधान मान हैं जो पूर्णांक हैं (सबफ़ैमिली में चुने गए सेट की संख्या), इष्टतम समाधान गुणवत्ता कम से कम अगले बड़े पूर्णांक के रूप में बड़ी होनी चाहिए, 2. इस प्रकार, इस उदाहरण में, एक अलग होने के बावजूद असंबद्ध समस्या से मूल्य, रैखिक प्रोग्रामिंग छूट हमें मूल समस्या के समाधान की गुणवत्ता पर एक कम निचली सीमा प्रदान करती है।
+समुच्चय कवर प्रॉब्लम के विशिष्ट उदाहरण के रूप में, ''F''<nowiki> = {{</nowiki>''a'', ''b''}, {''b'', ''c''}, {''a'', ''c''<nowiki>}} पर विचार करते है और इस प्रकार तीन इष्टतम समुच्चय कवर होते हैं, जिनमें से प्रत्येक में दिए गए तीन समुच्चयो में से दो सम्मलित रूप में होते है। इस प्रकार, संबंधित 0-1 पूर्णांक फलन के उद्देश्य फलन का इष्टतम मूल्य 2 है और इस प्रकार इष्टतम कवर में समुच्चय की संख्या चूँकि भिन्नात्मक समाधान के रूप में होती है, जिसमें प्रत्येक समुच्चय को 1/2 भार दिया गया है और जिसके लिए उद्देश्य फलन का कुल मान 3/2 होता है। इस प्रकार इस उदाहरण में, रैखिक प्रोग्रामिंग रिलैक्सेशन का मूल्य असंबद्ध 0–1 पूर्णांक फलन से भिन्न होता है।</nowiki>
+== रिलैक्स्ड और मूल फलनो की समाधान गुणवत्ता ==
+किसी भी मानक रैखिक प्रोग्रामिंग प्रोद्योगिकीय का उपयोग करके पूर्णांक फलन की रैखिक प्रोग्रामिंग छूट को हल किया जा सकता है। यदि रैखिक फलन के इष्टतम समाधान में सभी चर या तो 0 या 1 होते हैं, तो यह मूल पूर्णांक फलन का इष्टतम समाधान के रूप में होता है। चूंकि, यह सामान्यतः सच नहीं है कुछ विशेष स्थितियों को छोड़कर जैसे,पूरी तरह से यूनिमॉड्यूलर आव्यूह विनिर्देशों के साथ समस्याएं होती है।
+चूंकि, सभी स्थितियों में, रैखिक फलन की समाधान गुणवत्ता कम से कम पूर्णांक फलन जितनी अच्छी होती है, क्योंकि कोई भी पूर्णांक फलन समाधान भी वैध रैखिक फलन समाधान के रूप में होता है। यही एक अधिकतमकरण प्रॉब्लम में रिलैक्स्ड से फलन का मूल्य मूल फलन से अधिक या उसके बराबर होता है, जबकि न्यूनतम प्रॉब्लम में जैसे कि समुच्चय कवर प्रॉब्लम में रिलैक्स्ड से फलन का मूल्य उससे कम या उसके बराबर होता है। मूल फलन इस प्रकार रिलैक्सेशन पूर्णांक फलन के समाधान पर एक आशावादी सीमा प्रदान करता है।
+ऊपर वर्णित समुच्चय कवर प्रॉब्लम के उदाहरण में, जिसमें रिलैक्सेशन का इष्टतम समाधान मान 3/2 के रूप में होता है, हम यह निष्कर्ष निकाल सकते हैं कि असंबद्ध पूर्णांक फलन का इष्टतम समाधान मान कम से कम उतना ही बड़ा होता है। चूंकि निर्धारित कवर प्रॉब्लम के मान, उप-कुल में चुने गए समुच्चय की संख्या के पूर्णांक मान होते हैं और इस प्रकार इष्टतम समाधान गुणवत्ता कम से कम अगली बड़ी पूर्णांक संख्या 2 जितनी बड़ी होनी चाहिए। इस प्रकार इस उदाहरण में असंबद्ध प्रॉब्लम से भिन्न मूल्य होने के अतिरिक्त रैखिक प्रोग्रामिंग छूट हमें मूल प्रॉब्लम के समाधान की गुणवत्ता पर एक कम निम्नतर सीमा प्रदान करती है।
 == सन्निकटन और अभिन्नता अंतर ==
-<!-- this section is linked to from [[Randomized_rounding]], please update that link there if you change the section title here --nealeyoung May 31, 2010 -->
+रैखिक प्रोग्रामिंग छूट कठिन अनुकूलन समस्याओं के लिए सन्निकटन कलन विधि डिजाइन करने के लिए एक मानक प्रोद्योगिकीय के रूप में है। इस अनुप्रयोग में, महत्वपूर्ण अवधारणा अभिन्नता अंतर होता है, जो पूर्णांक फलन की समाधान गुणवत्ता और इसकी छूट के बीच अधिकतम अनुपात के रूप में होता है और इस प्रकार न्यूनतम प्रॉब्लम के उदाहरण में यदि वास्तविक न्यूनतम पूर्णांक प्रॉब्लम का न्यूनतम <math>M_\text{int}</math> है और रिलैक्स्ड से न्यूनतम रैखिक प्रोग्रामिंग छूट का न्यूनतम <math>M_\text{frac}</math> है, तो उस उदाहरण का समाकलन अतर इस रूप में <math>IG = \frac{M_\text{int}}{M_\text{frac}}</math><nowiki>होगा और एक अधिकतमकरण प्रॉब्लम में अंश उलटा होता है। पूर्णात्मकता अतर अधिकांशता कम से कम 1 होता है। उदाहरण में, F = {{</nowiki>''a'', ''b''}, {''b'', ''c''}, {''a'', ''c''<nowiki>}} का समाकलन अतर 4/3 के रूप में दिखाता है।</nowiki>
-रैखिक प्रोग्रामिंग छूट कठिन अनुकूलन समस्याओं के लिए सन्निकटन एल्गोरिदम डिजाइन करने के लिए एक मानक तकनीक है। इस आवेदन में, एक महत्वपूर्ण अवधारणा अभिन्नता अंतर है, पूर्णांक कार्यक्रम की समाधान गुणवत्ता और इसकी छूट के बीच अधिकतम अनुपात। न्यूनीकरण समस्या के एक उदाहरण में, यदि वास्तविक न्यूनतम (पूर्णांक समस्या का न्यूनतम) है <math>M_\text{int}</math>, और आराम से न्यूनतम (रैखिक प्रोग्रामिंग छूट का न्यूनतम) है <math>M_\text{frac}</math>, तो उस उदाहरण का इंटीग्रेलिटी गैप है <math>IG = \frac{M_\text{int}}{M_\text{frac}}</math>. एक अधिकतमकरण समस्या में अंश उलटा होता है। इंटीग्रेलिटी गैप हमेशा कम से कम 1 होता है। #उदाहरण में, उदाहरण F = {{''a'', ''b''}, {''b'', ''c''}, {''a'', ''c''}} 4/3 का इंटीग्रेलिटी गैप दिखाता है।
-आमतौर पर, इंटीग्रेलिटी गैप एक सन्निकटन एल्गोरिथम के [[सन्निकटन अनुपात]] में बदल जाता है। ऐसा इसलिए है क्योंकि एक सन्निकटन एल्गोरिथम कुछ राउंडिंग रणनीति पर निर्भर करता है जो आकार के हर आराम समाधान के लिए पाता है <math>M_\text{frac}</math>, अधिकतम आकार का एक पूर्णांक समाधान <math>RR\cdot M_\text{frac}</math> (जहां आरआर गोलाई अनुपात है)। यदि इंटीग्रेलिटी गैप आईजी के साथ एक उदाहरण है, तो प्रत्येक राउंडिंग रणनीति वापस आ जाएगी, उस उदाहरण पर, कम से कम आकार का एक गोल समाधान <math>M_\text{int} = IG\cdot M_\text{frac}</math>. इसलिए अनिवार्य रूप से <math>RR \geq IG</math>. राउंडिंग अनुपात आरआर सन्निकटन अनुपात पर केवल एक ऊपरी सीमा है, इसलिए सिद्धांत रूप में वास्तविक सन्निकटन अनुपात आईजी से कम हो सकता है, लेकिन यह साबित करना कठिन हो सकता है। व्यवहार में, एक बड़े IG का आमतौर पर मतलब होता है कि रैखिक प्रोग्रामिंग छूट में सन्निकटन अनुपात खराब हो सकता है, और उस समस्या के लिए अन्य सन्निकटन योजनाओं की तलाश करना बेहतर हो सकता है।
+सामान्यतः , समाकलन अतर सन्निकटन कलन विधि के [[सन्निकटन अनुपात]] में बदल जाता है। ऐसा इसलिए है क्योंकि एक सन्निकटन कलन विधि कुछ घूर्णन रणनीति पर निर्भर करता है जो आकार के हर रिलैक्स्ड समाधान के लिए <math>M_\text{frac}</math>के रूप में होता है और अधिकतम आकार का पूर्णांक समाधान <math>RR\cdot M_\text{frac}</math> के रूप में होता है, जहां आरआर गोलाई अनुपात है। यदि समाकलन अतर IG के साथ उदाहरण है, तो प्रत्येक घूर्णन रणनीति कम से कम आकार का गोल समाधान <math>M_\text{int} = IG\cdot M_\text{frac}</math>.के रूप में वापस आ जाएगी इसलिए अनिवार्य रूप से <math>RR \geq IG</math>. घूर्णन अनुपात आरआर सन्निकटन अनुपात पर केवल ऊपरी परिबद्ध होता है, इसलिए सिद्धांत रूप में वास्तविक सन्निकटन अनुपात आईजी से कम हो सकता है, लेकिन यह सिद्ध करना कठिन हो सकता है। इस प्रकार व्यवहार में, एक बड़े IG का सामान्यतः तात्पर्य है कि रैखिक प्रोग्रामिंग छूट में सन्निकटन अनुपात खराब हो सकता है और उस प्रॉब्लम के लिए अन्य सन्निकटन योजनाओं को देखना बेहतर हो सकता है।
-सेट कवर समस्या के लिए, लोवाज़ ने साबित किया कि एन तत्वों के साथ एक उदाहरण के लिए अभिन्नता अंतर एच है<sub>n</sub>, nth [[हार्मोनिक संख्या]]। कोई इस समस्या के लिए रैखिक प्रोग्रामिंग विश्राम को यादृच्छिक राउंडिंग की तकनीक के माध्यम से मूल असंबद्ध सेट कवर उदाहरण के अनुमानित समाधान में बदल सकता है। {{harv|Raghavan|Tompson|1987}}. एक भिन्नात्मक आवरण दिया गया है, जिसमें प्रत्येक सेट S<sub>i</sub>वजन डब्ल्यू है<sub>i</sub>, यादृच्छिक रूप से प्रत्येक 0–1 सूचक चर x का मान चुनें<sub>i</sub>प्रायिकता w के साथ 1 होना<sub>i</sub>× (ln n +1), और 0 अन्यथा। तब कोई तत्व e<sub>j</sub>खुले रहने की संभावना 1/(e×n) से कम है, इसलिए निरंतर संभावना के साथ सभी तत्व शामिल हैं। इस तकनीक द्वारा उत्पन्न कवर का कुल आकार है, उच्च संभावना के साथ, (1+o(1))(ln n)W, जहां W भिन्नात्मक समाधान का कुल वजन है। इस प्रकार, यह तकनीक एक [[यादृच्छिक एल्गोरिदम]] सन्निकटन एल्गोरिदम की ओर ले जाती है जो इष्टतम के लॉगरिदमिक कारक के भीतर एक सेट कवर ढूंढती है। जैसा {{harvtxt|Young|1995}} ने दिखाया, इस एल्गोरिथम के यादृच्छिक भाग और रैखिक प्रोग्रामिंग छूट के लिए एक स्पष्ट समाधान बनाने की आवश्यकता को [[सशर्त संभावनाओं की विधि]] का उपयोग करके समाप्त किया जा सकता है, जिससे सेट कवर के लिए एक नियतात्मक लालची एल्गोरिथम हो जाता है, जो पहले से ही लोवाज़ के लिए जाना जाता है, बार-बार उस सेट का चयन करता है जो शेष खुले तत्वों की सबसे बड़ी संभावित संख्या को कवर करता है। यह [[लालची एल्गोरिदम]] सेट कवर को उसी एच के भीतर अनुमानित करता है<sub>n</sub>कारक है कि लोवाज़ ने सेट कवर के लिए इंटीग्रेलिटी गैप के रूप में साबित किया। यह मानने के लिए मजबूत जटिलता-सैद्धांतिक कारण हैं कि कोई बहुपद समय सन्निकटन एल्गोरिथम महत्वपूर्ण रूप से बेहतर सन्निकटन अनुपात प्राप्त नहीं कर सकता है। {{harv|Feige|1998}}.
+समुच्चय कवर प्रॉब्लम के लिए, लोवाज़ ने सिद्ध किया कि n तत्वों के साथ उदाहरण के लिए अभिन्नता अंतर ''H<sub>n</sub>'' और nth [[हार्मोनिक संख्या]] के रूप में है। इस प्रॉब्लम के लिए रैखिक प्रोग्रामिंग रिलैक्सेशन को यादृच्छिक घूर्णन राघवन और टोम्पसन 1987 की प्रोद्योगिकीय के माध्यम से मूल असंबद्ध समुच्चय के आवरण उदाहरण के एक अनुमानित समाधान में परिवर्तित किया जा सकता है। एक भिन्नात्मक आवरण दिया गया है, जिसमें प्रत्येक समुच्चय S<sub>i</sub> वजन w<sub>i</sub> है और इस प्रकार यादृच्छिक रूप से प्रत्येक 0–1 सूचक चर x<sub>i</sub> के रूप में चुनते है प्रायिकता ''w<sub>i</sub>'' × (ln ''n'' +1) के साथ 1 और 0 अन्य,के रूप में होता है। तब कोई तत्व 1/(''e''×''n'') खुले रहने की संभावना से कम है, इसलिए निरंतर संभावना के साथ सभी तत्व के रूप में सम्मलित हैं। इस प्रोद्योगिकीय द्वारा उत्पन्न कवर का कुल आकार उच्च संभावना के साथ, (1+o(1))(ln n)W है, जहां W भिन्नात्मक समाधान का कुल वजन है। इस प्रकार, यह प्रोद्योगिकीय [[यादृच्छिक एल्गोरिदम|यादृच्छिक]] कलन विधि सन्निकटन कलन विधि की ओर ले जाती है जो इष्टतम के लघुगणक कारक के भीतर एक समुच्चय कवर ढूंढती है। जैसा {{harvtxt|यंग|1995}} ने दिखाया, इस कलन विधि के यादृच्छिक भाग और रैखिक प्रोग्रामिंग छूट के लिए स्पष्ट समाधान बनाने की आवश्यकता को [[सशर्त संभावनाओं की विधि]] का उपयोग करके समाप्त किया जा सकता है, जिससे समुच्चय कवर के लिए एक नियतात्मक ग्रीडी कलन विधि हो जाता है, जो पहले से ही लोवाज़ के लिए जाना जाता है और इस प्रकार बार-बार उस समुच्चय का चयन करता है जो शेष खुले तत्वों की सबसे बड़ी संभावित संख्या को कवर करता है। यह [[लालची एल्गोरिदम|ग्रीडी]] कलन विधि समुच्चय कवर को उसी ''H<sub>n</sub>'' के भीतर अनुमानित करता है और लोवाज़ ने समुच्चय कवर के लिए समाकलन अतर के रूप में सिद्ध किया। यह मानने के लिए मजबूत जटिलता-सैद्धांतिक कारण हैं कि कोई बहुपद समय सन्निकटन कलन विधि महत्वपूर्ण रूप से अपेक्षाकृत अधिक सन्निकटन अनुपात {{harv|फीज|1998}}.प्राप्त नहीं कर सकता है।
-राघवन, टॉमपसन और यंग द्वारा वर्णित कई अन्य समस्याओं के लिए सन्निकटन एल्गोरिदम विकसित करने के लिए इसी तरह की यादृच्छिक राउंडिंग तकनीक, और डेरांडोमाइज्ड सन्निकटन एल्गोरिदम का उपयोग रैखिक प्रोग्रामिंग छूट के संयोजन के साथ किया जा सकता है।
+राघवन, टॉमपसन और यंग द्वारा वर्णित कई अन्य समस्याओं के लिए सन्निकटन कलन विधि विकसित करने के लिए इसी तरह की यादृच्छिक घूर्णन प्रोद्योगिकीय और डेरांडोमाइज्ड सन्निकटन कलन विधि का उपयोग रैखिक प्रोग्रामिंग छूट के संयोजन के साथ किया जा सकता है।
-== शाखा और सटीक समाधान के लिए बाध्य ==
+== शाखा और यथार्थ समाधान के लिए बाध्य ==
-सन्निकटन में इसके उपयोग के साथ-साथ रैखिक प्रोग्रामिंग कठिन अनुकूलन समस्याओं के सही इष्टतम समाधान की गणना के लिए शाखा और बाध्य एल्गोरिदम में महत्वपूर्ण भूमिका निभाती है।
+सन्निकटन में इसके उपयोग के साथ-साथ रैखिक प्रोग्रामिंग कठिन अनुकूलन समस्याओं के सही इष्टतम समाधान की गणना के लिए शाखा और बाध्य कलन विधि में महत्वपूर्ण भूमिका निभाती है।
-यदि इष्टतम समाधान में कुछ चर के भिन्नात्मक मान हैं, तो हम एक शाखा और बाउंड प्रकार की प्रक्रिया शुरू कर सकते हैं, जिसमें हम पुनरावर्ती रूप से उप-समस्याओं को हल करते हैं जिसमें कुछ भिन्नात्मक चर के मान शून्य या एक के लिए तय होते हैं। इस प्रकार के एल्गोरिथम के प्रत्येक चरण में, हम मूल 0-1 पूर्णांक प्रोग्राम की एक उपसमस्या पर विचार करते हैं जिसमें कुछ चरों को उनके लिए निर्दिष्ट मान होते हैं, या तो 0 या 1, और शेष चर अभी भी या तो लेने के लिए स्वतंत्र हैं कीमत। उपसमस्या i में, मान लीजिए V<sub>i</sub>शेष चर के सेट को निरूपित करें। प्रक्रिया एक उप-समस्या पर विचार करके शुरू होती है जिसमें कोई चर मान निर्दिष्ट नहीं किया गया है, और जिसमें V<sub>0</sub>मूल समस्या के चरों का पूरा सेट है। फिर, प्रत्येक उपसमस्या i के लिए, यह निम्न चरणों का पालन करता है।
+यदि इष्टतम समाधान में कुछ चर के भिन्नात्मक मान हैं, तो हम एक शाखा और बाउंड प्रकार की प्रक्रिया प्रारंभ कर सकते हैं, जिसमें हम पुनरावर्ती रूप से उप-समस्याओं को हल करते हैं जिसमें कुछ भिन्नात्मक चर के मान शून्य या एक के लिए तय होते हैं। इस प्रकार के कलन विधि के प्रत्येक चरण में मूल 0-1 पूर्णांक प्रोग्राम की एक उप प्रॉब्लम पर विचार करते हैं, जिसमें कुछ चरों को उनके लिए निर्दिष्ट मान दिए गए हैं और इस प्रकार या तो 0 या 1 और शेष चर अभी भी या तो लेने के लिए स्वतंत्र हैं कीमत। उप प्रॉब्लम i में मान लीजिए V<sub>i</sub> शेष चर के समुच्चय को निरूपित करता है। यह प्रक्रिया एक उप- प्रॉब्लम पर विचार करके प्रारंभ होती है जिसमें कोई चर मान निर्दिष्ट नहीं किया गया है और जिसमें V<sub>0</sub> मूल प्रॉब्लम के चरों का संपूर्ण समुच्चय है। फिर, प्रत्येक उप प्रॉब्लम i के लिए यह निम्नलिखित चरणों का पालन करता है।
-# वर्तमान उप-समस्या के रैखिक प्रोग्रामिंग छूट के इष्टतम समाधान की गणना करें। अर्थात्, प्रत्येक चर x के लिए<sub>j</sub>वी में<sub>i</sub>, हम उस बाधा को प्रतिस्थापित करते हैं जो x<sub>j</sub>आराम की बाधा से 0 या 1 हो कि यह अंतराल [0,1] में हो; हालाँकि, जिन चरों को पहले से ही मान निर्दिष्ट किए जा चुके हैं, उन्हें आराम नहीं दिया जाता है।
+# वर्तमान उप- प्रॉब्लम के रैखिक प्रोग्रामिंग छूट के इष्टतम समाधान की गणना करते है। अर्थात्, प्रत्येक चर ''x<sub>j</sub>'' के लिए ''V<sub>i</sub>'', में उस बाधा को प्रतिस्थापित करते हैं जो x<sub>j</sub> रिलैक्स्ड की बाधा में 0 या 1 के रूप में हो कि यह अंतराल [0,1] होते है; चूँकि जिन चरों को पहले से ही मान निर्दिष्ट किए जा चुके हैं, उन्हें रिलैक्स्ड नहीं दिया जाता है।
-# यदि वर्तमान उप-समस्या का आराम समाधान अब तक मिले सर्वोत्तम पूर्णांक समाधान से भी बदतर है, तो पुनरावर्ती खोज की इस शाखा से पीछे हटें।
+# यदि वर्तमान उप- प्रॉब्लम का रिलैक्स्ड समाधान अब तक मिले सर्वोत्तम पूर्णांक समाधान से भी बदतर है, तो पुनरावर्ती खोज की इस शाखा से पीछे हट जाते है।
-# यदि आराम से समाधान में सभी चर 0 या 1 पर सेट हैं, तो अब तक मिले सर्वोत्तम पूर्णांक समाधान के खिलाफ इसका परीक्षण करें और दोनों में से जो भी समाधान सबसे अच्छा हो, उसे रखें।
+# यदि रिलैक्स्ड से समाधान में सभी चर 0 या 1 पर समुच्चय हैं, तो अब तक मिले सर्वोत्तम पूर्णांक समाधान के विरुद्ध इसका परीक्षण करते है और दोनों में से जो भी समाधान सबसे अच्छा हो, उसे रखते है।
-# अन्यथा, चलो x<sub>j</sub>कोई भी चर हो जो आराम से समाधान में एक भिन्नात्मक मान पर सेट हो। दो उपसमस्याएँ बनाएँ, एक जिसमें x<sub>j</sub>0 पर सेट है और दूसरा जिसमें x<sub>j</sub>1 पर सेट है; दोनों उपसमस्याओं में, कुछ चरों के मानों के मौजूदा असाइनमेंट अभी भी उपयोग किए जाते हैं, इसलिए शेष चरों का सेट V बन जाता है<sub>i</sub>\ {एक्स<sub>j</sub>}. दोनों उप-समस्याओं को पुनरावर्ती रूप से खोजें।
+# अन्यथा माना x<sub>j</sub> कोई भी चर हैं, जो रिलैक्स्ड से समाधान में भिन्नात्मक मान पर समुच्चय हो तो दो उपसमस्याएँ बनाती है, जिसमें x<sub>j</sub> 0 पर समुच्चय है और दूसरा जिसमें x<sub>j</sub>1 पर समुच्चय है; दोनों उपसमस्याओं में कुछ चरों के मानों के उपस्थित असाइनमेंट अभी भी उपयोग किए जाते हैं, इसलिए शेष चरों का समुच्चय ''V<sub>i</sub>'' \ {''x<sub>j</sub>''}. बन जाता है, जो दोनों उप-समस्याओं को पुनरावर्ती रूप से खोजते है।
-हालांकि इस प्रकार के एल्गोरिदम के प्रदर्शन पर सैद्धांतिक सीमा को साबित करना मुश्किल है, वे व्यवहार में बहुत प्रभावी हो सकते हैं।
+चूंकि इस प्रकार के कलन विधि के प्रदर्शन पर सैद्धांतिक सीमा को सिद्ध करना कठिन है और इस प्रकार वे व्यवहार में बहुत प्रभावी हो सकते हैं।
 == समतल विधि काटना ==
-दो 0-1 पूर्णांक कार्यक्रम जो समतुल्य हैं, जिसमें उनका एक ही उद्देश्य फ़ंक्शन और व्यवहार्य समाधानों का एक ही सेट है, में काफी भिन्न रैखिक प्रोग्रामिंग छूट हो सकती है: एक रैखिक प्रोग्रामिंग छूट को ज्यामितीय रूप से देखा जा सकता है, एक [[उत्तल पॉलीटॉप]] के रूप में जिसमें सभी शामिल हैं व्यवहार्य समाधान और अन्य सभी 0–1 वैक्टर को बाहर करता है, और असीम रूप से कई अलग-अलग पॉलीटोप्स में यह गुण होता है। आदर्श रूप से, कोई व्यवहार्य समाधान के उत्तल पतवार को विश्राम के रूप में उपयोग करना चाहेगा; इस पॉलीटोप पर रैखिक प्रोग्रामिंग स्वचालित रूप से मूल पूर्णांक कार्यक्रम का सही समाधान देगी। हालांकि, सामान्य तौर पर, इस पॉलीटॉप में घातीय रूप से कई [[पहलू (गणित)]] होंगे और निर्माण करना मुश्किल होगा। विशिष्ट छूट, जैसे कि पहले चर्चा की गई सेट कवर समस्या की छूट, एक पॉलीटॉप बनाती है जिसमें उत्तल पतवार को सख्ती से शामिल किया जाता है और इसमें 0–1 वैक्टर के अलावा अन्य कोने होते हैं जो असंतुलित समस्या को हल करते हैं।
+दो 0-1 पूर्णांक फलन जो समतुल्य हैं, जिनमें समान वस्तुनिष्ठ फलन और व्यावहारिक समाधान के समान समुच्चय में बहुत भिन्न रैखिक प्रोग्रामिंग छूट हो सकती है, रैखिक प्रोग्रामिंग छूट को [[उत्तल पॉलीटॉप]] के रूप में देखा जा सकता है, जिसमें सभी व्यवहार्य समाधान के रूप में सम्मलित होते हैं और व्यवहार्य समाधान और अन्य सभी 0–1 सदिश को भी इसमें सम्मिलित नहीं किया जाता है और यह गुण अनंत रूप से विभिन्न पॉलीटोप्स में पाया जाता है। आदर्श रूप में, कोई व्यवहार्य समाधान के उत्तल पतवार को रिलैक्सेशन के रूप में उपयोग करना चाहिए; इस पॉलीटोप पर रैखिक प्रोग्रामिंग से मूल पूर्णांक प्रोग्राम का सही समाधान स्वतः ही उत्पन्न हो जाता है। चूंकि, सामान्यतः रूप से इस पॉलीटॉप में घातीय रूप से कई [[पहलू (गणित)|(गणित) पहलू]] होते है और अनेक पहलुओं को तीव्रता से उभारना कठिन होता है। इस प्रकार विशिष्ट छूट जैसे कि पहले चर्चा की गई समुच्चय कवर प्रॉब्लम की छूट पॉलीटॉप बनाती है जिसमें उत्तल पतवार को सख्ती से सम्मलित किया जाता है और इसमें 0–1 सदिश के अतिरिक्त अन्य शीर्ष होते हैं, जो असंतुलित प्रॉब्लम को हल करते हैं।
--1 पूर्णांक प्रोग्राम को हल करने के लिए [[कटिंग-प्लेन विधि]], पहली बार [[ट्रैवलिंग सेल्समैन की समस्या]] के लिए किसके द्वारा शुरू की गई थी {{harvtxt|Dantzig|Fulkerson|Johnson|1954}} और द्वारा अन्य पूर्णांक कार्यक्रमों के लिए सामान्यीकृत {{harvtxt|Gomory|1958}}, छूट के अनुक्रम को ढूंढकर संभावित छूट की इस बहुलता का लाभ उठाता है जो अंत में एक पूर्णांक समाधान प्राप्त होने तक समाधान स्थान को अधिक मजबूती से बाधित करता है। यह विधि दिए गए प्रोग्राम की किसी भी छूट से शुरू होती है, और एक रैखिक प्रोग्रामिंग सॉल्वर का उपयोग करके इष्टतम समाधान ढूंढती है। यदि समाधान सभी चरों के लिए पूर्णांक मान निर्दिष्ट करता है, तो यह असंबद्ध समस्या का इष्टतम समाधान भी है। अन्यथा, एक अतिरिक्त रैखिक बाधा (एक काटने वाला विमान या कट) पाया जाता है जो परिणामी भिन्नात्मक समाधान को पूर्णांक समाधानों के उत्तल पतवार से अलग करता है, और विधि इस नई अधिक कसकर विवश समस्या पर दोहराती है।
+-1 पूर्णांक प्रोग्राम को हल करने के लिए [[कटिंग-प्लेन विधि|कटिंग-तल विधि]], पहली बार [[ट्रैवलिंग सेल्समैन की समस्या|ट्रैवलिंग सेल्समैन की]] प्रॉब्लम के लिए {{harvtxt|डेंटज़िग|फुलकर्सन| एंड जॉनसन|1954}} द्वारा प्रारंभ की गई थी और अन्य पूर्णांक फलनो के लिए सामान्यीकृत {{harvtxt|गमरी|1958}}, छूट के अनुक्रम को ढूंढकर संभावित छूट की इस बहुलता का लाभ उठाता है जो अंत में एक पूर्णांक समाधान प्राप्त होने तक समाधान स्थान को अधिक मजबूती से बाधित करता है। यह विधि दिए गए प्रोग्राम की किसी भी छूट से प्रारंभ होती है और एक रैखिक प्रोग्रामिंग सॉल्वर का उपयोग करके इष्टतम समाधान ढूंढती है। यदि समाधान सभी चरों के लिए पूर्णांक मान निर्दिष्ट करता है, तो यह असंबद्ध प्रॉब्लम का इष्टतम समाधान के रूप में भी है। अन्यथा, एक अतिरिक्त रैखिक बाधा जो परिणामतः भिन्नक भिन्नात्मक विलयन को पूर्णांक समाधानों के उत्तल पतवार से अलग करता है और इस नई विधि से अधिक कसकर विवश प्रॉब्लम पर दोहराता है।
-इस पद्धति द्वारा उपयोग किए जाने वाले कटौती को खोजने के लिए समस्या-विशिष्ट विधियों की आवश्यकता होती है। काटने वाले विमानों को ढूंढना विशेष रूप से वांछनीय है जो पूर्णांक समाधानों के उत्तल पतवार के पहलू बनाते हैं, क्योंकि ये विमान वे हैं जो समाधान स्थान को सबसे अधिक कसते हैं; इस प्रकार का एक कटिंग प्लेन हमेशा मौजूद होता है जो किसी भी आंशिक समाधान को पूर्णांक समाधान से अलग करता है। [[पॉलीहेड्रल कॉम्बिनेटरिक्स]] के ढांचे के तहत विभिन्न प्रकार के दहनशील अनुकूलन समस्याओं के लिए इन पहलुओं को खोजने के तरीकों पर बहुत अधिक शोध किया गया है। {{harv|Aardal|Weismantel|1997}}.
+इस पद्धति द्वारा उपयोग किए जाने वाले कटौती को खोजने के लिए समस्या-विशिष्ट विधियों की आवश्यकता होती है। यह विशेष रूप से वांछनीय है कि पूर्णांक समाधानों के उन्नतोदर तल के आयाम वाले स्तरों को ज्ञात करते है, क्योंकि ये स्तर ऐसे हैं, जो समाधान स्थान को सबसे अधिक कसते हैं इस प्रकार का एक कटिंग तल अधिकांशता उपस्थित होता है जो किसी भी भिन्नात्मक समाधान को पूर्णांक समाधान से अलग करता है। [[पॉलीहेड्रल कॉम्बिनेटरिक्स]] आर्डल और वीइस्मैन्टल 1997 के फ्रेमवर्क के अनुसार विभिन्न प्रकार के दहनशील अनुकूलन समस्याओं के लिए इन पहलुओं को खोजने की विधियों पर बहुत अनुसंधान किया गया है।
-संबंधित [[शाखा और कट]] विधि काटने के विमान और शाखा और बाध्य विधियों को जोड़ती है। किसी भी उप-समस्या में, यह कटिंग प्लेन विधि को तब तक चलाता है जब तक कि कोई और कटिंग प्लेन नहीं मिल जाता है, और फिर शेष भिन्नात्मक चरों में से एक पर शाखाएं।
+संबंधित [[शाखा और कट]] पद्धति में कटाई तल और शाखा तथा बाध्य पद्धति का संयोजन होता है। किसी भी उप- प्रॉब्लम में यह कटिंग तल पद्धति को तब तक चलाता है, जब तक कि कोई और कटिंग तल नहीं मिल जाता है और उसके बाद किसी शेष खंड चर पर शाखाएं न मिल जायें।
 == यह भी देखें ==
-* [[ आंशिक रंग ]], [[ ग्राफ रंग ]] की एक लीनियर प्रोग्रामिंग रिलैक्सेशन।
+* [[ आंशिक रंग | भिन्नात्मक रंग]], [[ ग्राफ रंग |ग्राफ रंग]] की रेखीय प्रोग्रामिंग रिलैक्सेशन के रूप में होता है।
-* रैंडमाइज्ड राउंडिंग, मूल समस्या के समाधान से लेकर विश्राम तक का समाधान प्राप्त करने के लिए।
+* रैंडमाइज्ड घूर्णन, मूल प्रॉब्लम के समाधान से लेकर रिलैक्सेशन तक का समाधान प्राप्त करने के लिए होता है।
 ==संदर्भ==
@@ Line 75: / Line 76: @@
 * {{citation | title= Randomized rounding: A technique for provably good algorithms and algorithmic proofs|first1=Prabhakar|last1=Raghavan|first2=Clark D. |last2=Thompson|journal=Combinatorica|volume=7|issue=4|year=1987|pages=365–374|doi=10.1007/BF02579324}}.
 * {{citation | contribution = Randomized rounding without solving the linear program | first = Neal E. | last = Young | title = Proc. 6th ACM-SIAM Symp. Discrete Algorithms (SODA) | year = 1995 | url = http://portal.acm.org/citation.cfm?id=313689 | pages = 170–178| isbn = 9780898713497 | series = Soda '95 }}.
-[[Category: रैखिक प्रोग्रामिंग]] [[Category: संयुक्त अनुकूलन]] [[Category: पॉलीहेड्रल कॉम्बिनेटरिक्स]] [[Category: आराम (सन्निकटन)]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 06/05/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Templates Vigyan Ready]]
+[[Category:आराम (सन्निकटन)]]
+[[Category:पॉलीहेड्रल कॉम्बिनेटरिक्स]]
+[[Category:रैखिक प्रोग्रामिंग]]
+[[Category:संयुक्त अनुकूलन]]

Anonymous

Search

रैखिक प्रोग्रामिंग छूट: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 19:29, 17 May 2023

Contents

उदाहरण

रिलैक्स्ड और मूल फलनो की समाधान गुणवत्ता

सन्निकटन और अभिन्नता अंतर

शाखा और यथार्थ समाधान के लिए बाध्य

समतल विधि काटना

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

रैखिक प्रोग्रामिंग छूट: Difference between revisions

Latest revision as of 19:29, 17 May 2023

उदाहरण

रिलैक्स्ड और मूल फलनो की समाधान गुणवत्ता

सन्निकटन और अभिन्नता अंतर

शाखा और यथार्थ समाधान के लिए बाध्य

समतल विधि काटना

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories