Integer programming — पूर्णांक प्रोग्रामिंग

पूर्णांक प्रोग्रामिंग (पू.प्र.; अंग्रेज़ी: integer programming, IP) — यह गणितीय अनुकूलन की वह शाखा है जिसमें ऐसी समस्याओं का अध्ययन किया जाता है, जहाँ कुछ या सभी चर केवल पूर्णांक मान ही ग्रहण कर सकते हैं।

सर्वाधिक अध्ययन किया गया विशेष मामला पूर्णांक रैखिक प्रोग्रामिंग (पू.रै.प्र.; अंग्रेज़ी: integer linear programming, ILP) है, जिसमें उद्देश्य फलन और बाधाएँ रैखिक होती हैं। रैखिक प्रोग्रामिंग के विपरीत, जहाँ चर कोई भी वास्तविक मान ले सकते हैं, पूर्णांकता की आवश्यकता पू.प्र. की समस्याओं को हल करना काफी अधिक जटिल बना देती है।

पूर्णांक प्रोग्रामिंग का अर्थशास्त्र, लॉजिस्टिक्स, उत्पादन नियोजन और अन्य क्षेत्रों में व्यापक उपयोग है, जहाँ चर स्वभावतः विविक्त (discrete) होते हैं (उदाहरण के लिए, उत्पादित इकाइयों की संख्या या कर्मचारियों की संख्या)।

परिभाषा और शब्दावली

पूर्णांक रैखिक प्रोग्रामिंग की सामान्य समस्या को निम्नलिखित रूप में लिखा जा सकता है:

वेक्टर $x$ ज्ञात कीजिए, जो:

$c^{T}x$ को अधिकतम (या न्यूनतम) करे

इन शर्तों के अधीन:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{Z}}^n$ (वेक्टर $x$ के सभी घटक — पूर्णांक हैं)

जहाँ $x$ — चरों का वेक्टर, $c$ और $b$ — वेक्टर हैं, तथा $A$ — गुणांकों की आव्यूह है।

चरों पर आवश्यकताओं के अनुसार निम्नलिखित प्रकार की समस्याएँ विभेदित की जाती हैं:

• पूर्णतः पूर्णांक प्रोग्रामिंग: सभी चर पूर्णांक होने चाहिए।
• मिश्रित-पूर्णांक प्रोग्रामिंग (अंग्रेज़ी: mixed-integer programming, MIP): केवल कुछ चर ही पूर्णांक होने चाहिए।
• बूलीय (0-1) प्रोग्रामिंग: चर केवल 0 या 1 का मान लेते हैं, जिससे "हाँ/नहीं" जैसे तार्किक निर्णयों का मॉडलिंग संभव होता है।

मुख्य गुण और जटिलता

परिकलनीय जटिलता

पूर्णांक रैखिक प्रोग्रामिंग की सामान्य समस्या NP-कठिन है। इसका अर्थ यह है कि कोई ज्ञात एल्गोरिथ्म नहीं है जो किसी भी स्वेच्छ पू.प्र. समस्या का सटीक इष्टतम हल बहुपद समय में ज्ञात कर सके। यह जटिलता समस्या की संयोजनात्मक प्रकृति के कारण है, क्योंकि संभावित पूर्णांक हलों की संख्या चरों की संख्या बढ़ने के साथ घातीय रूप से बढ़ सकती है।

रैखिक प्रोग्रामिंग से संबंध (LP-शिथिलता)

किसी भी पू.प्र. समस्या के लिए उसकी रैखिक शिथिलता (linear relaxation) — एक रैखिक प्रोग्रामिंग (LP) समस्या — को सूत्रबद्ध किया जा सकता है, जिसमें पूर्णांकता की आवश्यकता को हटा दिया जाता है। LP-शिथिलता के हल के दो महत्त्वपूर्ण गुण हैं:

1. इसे काफी तेज़ी से (बहुपद समय में) ज्ञात किया जा सकता है।
2. LP-शिथिलता के उद्देश्य फलन का इष्टतम मान मूल पूर्णांक समस्या के इष्टतम मान का आकलन (अधिकतमीकरण समस्या के लिए ऊपरी सीमा और न्यूनतमीकरण के लिए निचली सीमा) प्रदान करता है।

हालाँकि, LP-शिथिलता के भिन्नात्मक हल को निकटतम पूर्णांकों तक सरल रूप से पूर्णांकित करने पर सामान्यतः पूर्णांक समस्या का इष्टतम या यहाँ तक कि सुसंगत हल प्राप्त नहीं होता।

पूर्ण यूनिमॉड्यूलरिटी का गुण

