cutting_plane

1. 割平面

目标： 切割松弛问题的可行域，加快搜索

要求：

1. 不能将原问题的可行域切掉
2. 需要切割松弛问题，如果可以切割松弛问题的最优解（非原问题可行解）最好

1.1. 分割的步骤

仅有batch bound的步骤

在分支前采用有效的不等式进行切割可行域

batch_cutting

1.2. 两种方法

1.2.1. Gomony cutting

1. 将所有系数向下取整

   成立：因为原可行解，在新的割中依然成立，不改变原解

2. 右值也向下取整

   成立：系数为整数，所以结果必须是整数

分割方法

1.2.1.1. 单纯行表使用

对于IP 问题，使用LP 问题求解的optimal 中有分数，所有不是最优解，且其中的分式中有分数

将其中的分数式子，使用Gomony cutting， 将这个分式转换为有效的割平面

单纯性表中有分数

image-20260205235803949

1.2.1.2. 增强割平面

对于 ax < b 如果ax 靠近b，那么约束更加有效，所以，可以抬升a， 对约束是有效的

当 x 前的系数 小于b 的时候， a 可以向上取整，实现约束的增强

1.2.2. cover cutting

增加一个不等式，对 部分约束的集合进行约束

覆盖约束适用范围

1.2.2.1. 解题步骤

1. 求一个系数 a 对 b的最大覆盖集合
2. 选择集合中的系数，构建约束 ,右值小于 |c|-1

集合约束示例

1.2.3. 割平面强度

1. 切割的维度越高越好

   

   切割维度

2. 切割越靠近conv() 越好

   

   image-20260206001044421