幺模矩阵-线性规划的整数解特性

百度百科:幺模矩阵

在线性规划问题中，如果A为幺模矩阵，那么该问题具有最优整数解特性。也就是说使用单纯形法进行求解，得到的解即为整数解。无需再特定使用整数规划方法。
$$\begin{array}{rl}min& {\mathbf{c}}^T\mathbf{x}\\ s.t.& \{\begin{array}{l}\mathbf{Ax}\ge \mathbf{b}\\ \mathbf{x}\ge 0\end{array}\end{array}$$
在实际应用中，例如网络流问题、匹配问题和覆盖问题等，在问题的线性表示中，经常出现幺模矩阵作为约束矩阵。