分支定界演算法

分支定界演算法是已被提出的多種自適應分割槽策略，用於解決全域性最佳化模型。 這些方法基於分割槽、抽樣以及後續的下界和上界程式：這些操作被迭代地應用於可行集 內的活動（“候選”）子集集合中。 它們的窮舉搜尋特性以類似於整數線性規劃方法的精神得到保證。 分支定界涵蓋了許多具體的方法，並允許各種實現方式。 分支定界方法通常依賴於關於問題的一些先驗結構知識。 例如，這些資訊可能與每個函式的變化速度有關（例如，關於每個函式 和 的合適“整體”利普希茨常數的知識）；或者與所有函式的解析公式的可用性和保證的光滑性有關（例如，在基於區間算術的方法中）。 一般的分支定界方法適用於廣泛的全域性最佳化問題，例如，在組合最佳化、凹最小化、反向凸規劃、DC 規劃和利普希茨最佳化中（Neumaier 1990, Hansen 1992, Ratschek and Rokne 1995, Kearfott 1996, Horst and Tuy 1996, Pintér 1996）。