रैखिक प्रोग्रामिंग छूट

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

गणित में, एक मिश्रित पूर्णांक रैखिक प्रोग्रामिंग | (मिश्रित) पूर्णांक रैखिक कार्यक्रम की छूट वह समस्या है जो प्रत्येक चर की अभिन्नता बाधा को दूर करने से उत्पन्न होती है।

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

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

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

$0\leq x_{i}\leq 1.$

परिणामी विश्राम एक रेखीय कार्यक्रम है, इसलिए यह नाम है। यह विश्राम तकनीक (गणित) एक एनपी कठिन अनुकूलन समस्या (पूर्णांक प्रोग्रामिंग) को एक संबंधित समस्या में बदल देती है जो बहुपद समय (रैखिक प्रोग्रामिंग) में हल करने योग्य है; मूल पूर्णांक कार्यक्रम के समाधान के बारे में जानकारी प्राप्त करने के लिए आराम से रैखिक कार्यक्रम के समाधान का उपयोग किया जा सकता है।

उदाहरण

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

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

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

(यानी, केवल निर्दिष्ट सूचक चर मानों की अनुमति है) और, प्रत्येक तत्व के लिए ई_jF के मिलन का,

$\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}}$ (जहां आरआर गोलाई अनुपात है)। यदि इंटीग्रेलिटी गैप आईजी के साथ एक उदाहरण है, तो प्रत्येक राउंडिंग रणनीति वापस आ जाएगी, उस उदाहरण पर, कम से कम आकार का एक गोल समाधान $M_{\text{int}}=IG\cdot M_{\text{frac}}$. इसलिए अनिवार्य रूप से $RR\geq IG$. राउंडिंग अनुपात आरआर सन्निकटन अनुपात पर केवल एक ऊपरी सीमा है, इसलिए सिद्धांत रूप में वास्तविक सन्निकटन अनुपात आईजी से कम हो सकता है, लेकिन यह साबित करना कठिन हो सकता है। व्यवहार में, एक बड़े IG का आमतौर पर मतलब होता है कि रैखिक प्रोग्रामिंग छूट में सन्निकटन अनुपात खराब हो सकता है, और उस समस्या के लिए अन्य सन्निकटन योजनाओं की तलाश करना बेहतर हो सकता है।

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

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

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

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

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

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

हालांकि इस प्रकार के एल्गोरिदम के प्रदर्शन पर सैद्धांतिक सीमा को साबित करना मुश्किल है, वे व्यवहार में बहुत प्रभावी हो सकते हैं।

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

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

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

इस पद्धति द्वारा उपयोग किए जाने वाले कटौती को खोजने के लिए समस्या-विशिष्ट विधियों की आवश्यकता होती है। काटने वाले विमानों को ढूंढना विशेष रूप से वांछनीय है जो पूर्णांक समाधानों के उत्तल पतवार के पहलू बनाते हैं, क्योंकि ये विमान वे हैं जो समाधान स्थान को सबसे अधिक कसते हैं; इस प्रकार का एक कटिंग प्लेन हमेशा मौजूद होता है जो किसी भी आंशिक समाधान को पूर्णांक समाधान से अलग करता है। पॉलीहेड्रल कॉम्बिनेटरिक्स के ढांचे के तहत विभिन्न प्रकार के दहनशील अनुकूलन समस्याओं के लिए इन पहलुओं को खोजने के तरीकों पर बहुत अधिक शोध किया गया है। (Aardal & Weismantel 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.