Configuration linear program
विन्यास रैखिक कार्यक्रम (विन्यास-एल. पी.) एक रैखिक प्रोग्रामिंग तकनीक है जिसका उपयोग संयोजन अनुकूलन समस्याओं को हल करने के लिए किया जाता है। इसे स्टॉक में कटौती की समस्या के संदर्भ में पेश किया गया था। बाद में, इसे बिन पैकिंग और नौकरी के समय निर्धारण की समस्याओं पर लागू किया गया है। विन्यास-एल. पी. में, प्रत्येक संभावित विन्यास के लिए एक चर होता है-वस्तुओं का प्रत्येक संभावित बहु-समूह जो एक ही बिन में फिट हो सकता है (इन विन्यासों को पैटर्न के रूप में भी जाना जाता है)। आमतौर पर, कॉन्फ़िगरेशन की संख्या समस्या के आकार में घातीय होती है, लेकिन कुछ मामलों में कॉन्फ़िगरेशन की केवल एक बहुपद संख्या का उपयोग करके अनुमानित समाधान प्राप्त करना संभव है। बिन पैकिंग में अभिन्न एल. पी. बिन पैकिंग समस्या में, विभिन्न आकारों वाले एन आइटम होते हैं। लक्ष्य वस्तुओं को कम से कम डिब्बे में पैक करना है, जहां प्रत्येक डिब्बे में अधिकतम बी हो सकता है। एक व्यवहार्य विन्यास अधिकतम बी के योग के साथ आकारों का एक समूह है। उदाहरण के लिएः मान लीजिए कि वस्तु का आकार 3,3,3,3,3,4,4,4,4,4, और B = 12 है। फिर संभावित विन्यास हैंः 3333; 333; 33,334,344; 4,44,444। अगर हमारे पास आकार 3 की केवल तीन वस्तुएँ होतीं, तो हम 3333 विन्यास का उपयोग नहीं कर सकते थे। एस द्वारा विभिन्न आकारों के समूह (और उनकी संख्या) को निरूपित करें। सी द्वारा विभिन्न विन्यासों के समूह (और उनकी संख्या) को निरूपित करें। एस में प्रत्येक आकार एस और सी में विन्यास सी के लिए, दर्शाते हैंः एनएस-आकार एस की वस्तुओं की संख्या. के रूप में, सी-विन्यास सी में आकार एस की घटनाओं की संख्या. एक्ससी-विन्यास सी के साथ डिब्बे की संख्या को दर्शाने वाला एक चर। फिर, बिन-पैकिंग का विन्यास एलपी हैः एस में सभी एस के लिए (-आकार एस के सभी एनएस आइटम पैक किए जाते हैं)। सी में सभी सी के लिए (-कुल मिलाकर अधिकतम एन डिब्बे हैं, इसलिए प्रत्येक व्यक्तिगत विन्यास के अधिकतम एन)। विन्यास एल. पी. एक पूर्णांक रैखिक कार्यक्रम है, इसलिए सामान्य रूप से यह एन. पी.-हार्ड है। इसके अलावा, समस्या भी आम तौर पर बहुत बड़ी होती हैः इसमें सी चर और एस बाधाएं होती हैं। यदि सबसे छोटी वस्तु का आकार eB है (कुछ अंश e के लिए (0,1)), तो प्रत्येक बिन में 1/e आइटम तक हो सकते हैं, इसलिए कॉन्फ़िगरेशन की संख्या C ~ S1/e, जो बहुत बड़ी हो सकती है यदि e छोटा है (यदि e को एक स्थिरांक माना जाता है, तो पूर्णांक LP को संपूर्ण खोज द्वारा हल किया जा सकता हैः अधिकतम S1/e कॉन्फ़िगरेशन हैं, और प्रत्येक कॉन्फ़िगरेशन के लिए अधिकतम n संभावित मान हैं, इसलिए जांच करने के लिए अधिकांश संयोजन हैं। प्रत्येक संयोजन के लिए, हमें एस बाधाओं की जांच करनी होगी, इसलिए रन-टाइम है, जो एन में बहुपद है जब एस, ई स्थिर हैं)। हालाँकि, यह आईएलपी कई सन्निकटन एल्गोरिदम के लिए एक आधार के रूप में कार्य करता है। इन एल्गोरिदम का मुख्य विचार मूल उदाहरण को एक नए उदाहरण में कम करना है जिसमें S छोटा है और e बड़ा है, इसलिए C अपेक्षाकृत छोटा है। फिर, आई. एल. पी. को या तो पूरी खोज (यदि एस, सी पर्याप्त रूप से छोटे हैं), या इसे एक आंशिक एल. पी. में शिथिल करके हल किया जा सकता है। भिन्नात्मक एल. पी. बिन-पैकिंग का भिन्नात्मक विन्यास एल. पी. यह उपरोक्त आई. एल. पी. की रैखिक प्रोग्रामिंग छूट है। यह अंतिम बाधा को बाधा से बदल देता है। दूसरे शब्दों में, प्रत्येक विन्यास का उपयोग आंशिक संख्या में किया जा सकता है। छूट सबसे पहले गिलमोर और गोमोरी द्वारा प्रस्तुत की गई थी, और इसे अक्सर गिलमोर-गोमोरी रैखिक कार्यक्रम कहा जाता है। उदाहरण के लिएः मान लीजिए कि आकार 3 की 31 वस्तुएँ और आकार 4 की 7 वस्तुएँ हैं, और बिन-आकार 10 है। विन्यास इस प्रकार हैंः 4,44,34,334,33,333। बाधाएँ हैं [0,0,1,2,1,2,3] * x = 31 और [1,2,1,1,0,0,0] * x = 7। भिन्नात्मक एल. पी. का एक इष्टतम समाधान है [0,0,0,7,0,0,17/3] अर्थात्ः विन्यास 334 के 7 डिब्बे और विन्यास 333 के 17/3 डिब्बे हैं। ध्यान दें कि केवल दो अलग-अलग विन्यासों की आवश्यकता है। संक्षेप में, भिन्नात्मक एल. पी. को इस प्रकार लिखा जा सकता हैः जहाँ 1 आकार सी का सदिश (1,, 1) है, ए एक एस-बाय-सी मैट्रिक्स है जिसमें प्रत्येक स्तंभ एक एकल विन्यास का प्रतिनिधित्व करता है, और एन सदिश (एन1,, एन. एस.) है। भिन्नात्मक एल. पी. को हल करना बिना किसी समाकलन बाधाओं के एक रैखिक कार्यक्रम को चर और बाधाओं की संख्या में समय बहुपद में हल किया जा सकता है। समस्या यह है कि भिन्नात्मक विन्यास एल. पी. में चरों की संख्या संभावित विन्यासों की संख्या के बराबर है, जो बहुत बड़ी हो सकती है। करमरकर और कार्प एक एल्गोरिथ्म प्रस्तुत करते हैं जो इस समस्या को दूर करता है। सबसे पहले, वे भिन्नात्मक एल. पी. के दोहरे रैखिक कार्यक्रम का निर्माण करते हैंः. इसमें एस चर y1,., yS और C बाधाएं होती हैंः प्रत्येक विन्यास c के लिए, एक बाधा होती है, जहां ए का स्तंभ विन्यास c का प्रतिनिधित्व करता है। प्रत्येक आकार s के लिए, हमें एक गैर-नकारात्मक मूल्य ys निर्धारित करना चाहिए। हमारा लाभ सभी वस्तुओं की कुल कीमत है। हम इन बाधाओं के अधीन लाभ को अधिकतम करना चाहते हैं कि प्रत्येक विन्यास में वस्तुओं की कुल कीमत अधिकतम 1 हो। दूसरा, वे दीर्घवृत्त विधि का एक प्रकार लागू करते हैं, जिसे सभी बाधाओं को सूचीबद्ध करने की आवश्यकता नहीं है-इसे केवल एक पृथक्करण दैवज्ञ की आवश्यकता है। एक पृथक्करण ऑरेकल एक एल्गोरिथ्म है जो, एक वेक्टर y को देखते हुए, या तो यह दावा करता है कि यह संभव है, या एक बाधा पाता है जिसका यह उल्लंघन करता है। दोहरे एल. पी. के लिए पृथक्करण दैवज्ञ को नापसैक समस्या को आकार एस और मान वाई के साथ हल करके लागू किया जा सकता हैः यदि नापसैक समस्या के इष्टतम समाधान का कुल मूल्य अधिकतम 1 है, तो वाई संभव है; यदि यह 1 से बड़ा है, तो वाई संभव नहीं है, और नापसैक समस्या का इष्टतम समाधान एक ऐसे विन्यास की पहचान करता है जिसके लिए बाधा का उल्लंघन किया जाता है। तीसरा, वे दिखाते हैं कि, नैप्सैक समस्या के एक अनुमानित समाधान के साथ, कोई भी दोहरे एल. पी. का एक अनुमानित समाधान प्राप्त कर सकता है, और इससे, प्राथमिक एल. पी. का एक अनुमानित समाधान; करमरकर-कार्प बिन पैकिंग एल्गोरिदम देखें। कुल मिलाकर, किसी भी सहिष्णुता कारक एच के लिए, अधिकतम एलओपीटी (आई) + एच पर लागत का एक बुनियादी व्यवहार्य समाधान मिलता है, और समय पर चलता हैः, जहां एस विभिन्न आकारों की संख्या है, एन विभिन्न वस्तुओं की संख्या है, और सबसे छोटी वस्तु का आकार ईबी है। विशेष रूप से, यदि ई ≤1/एन और एच = 1 है, तो एल्गोरिथ्म समय में अधिकतम एलओपीटी + 1 डिब्बे के साथ एक समाधान ढूंढता हैः इस एल्गोरिथ्म का एक यादृच्छिक संस्करण अपेक्षित समय में चलता हैः फ्रैक्शनल एल. पी. को गोल करने के लिए करमरकर और कार्प ने आगे फ्रैक्शनल एल. पी. को इंटीग्रल एल. पी. के अनुमानित समाधान में गोल करने का एक तरीका विकसित किया; करमरकर-कार्प बिन पैकिंग एल्गोरिदम देखें। उनके प्रमाण से पता चलता है कि इस एल. पी. का योगात्मक समाकलन अंतर ओ (लॉग2 (एन)) में है। बाद में, होबर्ग और रोथवोस ने अपने परिणाम में सुधार किया और साबित किया कि समाकलन अंतर ओ (लॉग (एन)) में है। समाकलन अंतराल पर सबसे अच्छी ज्ञात निचली सीमा एक स्थिरांक ω (1) है। सटीक समाकलन अंतर का पता लगाना एक खुली समस्या है। बिन के आवरण में बिन के आवरण की समस्या में, विभिन्न आकारों के एन आइटम होते हैं। लक्ष्य वस्तुओं को अधिकतम संख्या में डिब्बे में पैक करना है, जहां प्रत्येक डिब्बे में कम से कम बी होना चाहिए। इस समस्या के लिए एक प्राकृतिक विन्यास एल. पी. हो सकता हैः जहां ए कम से कम बी के योग के साथ वस्तुओं के सभी विन्यासों का प्रतिनिधित्व करता है (कोई केवल समावेश-न्यूनतम विन्यास ले सकता है)। इस एल. पी. के साथ समस्या यह है कि, बिन-कवरिंग समस्या में, छोटी वस्तुओं को संभालना समस्याग्रस्त है, क्योंकि इष्टतम समाधान के लिए छोटी वस्तुएं आवश्यक हो सकती हैं। छोटी वस्तुओं की अनुमति के साथ, करमरकर और कार्प की तकनीक के लिए भी विन्यास की संख्या बहुत बड़ी हो सकती है। सिरिक, जॉनसन और केन्यन एक वैकल्पिक एल. पी. प्रस्तुत करते हैं। सबसे पहले, वे वस्तुओं के एक समूह को परिभाषित करते हैं जिन्हें छोटा कहा जाता है। मान लीजिए कि टी सभी छोटी वस्तुओं का कुल आकार है। फिर, वे एक मैट्रिक्स ए का निर्माण करते हैं जो योग <2 के साथ सभी विन्यासों का प्रतिनिधित्व करता है। फिर, वे उपरोक्त एल. पी. को एक अतिरिक्त बाधा मानते हैंः अतिरिक्त बाधा इस बात की गारंटी देती है कि डिब्बे में "खाली जगह" को छोटी वस्तुओं से भरा जा सकता है। इस एल. पी. का दोहरे भाग अधिक जटिल है और इसे एक साधारण नापसैक-समस्या पृथक्करण ऑरेकल द्वारा हल नहीं किया जा सकता है। सिरिक, जॉनसन और केन्यन इसे लगभग 1/एप्सिलॉन में समय घातांक में हल करने के लिए एक अलग विधि प्रस्तुत करते हैं। जेनसेन और सोलिस-ओबा इसे लगभग 1/एप्सिलॉन में समय घातांक में हल करने के लिए एक बेहतर विधि प्रस्तुत करते हैं। मशीन शेड्यूलिंग में असंबंधित-मशीन शेड्यूलिंग की समस्या में, कुछ अलग-अलग मशीनें हैं जिन्हें कुछ अलग-अलग कार्यों को संसाधित करना चाहिए। जब मशीन I काम जे को संसाधित करता है, तो इसमें पाई, जे में समय लगता है। लक्ष्य मशीनों के बीच कार्यों को इस तरह विभाजित करना है कि एक मशीन का अधिकतम पूरा होने का समय जितना संभव हो उतना कम हो। इस समस्या का निर्णय संस्करण हैः समय T दिए जाने पर, क्या कोई विभाजन है जिसमें सभी मशीनों का पूरा होने का समय अधिकतम T है? प्रत्येक मशीन i के लिए, कार्यों के सीमित रूप से कई उपसमुच्चय होते हैं जिन्हें मशीन i द्वारा अधिकतम T पर समय पर संसाधित किया जा सकता है। ऐसे प्रत्येक उपसमुच्चय को मशीन i के लिए एक विन्यास कहा जाता है। Ci (T) द्वारा मशीन i के लिए सभी विन्यासों का सेट, समय T दिया गया है। Ci (T) में प्रत्येक मशीन i और विन्यास c के लिए, एक चर को परिभाषित करें जो मशीन i में उपयोग किए गए वास्तविक विन्यास c के 1 iff के बराबर है, और अन्यथा 0 है। फिर, एल. पी. की बाधाएं हैंः प्रत्येक मशीन के लिए i 1,., m में; प्रत्येक कार्य के लिए j 1,., n में; प्रत्येक i, j के लिए। गुण असंबंधित-मशीनों के समय निर्धारण के लिए विन्यास-एल. पी. का अभिन्नता अंतर 2 है। हाई-मल्टीप्लिसिटी बिन पैकिंग संदर्भ बिन पैकिंग संख्या विभाजन कार्य निर्धारण रैखिक प्रोग्रामिंग भी देखें।