1. 從分支定界（branch and cut）到割平面（cutting plane）

割平面簡(jiǎn)單來說，就是添加約束條件。比如在分支定界算法中，添加的x≤floor[x_s]和x≥ceil[x_s]便是兩個(gè)用來割平面的約束條件。
分支定界法最終生成一顆樹，當(dāng)整數(shù)變量非常多時(shí)，求解節(jié)點(diǎn)會(huì)指數(shù)速度增加，因此需要使用一些方法提高求解速度，割平面法便是重要方法之一。分支的過程其實(shí)本身就是割平面的過程，floor[x]和ceil[x]之間的整個(gè)可行域在對(duì)x進(jìn)行分支的過程中被切割掉了。

2.從單純型表中尋找割平面

核心思想是：將約束條件中的小數(shù)部分分離出來形成新的約束。
假設(shè)整數(shù)規(guī)劃的線性松弛問題求解結(jié)果中有一個(gè)基變量x_i=b_i0不是整數(shù)，對(duì)應(yīng)的約束條件為：
x_i+Σ_j∈Jx_jb_ij = b_i0
其中J是非基變量下標(biāo)集合。
令Z(b) = floor(b)，也就是b的整數(shù)部分；S(b) = b-floor(b)，也就是b的小數(shù)部分。則有：
S(b_i) - Σ_j∈Jx_jS(A_ij) = Z(b_i) + Σ_j∈Jx_jZ(A_ij) - Z(b_i)
因此S(b_i) - Σ_j∈Jx_jA(b_ij) 是一個(gè)整數(shù)。
再結(jié)合S(b_i) - Σ_j∈Jx_jS(A_ij) ≤ S(b_i) ＜1
得到：
S(b_i) - Σ_j∈Jx_jS(b_ij) ≤ 0
好了，這就是松弛問題每個(gè)非整數(shù)基變量帶來的新的約束條件。為了轉(zhuǎn)為標(biāo)準(zhǔn)型，還需要給這個(gè)約束條件添加一個(gè)剩余變量x'：
Σj∈_j∈Jx_jS(A_ij) - x' = S(b_i)

3.python代碼

基本框架還是用分支定界法，每次求解完之后添加割平面的約束條件：

def add_new_restriction(matrix):
    new_column = np.zeros(matrix.shape[0]+1)
    new_line = np.zeros(matrix.shape[1])
    new_column[-1] = -1 #添加剩余變量
    new_line = matrix[1, :] #這里簡(jiǎn)單的使用第一行約束條件為基礎(chǔ)，生成新約束條件。
    for index in range(0, len(new_line)):
        number = np.array(new_line[index], dtype=float)
        if number.tolist().is_integer() == False:
            new_line[index] = math.floor(new_line[index])
    matrix = np.insert(matrix, matrix.shape[0], new_line, axis=0)
    matrix = np.insert(matrix, -1, new_column, axis=1)
    return matrix