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

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

पूर्णांक प्रोग्रामिंग एनपी-पूर्ण है। विशेष रूप से, 0-1 पूर्णांक रैखिक प्रोग्रामिंग का विशेष स्थिति, जिसमें अज्ञात बाइनरी हैं, और एकमात्र प्रतिबंधों को संतुष्ट होना चाहिए, कार्प की 21 एनपी-पूर्ण समस्याओं में से एक है।

यदि कुछ निर्णय चर असतत नहीं हैं, तो समस्या को मिश्रित-पूर्णांक प्रोग्रामिंग समस्या के रूप में जाना जाता है।

आईएलपी के लिए प्रामाणिक और मानक रूप

पूर्णांक रैखिक प्रोग्रामिंग में, विहित रूप मानक रूप से भिन्न होता है। विहित रूप में एक पूर्णांक रैखिक कार्यक्रम इस प्रकार व्यक्त किया जाता है (ध्यान दें कि यह है $\mathbf {x}$ वेक्टर जो तय किया जाना है):

${\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ^{n},\end{aligned}}$

और आई. एल. पी. को मानक रूप में व्यक्त किया जाता है

${\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ^{n},\end{aligned}}$

जहाँ $\mathbf {c} \in \mathbb {R} ^{n},\mathbf {b} \in \mathbb {R} ^{m}$ वेक्टर और हैं $A\in \mathbb {R} ^{m\times n}$ एक मैट्रिक्स है। जैसा कि रैखिक कार्यक्रमों के साथ होता है, आईएलपी जो मानक रूप में नहीं हैं, असमानताओं को समाप्त करके, सुस्त चरों ($\mathbf {s}$) को प्रस्तुत करके सरल एल्गोरिथम मानक रूप हो सकते हैं और वेरिएबल्स को बदलना जो साइन-बाधित नहीं हैं, दो साइन-बाधित चर के अंतर के साथ

उदाहरण

एलपी छूट के साथ आईपी पॉलीटॉप

दाईं ओर का प्लॉट निम्नलिखित समस्या दिखाता है।

${\begin{aligned}\max &{\text{ }}y\\-x+y&\leq 1\\3x+2y&\leq 12\\2x+3y&\leq 12\\x,y&\geq 0\\x,y&\in \mathbb {Z} \end{aligned}}$

व्यवहार्य पूर्णांक बिंदुओं को लाल रंग में दिखाया गया है, और लाल धराशायी रेखाएँ उनके उत्तल पतवार को दर्शाती हैं, जो कि सबसे छोटा उत्तल पॉलीहेड्रॉन है जिसमें ये सभी बिंदु सम्मलित हैं। समन्वय अक्षों के साथ नीली रेखाएं एलपी छूट के पॉलीहेड्रॉन को परिभाषित करती हैं, जो असमानताओं के माध्यम से अभिन्नता बाधा के बिना दी जाती है। ऑप्टिमाइज़ेशन का लक्ष्य काली धराशायी रेखा को पॉलीहेड्रॉन को छूते हुए ऊपर की ओर ले जाना है। पूर्णांक समस्या का इष्टतम समाधान बिंदु हैं $(1,2)$ और $(2,2)$ जिसका दोनों का उद्देश्य मान 2 है। विश्राम का अद्वितीय इष्टतम है $(1.8,2.8)$ 2.8 के उद्देश्य मूल्य के साथ है। यदि छूट का समाधान निकटतम पूर्णांकों तक किया जाता है, तो यह आईएलपी के लिए संभव नहीं है।

एनपी-कठोरता का प्रमाण

निम्नलिखित न्यूनतम वर्टेक्स कवर से पूर्णांक प्रोग्रामिंग में कमी है जो एनपी-कठोरता के प्रमाण के रूप में काम करेगा।

मान लीजिए $G=(V,E)$ एक अप्रत्यक्ष ग्राफ बनें। एक रेखीय कार्यक्रम को निम्नानुसार परिभाषित करें:

${\begin{aligned}\min \sum _{v\in V}y_{v}\\y_{v}+y_{u}&\geq 1&&\forall uv\in E\\y_{v}&\geq 0&&\forall v\in V\\y_{v}&\in \mathbb {Z} &&\forall v\in V\end{aligned}}$

