完全単模行列

完全単模行列#

  • 読み: かんぜんたんもぎょうれつ

  • 英名: Totally Unimodular Matrix

任意の小行列式が 0, 1, -1 の値をとる整数行列のことをいう.

整数線形計画問題において,係数行列が完全単模行列となるとき,連続緩和問題の最適基底解が整数計画問題の最適解になる.したがって,単体法で解くと整数解が得られる.これは,完全単模行列の任意の基底行列は,逆行列が再び整数行列になっていることから分かる.

関連