पूर्ण दोहरी अभिन्नता

गणितीय अनुकूलन में, पूर्ण दोहरी अभिन्नता अभिन्न बहुफलक के लिए पर्याप्त शर्त है। इस प्रकार, ऐसे बहुफलक की पूर्णांक प्रोग्रामिंग रैखिक प्रोग्रामिंग की तकनीकों का उपयोग करके की जा सकती है।

एक रेखीय प्रणाली $Ax\leq b$, जहाँ $A$ और $b$ तर्कसंगत हैं, यदि कोई हो तो इसे पूर्ण दोहरी अभिन्नता (टीडीआई) कहा जाता है $c\in \mathbb {Z} ^{n}$ जैसे कि रैखिक कार्यक्रम का एक व्यवहार्य, सीमित समाधान हो

${\begin{aligned}&&\max c^{\mathrm {T} }x\\&&Ax\leq b,\end{aligned}}$

एक पूर्णांक इष्टतम दोहरा समाधान है।

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

ध्यान दें कि टीडीआई यूनिमॉड्यूलर मैट्रिक्स #पूर्ण_यूनिमॉड्यूलरिटी की तुलना में अभिन्नता के लिए एक अशक्त पर्याप्त शर्त है।