分支-切割法

分支-切割法是把分支定界法與割平面法結合起來。

20世紀60年代至70年代初，由於分支定界法的發展和最佳化，產生了一次大的突破，小問題(100個變數以內)能被高效率地解決，題目稍微增大點卻很可能使計算時間呈指數級增長，超出了可行範圍內。在攻克計算時間隨問題增大指數級增長方面沒有多大的進展。現實中的許多問題無法解決。

隨著分支-切割法被用處理0-1整數規劃問題，20世紀80年代中期迎來了很大的突破。此後，有進一步的發展。起先，此方法只用於純0-1整數規劃問題，然後被擴展至混合0-1整數規劃問題。接著是混合整數規劃問題。

現在分支-切割法已經很普遍的套用於成千上萬變數的問題了。

ps：這種算法並不能解決所有成千上萬變數的整數規劃問題。該算法依賴於稀疏係數矩陣，所以大家建模時還得謹慎。