यह देखते हुए कि बाधाओं की सीमा $y_{v}$ से या तो 0 या 1 तक, पूर्णांक प्रोग्राम का कोई भी व्यवहार्य समाधान वर्टिकल का एक सबसेट है। पहली बाधा का तात्पर्य है कि इस उपसमुच्चय में प्रत्येक किनारे का कम से कम एक अंत बिंदु सम्मलित है। इसलिए, समाधान शीर्ष आवरण का वर्णन करता है। इसके अतिरिक्त कुछ वर्टेक्स कवर C दिया गया है, $y_{v}$ किसी के लिए 1 पर सेट किया जा सकता है $v\in C$ और किसी के लिए 0 $v\not \in C$ इस प्रकार हमें पूर्णांक कार्यक्रम के लिए एक व्यवहार्य समाधान प्रदान करता है। इस प्रकार हम यह निष्कर्ष निकाल सकते हैं कि यदि हम योग को कम करते हैं $y_{v}$ हमने न्यूनतम वर्टेक्स कवर भी पाया है।

वेरिएंट

मिश्रित-पूर्णांक रैखिक प्रोग्रामिंग (एमआईएलपी ) में ऐसी समस्याएँ सम्मलित हैं जिनमें एकमात्र कुछ चर, $x_{i}$, पूर्णांक होने के लिए विवश हैं, चूंकि अन्य चरों को गैर-पूर्णांक होने की अनुमति है।

शून्य-एक रैखिक प्रोग्रामिंग (या बाइनरी पूर्णांक प्रोग्रामिंग) में ऐसी समस्याएं सम्मलित हैं जिनमें चर 0 या 1 तक सीमित हैं। किसी भी परिबद्ध पूर्णांक चर को बाइनरी डेटा के संयोजन के रूप में व्यक्त किया जा सकता है। उदाहरण के लिए, एक पूर्णांक चर दिया गया है, $0\leq x\leq U$, चर का उपयोग करके व्यक्त किया जा सकता है $\lfloor \log _{2}U\rfloor +1$ द्विआधारी चर:

$x=x_{1}+2x_{2}+4x_{3}+\cdots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\rfloor +1}.$

अनुप्रयोग

एक रेखीय कार्यक्रम के रूप में समस्याओं को मॉडलिंग करते समय पूर्णांक चर का उपयोग करने के दो मुख्य कारण हैं:

1. पूर्णांक चर उन मात्राओं का प्रतिनिधित्व करते हैं जो एकमात्र पूर्णांक हो सकती हैं। उदाहरण के लिए, 3.7 कारों का निर्माण संभव नहीं है।
2. पूर्णांक चर निर्णयों का प्रतिनिधित्व करते हैं (उदाहरण के लिए एक ग्राफ (असतत गणित) में किनारे को सम्मलित करना है या नहीं) और इसलिए एकमात्र 0 या 1 मान लेना चाहिए।

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

उत्पादन योजना

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

निर्धारण

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

प्रादेशिक विभाजन

विभिन्न मानदंडों या बाधाओं पर विचार करते हुए कुछ कार्यों की योजना बनाने के लिए प्रादेशिक विभाजन या जिलाकरण समस्या में एक भौगोलिक क्षेत्र को जिलों में विभाजित करना सम्मलित है। इस समस्या के लिए कुछ आवश्यकताएँ हैं: सामीप्य, सघनता, संतुलन या समता, प्राकृतिक सीमाओं का सम्मान, और सामाजिक-आर्थिक एकरूपता। इस प्रकार की समस्या के लिए कुछ अनुप्रयोगों में सम्मलित हैं: राजनीतिक डिस्ट्रिक्टिंग, स्कूल डिस्ट्रिक्टिंग, स्वास्थ्य सेवाएं डिस्ट्रिक्टिंग और अपशिष्ट प्रबंधन डिस्ट्रिक्टिंग।

दूरसंचार नेटवर्क

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

सेलुलर नेटवर्क

मोबाइल संचार के लिए वैश्विक प्रणाली(जीएसएम) मोबाइल नेटवर्क में आवृत्ति प्लानिंग के कार्य में एंटेना में उपलब्ध आवृत्ति को वितरित करना सम्मलित है जिससे उपयोगकर्ताओं को सेवा दी जा सके और एंटेना के बीच हस्तक्षेप कम से कम हो। इस समस्या को एक पूर्णांक रेखीय कार्यक्रम के रूप में तैयार किया जा सकता है जिसमें द्विआधारी चर इंगित करते हैं कि एक आवृत्ति एक ऐन्टेना को सौंपी गई है या नहीं।

