割平面简单来说，就是添加约束条件。 Cuts are constraints added to a model to restrict (cut away) noninteger solutions that would otherwise be solutions of the continuous relaxation. The addition of cuts usually reduces the number of branches needed to solve a MIP.

在使用分支定界法时，我们一般是首先尝试添加各种割平面后看能不能求出整数解，如果不行再分支。这种方法叫做Branch and Cut。 首先介绍一些基本的cut方法：

剪枝方法分为对约束形式有要求的特殊剪枝以及通用的剪枝：

在分支定界算法中，添加的x≤floor[xs]和x≥ceil[xs]便是两个用来割平面的约束条件，floor[x]和ceil[x]之间的整个可行域在对x进行分支的过程中被切割掉了，称为disjunctive cuts。

Gomory的思想是将等式两边系数的小数部分拿出来做成新的约束，主要适用于纯整数规划。 假设 a x = b , x ∈ Z ax= b,x \in Z ax=b,x∈Z，则一定有 ⌊ a ⌋ x ≤ ⌊ b ⌋ \lfloor a\rfloor x\le \lfloor b\rfloor ⌊a⌋x≤⌊b⌋，然后两者相减，得到： f a x ≥ f b f_ax\ge f_b fa​x≥fb​；反过来有 y + ⌈ a ⌉ x ≥ ⌈ b ⌉ y+\lceil a\rceil x\ge \lceil b\rceil y+⌈a⌉x≥⌈b⌉，然后两者相减，得到： ( 1 − f a ) x ≥ 1 − f b (1-f_a)x\ge 1-f_b (1−fa​)x≥1−fb​。下面是个例子：

Gomory可以与其他方法组合使用。假设整数规划的线性松弛问题求解结果中有一个基变量 y = b y=b y=b不是整数，对应约束： y + Σ a j x j + Σ a k x k = b y+\Sigma a_jx_j+\Sigma a_kx_k=b y+Σaj​xj​+Σak​xk​=b 令： y + Σ ⌊ a j ⌋ x j + Σ ⌈ a k ⌉ x k = t y+\Sigma \lfloor a_j\rfloor x_j+\Sigma \lceil a_k\rceil x_k=t y+Σ⌊aj​⌋xj​+Σ⌈ak​⌉xk​=t（两边取整） 相减得到： Σ f a j x j − Σ ( 1 − f a k ) x k = b − t \Sigma f_{a_j}x_j-\Sigma (1-f_{a_k})x_k =b-t Σfaj​​xj​−Σ(1−fak​​)xk​=b−t disjunction，有 b − t ≥ 0 = > Σ f a j x j ≥ f b b-t\ge0=>\Sigma f_{a_j}x_j \ge f_b b−t≥0=>Σfaj​​xj​≥fb​， b − t < 0 = > Σ ( 1 − f a k ) x k ≥ 1 − f b b-t\Sigma (1-f_{a_k})x_k\ge 1-f_b b−tΣ(1−fak​​)xk​≥1−fb​ 合并得到 Σ f a j x j / f b + Σ ( 1 − f a k ) x k / ( 1 − f b ) ≥ max ⁡ { Σ f a j x j / f b , Σ ( 1 − f a k ) x k / ( 1 − f b ) } ≥ 1 \Sigma f_{a_j}x_j / f_b+\Sigma (1-f_{a_k})x_k/(1-f_b)\ge \max\{\Sigma f_{a_j}x_j / f_b,\Sigma (1-f_{a_k})x_k/(1-f_b)\}\ge1 Σfaj​​xj​/fb​+Σ(1−fak​​)xk​/(1−fb​)≥max{Σfaj​​xj​/fb​,Σ(1−fak​​)xk​/(1−fb​)}≥1 我们一般选取 f a j ≤ f b , f a k > f b f_{a_j}\le f_b,f_{a_k}>f_b faj​​≤fb​,fak​​>fb​，这样系数都小于1，约束比较紧。

在求解器中，一般只应用于根节点，挑选非整数最严重的一些变量（比如100个）添加gomory割平面到松弛问题上，然后重复两遍。

MIR cuts are generated by applying integer rounding on the coefficients of integer variables and the righthand side of a constraint. 核心思想是对整数变量与非整数变量>=0的交点进行distructive cut，然后连接cut的两个交点形成一个新的约束条件。

Mix integer rounding针对的是如下问题： 若 y ≤ b + x , y ∈ Z y\le b+x,y\in Z y≤b+x,y∈Z，我们可以添加cut： y ≤ ⌊ b ⌋ + x / ( 1 − f b ) y\le \lfloor b\rfloor+x/(1-f_b) y≤⌊b⌋+x/(1−fb​) 证明： 若 f x + f b < 1 f_x+f_bb，则把 C C C称为一个cover，cover cut为： σ C x j ≤ ∣ C ∣ − 1 \sigma_Cx_j\le |C|-1 σC​xj​≤∣C∣−1

cover cut也可以和其他方法进行结合，如下：

若一系列binary变量两两互斥，则可以生成clique cut，即： 若 x + y ≤ 1 , z + y ≤ 1 , x + z ≤ 1 x+y\le 1,z+y\le 1,x+z\le 1 x+y≤1,z+y≤1,x+z≤1 则 x + y + z ≤ 1 x+y+z\le 1 x+y+z≤1

无论是普通B&B中的对变量进行切分，还是B&C用约束条件的小数部分形成切分，切分条件对于原问题都是符合的，称为User cut。如果原问题还有一些隐含的额外约束可以作为cut，这些cut称为Lasy cut。 另外有种情况会使用到lasy cut，那就是有很多约束在最开始的时候是冗余的，这些约束会被放进一个pool中，时不时拿出来检查一下，如果被违反了，就加入约束中；如果有一段时间不违反了，再把它放回pool中。这样可以减少每次迭代的计算量

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