पू.रै.प्र. समस्याओं का एक महत्त्वपूर्ण वर्ग है जो उनकी LP-शिथिलता की तरह ही सरलता से हल हो जाता है। ये वे समस्याएँ हैं जिनमें बाधा आव्यूह $A$ पूर्णतः यूनिमॉड्यूलर होती है (अर्थात उसकी किसी भी वर्ग उपआव्यूह का सारणिक 0, +1 या −1 होता है)। यदि आव्यूह $A$ पूर्णतः यूनिमॉड्यूलर है और वेक्टर $b$ पूर्णांक है, तो LP-शिथिलता के सुसंगत हल के बहुफलकीय क्षेत्र के सभी शीर्ष स्वतः ही पूर्णांक होंगे। फलतः, सिम्प्लेक्स विधि द्वारा प्राप्त हल पूर्णांक होगा। ऐसी समस्याओं के उदाहरण परिवहन समस्या और असाइनमेंट समस्या हैं।

हल करने की विधियाँ

पूर्ण यूनिमॉड्यूलरिटी के गुण से रहित सामान्य पू.प्र. समस्याओं के लिए अंतर्निहित गणना के विचारों पर आधारित सटीक विधियाँ विकसित की गई हैं।

• ब्रांच और बाउंड विधि (अंग्रेज़ी: Branch and Bound) — मुख्य सटीक विधि, जो सुसंगत हलों के समुच्चय को उपसमुच्चयों में व्यवस्थित रूप से विभाजित (शाखाओं में बाँटने) और उन उपसमुच्चयों को काटने पर आधारित है जिनमें निश्चित रूप से इष्टतम हल नहीं है। उपसमुच्चयों की संभावना का आकलन करने के लिए LP-शिथिलता का उपयोग किया जाता है।

• छेदक तल विधि (गोमोरी विधि; अंग्रेज़ी: Cutting Plane Method) — एक पुनरावृत्त दृष्टिकोण जो क्रमशः समस्या में नई रैखिक बाधाएँ ("कटाव") जोड़ता है। ये कटाव LP-शिथिलता के भिन्नात्मक हलों को "काट देते" हैं, किसी भी सुसंगत पूर्णांक हल को प्रभावित किए बिना, धीरे-धीरे LP-शिथिलता के सुसंगत हल के क्षेत्र को पूर्णांक हलों के उत्तल आवरण के निकट लाते हैं।

आधुनिक समाधानकर्ता (solvers) सामान्यतः हाइब्रिड एल्गोरिदम का उपयोग करते हैं, जैसे ब्रांच और कट विधि (अंग्रेज़ी: Branch and Cut), जो दोनों दृष्टिकोणों के लाभों को संयुक्त करती है।

उदाहरण और अनुप्रयोग क्षेत्र

पूर्णांक प्रोग्रामिंग संयोजनात्मक अनुकूलन की अनेक क्लासिक समस्याओं का मॉडलिंग करने में सक्षम है।

• नैपसैक समस्या: 0-1 प्रोग्रामिंग की क्लासिक समस्या, जिसमें कुल वजन की सीमा से अधिक हुए बिना अधिकतम कुल मूल्य वाली वस्तुओं का चयन करना होता है।
• विक्रेता समस्या (Travelling Salesman Problem): दिए गए शहरों के समुच्चय से होकर गुजरने वाले सबसे छोटे मार्ग की खोज की समस्या। इसे पूर्णांक प्रोग्रामिंग समस्या के रूप में सूत्रबद्ध किया जा सकता है, जहाँ चर ग्राफ के किनारों को अंतिम मार्ग में शामिल करने के लिए उत्तरदायी होते हैं।

अपने लचीलेपन के कारण, पू.प्र. संक्रिया अनुसंधान में सर्वाधिक माँग वाले उपकरणों में से एक है और निम्नलिखित जैसे क्षेत्रों में इसका उपयोग होता है:

• लॉजिस्टिक्स और आपूर्ति श्रृंखला प्रबंधन: परिवहन मार्गों का अनुकूलन, गोदाम स्थापना, इन्वेंटरी प्रबंधन।
• उत्पादन नियोजन: उत्पादन अनुसूचियाँ बनाना, संसाधनों का वितरण, उपकरण लोडिंग।
• वित्त और अर्थशास्त्र: निवेश पोर्टफोलियो निर्माण, पूंजी बजटिंग।
• दूरसंचार और ऊर्जा: संचार नेटवर्क का डिज़ाइन, ऊर्जा इकाइयों के संचालन की योजना।

यह भी देखें

• रैखिक प्रोग्रामिंग
• ब्रांच और बाउंड विधि

टिप्पणियाँ

</references>