अन्य अनुप्रयोग

• कैशफ्लो मिलान
• ऊर्जा प्रणाली अनुकूलन
• मानव रहित हवाई वाहन मार्गदर्शन प्रणाली

एल्गोरिदम

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

कुल एकरूपता का उपयोग

चूंकि सामान्यतः LP छूट का समाधान अभिन्न होने की गारंटी नहीं होगी, यदि आईएलपी का रूप है $\max \mathbf {c} ^{\mathrm {T} }\mathbf {x}$ ऐसा है कि $A\mathbf {x} =\mathbf {b}$ जहाँ $A$ और $\mathbf {b}$ सभी पूर्णांक प्रविष्टियाँ हैं और $A$ एकरूप मैट्रिक्स कुल एकरूपता है, तो हर बुनियादी व्यवहार्य समाधान अभिन्न है। परिणाम स्वरुप, सिंप्लेक्स एल्गोरिदम के माध्यम से लौटाया गया समाधान अभिन्न होने की गारंटी है। यह दर्शाने के लिए कि प्रत्येक मूल साध्य हल समाकल है, मान लीजिए $\mathbf {x}$ एक इच्छानुसार बुनियादी व्यवहार्य समाधान बनें। तब से $\mathbf {x}$ व्यवहार्य है,

हम वह जानते हैं $A\mathbf {x} =\mathbf {b}$. होने देना $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$ मूल समाधान के लिए आधार स्तंभों के अनुरूप तत्व बनें $\mathbf {x}$. एक आधार की परिभाषा के अनुसार, कुछ वर्ग सबमैट्रिक्स होता है $B$ का $A$ रैखिक रूप से स्वतंत्र स्तंभों के साथ $B\mathbf {x} _{0}=\mathbf {b}$.

चूंकि के कॉलम $B$ रैखिक रूप से स्वतंत्र हैं और $B$ चौकोर है, $B$ विलक्षण भी है और इसलिए धारणा से, $B$ यूनिमॉड्यूलर मैट्रिक्स है और इसलिए $\det(B)=\pm 1$. इसके अतिरिक्त, चूंकि $B$ निरर्थक है, यह उलटा है और इसलिए $\mathbf {x} _{0}=B^{-1}\mathbf {b}$. परिभाषा से, $B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }$. यहाँ $B^{\mathrm {adj} }$ के अदजुगेट मैट्रिक्स को दर्शाता है $B$ और अभिन्न है क्योंकि $B$ अभिन्न है। इसलिए,

${\begin{aligned}&\Rightarrow B^{-1}=\pm B^{\mathrm {adj} }{\text{ is integral.}}\\&\Rightarrow \mathbf {x} _{0}=B^{-1}b{\text{ is integral.}}\\&\Rightarrow {\text{Every basic feasible solution is integral.}}\end{aligned}}$

इस प्रकार, यदि मैट्रिक्स $A$ एक आईएलपी पूरी प्रकार से एकरूप है, एक आईएलपी एल्गोरिदम का उपयोग करने के अतिरिक्त, एलपी विश्राम को हल करने के लिए सिंप्लेक्स विधि का उपयोग किया जा सकता है और समाधान पूर्णांक होगा।

त्रुटिहीन एल्गोरिदम

जब मैट्रिक्स $A$ पूरी प्रकार से एकरूप नहीं है, ऐसे कई प्रकार के एल्गोरिदम हैं जिनका उपयोग पूर्णांक रैखिक कार्यक्रमों को त्रुटिहीन रूप से हल करने के लिए किया जा सकता है। एल्गोरिदम का एक वर्ग कटिंग-प्लेन विधि है जो एलपी छूट को हल करके काम करता है और फिर रैखिक बाधाओं को जोड़ता है जो किसी भी पूर्णांक व्यवहार्य बिंदुओं को छोड़कर समाधान को पूर्णांक होने की ओर ले जाता है।

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

चरों की एक छोटी संख्या के लिए त्रुटिहीन एल्गोरिदम

