全單位模性

全單位模性(total unital modularity)組合最佳化問題的一種性質.指最佳化問題的約束Ax=b,二)0具有如下性質:A為整數矩陣且其任何一個非奇異子取值為1或一1.對於有全單位模性的最佳化問題,當b也為整數值向量時,就能確保其基礎最優解為整數解.例如,最大流問題、帶權的二部圖的匹配問題等組合最佳化問題,均具有全單位模性.

相關詞條

熱門詞條

聯絡我們