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

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

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

उदाहरण के लिए, 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.