कल्पना करना $A$ एक एम-बाय-एन पूर्णांक मैट्रिक्स है और $\mathbf {b}$ एक m-by-1 पूर्णांक वेक्टर है। हम व्यवहार्यता समस्या पर ध्यान केंद्रित करते हैं, जो यह तय करना है कि एन-बाय-1 वेक्टर सम्मलित है या नहीं $\mathbf {x}$ संतुष्टि देने वाला $A\mathbf {x} \leq \mathbf {b}$.

V में गुणांकों का अधिकतम निरपेक्ष मान होने दें $A$ और $\mathbf {b}$. यदि n (चरों की संख्या) एक निश्चित स्थिरांक है, तो व्यवहार्यता समस्या को m और लॉग V में समय बहुपद में हल किया जा सकता है। यह स्थिति n=1 के लिए तुच्छ है। स्थितियोंn = 2 को 1981 में हर्बर्ट स्कार्फ के माध्यम से हल किया गया था। सामान्य स्थिति 1983 में हेनरी लेनस्ट्रा के माध्यम से हल किया गया था, लेज़्लो लोवाज़ और पीटर वैन एम्डे बोस के विचारों को मिलाकर।

0-1 आईएलपी के विशेष स्थितियोंमें, लेनस्ट्रा का एल्गोरिथ्म पूर्ण गणना के बराबर है: सभी संभावित समाधानों की संख्या निश्चित है (2ⁿ), और प्रत्येक समाधान की व्यवहार्यता की जाँच टाइम पॉली (m, लॉग V) में की जा सकती है। सामान्य स्थिति में, जहां प्रत्येक चर एक इच्छानुसार पूर्णांक हो सकता है, पूर्ण गणना असंभव है। यहाँ, लेनस्ट्रा का एल्गोरिथ्म संख्याओं की ज्यामिति से विचारों का उपयोग करता है। यह मूल समस्या को निम्नलिखित गुण के साथ समकक्ष समस्या में बदल देता है: या तो समाधान का अस्तित्व $\mathbf {x}$ स्पष्ट है, या का मूल्य $x_{n}$ (एन-वें चर) एक अंतराल से संबंधित है जिसकी लंबाई एन के एक समारोह से बंधी है। बाद के स्थितियोंमें, समस्या कम-आयामी समस्याओं की एक सीमित संख्या में कम हो जाती है। एल्गोरिथम की रन-टाइम जटिलता को कई चरणों में सुधारा गया है:

• लेनस्ट्रा का मूल एल्गोरिदमरन-टाइम था $2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}$.
• कन्नन रन-टाइम के साथ एक अधिक अच्छा एल्गोरिथ्म प्रस्तुत किया $n^{O(n)}\cdot (m\cdot \log V)^{O(1)}$.
• फ्रैंक और टार्डोस एक अलग अधिक अच्छा एल्गोरिदम प्रस्तुत किया। अधिक अच्छा रनटाइम है $n^{2.5n}\cdot \ell$, जहाँ $\ell$ इनपुट बिट्स की संख्या है, जो इसमें है ${\text{poly}}(m,\log {V})$.

अनुमानी तरीके

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

आईएलपी पर लागू किए जा सकने वाले अन्य अनुमानी तरीकों में सम्मलित हैं

• पहाड़ी की चढ़ाई
• तैयार किए हुयी धातु पे पानी चढाने की कला
• प्रतिक्रियाशील खोज अनुकूलन
• चींटी कॉलोनी अनुकूलन एल्गोरिदम
• हॉपफील्ड नेटवर्क

कई अन्य समस्या-विशिष्ट अनुमान भी हैं, जैसे कि ट्रैवलिंग सेल्समैन समस्या इटरेटिव इम्प्रूवमेंट|के-ऑप्ट ह्यूरिस्टिक फॉर द ट्रैवलिंग सेल्समैन समस्या। हेयुरिस्टिक विधियों का एक हानि यह है कि यदि वे समाधान खोजने में विफल रहते हैं, तो यह निर्धारित नहीं किया जा सकता है कि क्या ऐसा इसलिए है क्योंकि कोई व्यवहार्य समाधान नहीं है या एल्गोरिथम एकमात्र एक को खोजने में असमर्थ था। इसके अतिरिक्त, सामान्यतः पर यह निर्धारित करना असंभव है कि इन विधियों के माध्यम से दिए गए इष्टतम समाधान के कितने करीब हैं।

विरल पूर्णांक प्रोग्रामिंग

