簡介
整數規劃英文（integer programming）
定義：
線上性規劃問題中，有些最優解可能是分數或小數，但對於某些具體問題，常要求某些變數的解必須是整數。例如，當變數代表的是機器的台數，工作的人數或裝貨的車數等。為了滿足整數的要求，初看起來似乎只要把已得的非整數解捨入化整就可以了。實際上化整後的數不見得是可行解和最優解，所以應該有特殊的方法來求解整數規劃。在整數規劃中，如果所有變數都限制為整數，則稱為純整數規劃；如果僅一部分變數限制為整數，則稱為混合整數規劃。整數規劃的一種特殊情形是01規劃，它的變數僅限於0或1。不同於線性規劃問題，整數和01規劃問題至今尚未找到一般的多項式解法。
組合最最佳化
組合最最佳化通常都可表述為整數規劃問題。兩者都是在有限個可供選擇的方案中，尋找滿足一定約束的最好方案。有許多典型的問題反映整數規劃的廣泛背景。例如，背袋（或裝載）問題、固定費用問題、和睦探險隊問題（組合學的對集問題）、有效探險隊問題（組合學的復蓋問題）、旅行推銷員問題, 車輛路徑問題等。因此整數規劃的套用範圍也是極其廣泛的。它不僅在工業和工程設計和科學研究方面有許多套用，而且在計算機設計、系統可靠性、編碼和經濟分析等方面也有新的套用。
整數規劃
整數規劃是從1958年由R.E.戈莫里提出割平面法之後形成獨立分支的 ，30多年來發展出很多方法解決各種問題。解整數規劃最典型的做法是逐步生成一個相關的問題，稱它是原問題的衍生問題。對每個衍生問題又伴隨一個比它更易於求解的鬆弛問題（衍生問題稱為鬆弛問題的源問題）。通過鬆弛問題的解來確定它的源問題的歸宿，即源問題應被捨棄，還是再生成一個或多個它本身的衍生問題來替代它。隨即 ，再選擇一個尚未被捨棄的或替代的原問題的衍生問題，重複以上步驟直至不再剩有未解決的衍生問題為止。現今比較成功又流行的方法是分支定界法和割平面法，它們都是在上述框架下形成的。
—1規劃
0—1規劃在整數規劃中占有重要地位，一方面因為許多實際問題，例如指派問題、選地問題、送貨問題都可歸結為此類規劃，另一方面任何有界變數的整數規劃都與0—1規劃等價，用0—1規劃方法還可以把多種非線性規劃問題表示成整數規劃問題，所以不少人致力於這個方向的研究。求解0—1規劃的常用方法是分枝定界法，對各種特殊問題還有一些特殊方法，例如求解指派問題用匈牙利方法就比較方便。
