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

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

एक रेखीय प्रणाली $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$ कुछ TDI प्रणाली का समाधान सेट है $Ax\leq b$, कहाँ $b$ पूर्णांक का मान है.

ध्यान दें कि TDI Unimodular_matrix#Total_unimodularity की तुलना में अभिन्नता के लिए एक कमजोर पर्याप्त शर्त है।