अधिकांशतः ऐसा होता है कि मैट्रिक्स $A$ जो परिभाषित करता है पूर्णांक कार्यक्रम विरल है। विशेष रूप से, यह तब होता है जब मैट्रिक्स में ब्लॉक संरचना होती है, जो कई अनुप्रयोगों में होती है। मैट्रिक्स की विरलता को निम्नानुसार मापा जा सकता है। का ग्राफ $A$ के स्तंभों के संगत शीर्ष हैं $A$, और दो स्तंभ एक किनारा बनाते हैं यदि $A$ एक पंक्ति है जहाँ दोनों स्तंभों में गैर-शून्य प्रविष्टियाँ हैं। समतुल्य रूप से, शीर्ष चर के अनुरूप होते हैं, और दो चर एक किनारे बनाते हैं यदि वे एक असमानता साझा करते हैं। विरलता माप $d$ का $A$ के ग्राफ की वृक्ष-गहराई के बीच न्यूनतम है $A$ और के स्थानान्तरण के ग्राफ की वृक्ष-गहराई $A$. होने देना $a$ का संख्यात्मक माप हो $A$ की किसी भी प्रविष्टि के अधिकतम निरपेक्ष मान के रूप में परिभाषित किया गया है $A$. होने देना $n$ पूर्णांक कार्यक्रम के चर की संख्या हो। फिर इसे 2018 में दिखाया गया कि पूर्णांक प्रोग्रामिंग को दृढ़ता से बहुपद और फिक्स्ड-पैरामीटर ट्रैक्टेबल समय के माध्यम से पैरामीटरित करके हल किया जा सकता है $a$ और $d$. अर्थात कुछ कम्प्यूटेशनल फंक्शन के लिए $f$ और कुछ स्थिर $k$, पूर्णांक प्रोग्रामिंग को समय पर हल किया जा सकता है $f(a,d)n^{k}$. विशेष रूप से, समय दाहिनी ओर से स्वतंत्र है $b$ और उद्देश्य समारोह $c$. इसके अतिरिक्त, लेनस्ट्रा के मौलिक परिणाम के विपरीत, जहां संख्या $n$ चर का एक पैरामीटर है, यहाँ संख्या है $n$ चर का इनपुट का एक परिवर्तनशील भाग है।

यह भी देखें

• विवश न्यूनतम वर्ग

अग्रिम पठन

• George L. Nemhauser; Laurence A. Wolsey (1988). Integer and combinatorial optimization. Wiley. ISBN 978-0-471-82819-8.
• Alexander Schrijver (1998). Theory of linear and integer programming. John Wiley and Sons. ISBN 978-0-471-98232-6.
• Laurence A. Wolsey (1998). Integer programming. Wiley. ISBN 978-0-471-28366-9.
• Dimitris Bertsimas; Robert Weismantel (2005). Optimization over integers. Dynamic Ideas. ISBN 978-0-9759146-2-5.
• John K. Karlof (2006). Integer programming: theory and practice. CRC Press. ISBN 978-0-8493-1914-3.
• H. Paul Williams (2009). Logic and Integer Programming. Springer. ISBN 978-0-387-92279-9.
• Michael Jünger; Thomas M. Liebling; Denis Naddef; George Nemhauser; William R. Pulleyblank; Gerhard Reinelt; Giovanni Rinaldi; Laurence A. Wolsey, eds. (2009). 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art. Springer. ISBN 978-3-540-68274-5.
• Der-San Chen; Robert G. Batson; Yu Dang (2010). Applied Integer Programming: Modeling and Solution. John Wiley and Sons. ISBN 978-0-470-37306-4.
• Gerard Sierksma; Yori Zwols (2015). Linear and Integer Optimization: Theory and Practice. CRC Press. ISBN 978-1-498-71016-9.

बाहरी संबंध

• A Tutorial on Integer Programming
• Conference Integer Programming and Combinatorial Optimization, IPCO
• The Aussois Combinatorial Optimization Workshop

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

• Evolutionary algorithm
• Hill climbing
• Local search
• Simulated annealing
• Tabu search

| below =

• Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

• पहाड़ी की चढ़ाई
• स्थानीय खोज
• तैयार किए हुयी धातु पे पानी चढाने की कला
• तब्बू खोज

| below =* सॉफ्टवेयर

}}