整數線性規劃

整數線性規劃 (integer linear programming )變數取整數值的線性規劃。

它的一般形式為min Z，滿足條件，或，且取整數值。在一般線性規劃的約束條件之上，增加要求變數為整數值之後，使問題發生了深刻的變化，對理論和應用均產生影響，從而，形成了整數線性規劃特有分支。在n維歐氏空間E”中的點x，若其所有坐標均為整數，則稱此點為整點。而E0中所有的整點記為Z"，是一個格，稱此格為整格。於是，整數線性規劃就是在整格上的線性規劃.