對于一個含有m個變量的模型，如果每個變量是連續(xù)變量，每個變量的范圍無論是[-5,100]、[5,500]、[0,1]......，都可以作為LP問題在多項式時間內(nèi)求解。

現(xiàn)在增加一個條件，模型中有n個變量是{0,1}變量。如果將變量松弛為[0,1]之間的連續(xù)變量，作為LP問題求解，這n個變量的取值可能是介于[0,1]區(qū)間的任何數(shù)，而無法保證是{0,1}。

分支定界是在這個背景下運用的。

我們以0-1整數(shù)規(guī)劃舉例：

首先，我們將0-1整數(shù)規(guī)劃模型松弛為LP模型求最優(yōu)解，對于最小化問題，該LRP的最優(yōu)解是原問題最優(yōu)解的下界，i.e. 原問題的最優(yōu)解一定不小于LRP的最優(yōu)解。

其次，我們令這n個變量在滿足{0,1}約束的前提下求出一個可行解，該解可能不是最優(yōu)解，一定是最優(yōu)解的上界，i.e. 原問題的最優(yōu)解一定不大于該可行解。

建樹：

如果模型中有n個{0,1}變量，我們就畫一個有

個葉子節(jié)點的二叉樹，如下。

n=4：

我們把LRP解得的x1的值（假如x1=0.7）作為根節(jié)點：

分支：

因為x1的取值是0或1，因此分支：

定界：

計算x1=0，其他變量松弛情況下，模型的最優(yōu)解y1。

計算x1=1，其他變量松弛情況下，模型的最優(yōu)解y2。

情形1：如果y1或y2大于當前的上界，則該支及其以下的分支沒必要search下去，稱為cut。

情形2：如果y1或y2小于當前的上界，則該支的下界被更新為y1或y2，稱為定界。

情形3：如果求得y1或y2時，這n個變量正好滿足{0,1}約束，則終止運算，因為滿足約束的松弛模型最優(yōu)解一定是原模型的最優(yōu)解。

對于情形1和2，我們還需要把運算進行下去。

分支：

因為x2的值也是在[0,1]區(qū)間上，我們將x2分支：

Note：x1=0或x1=1那個分支可能在上述情形1中被cut了。

定界：

分別計算x2=0、x2=1情況下，除x1、x2之外的其他變量松弛的最優(yōu)解。

情形1：當前松弛最優(yōu)解大于當前的上界（當前最優(yōu)可行解），則該支及其以下的分支沒必要search下去，稱為cut。

情形2：當前松弛最優(yōu)解小于當前的上界（當前最優(yōu)可行解），則下界被更新為當前松弛最優(yōu)解，稱為定界。

情形3：對于當前松弛最優(yōu)解，這n個變量正好滿足{0,1}約束，則終止運算，因為滿足約束的松弛模型最優(yōu)解一定是原模型的最優(yōu)解。

對于情形1和2，我們還需要把運算進行下去。

分支：

因為x3的值也是在[0,1]區(qū)間上，我們將x3分支：

Note：x2=0或x2=1的分支可能在上述情形1中被cut了。

定界：

與上同理。

分支：

因為x4的值也是在[0,1]區(qū)間上，我們將x4分支：

Note：x3=0或x3=1的某些分支可能在上述情形1中被cut了。

定界：

與上同理。

算法復雜度：

完整二叉樹的節(jié)點是指數(shù)增長的，to be exact，每增加1個{0,1}變量，最小分支（葉子節(jié)點）的個數(shù)需要乘以2。例如n=10，最小分支的個數(shù)為1024；n=15，最小分支的個數(shù)為32768；n=20，最小分支的個數(shù)為1048576。這就是指數(shù)爆炸！

如此復雜度的運算，那什么時候中止呢：

（1）獲得最優(yōu)解，如上情形3。

（2）上下界之間的gap小于預設(shè)的MIPGap參數(shù)值。

（3）完成了預設(shè)的運算時間。

（4）強制中止（Ctrl+C，輸入m.optimize()會從中止處繼續(xù)運行）

Note：“建樹”是根據(jù)定界逐步完成的，不是事先將完整的二叉樹建好，只會建滿足定界要求的“支”，顯然，最終建好的樹不是一個完整的二叉樹。

總結(jié)

以上是生活随笔為你收集整理的分支定界法上下界_分支定界(Branch-and-Cut)方法的逻辑的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。