设 为单纯形与 的交集，定义其有效不等式为不等式 满足 。设 表示 的凸包，显然凸包的某个方向的任意边界都是一个有效不等式。

Chvatal-Gomory方法

Chvatal-Gomory方法（简称C-G方法）用于产生有效不等式。对于 , 考虑 , 先构造 的有效不等式，按照下面的步骤：

1. 选择权值向量 ，则 中的不等式的线性组合即为其有效不等式，为

其中 .

2. 根据下取整的性质以及 的正性，可以将上面有效不等式的系数做一个下取整，就有

3. 由于不等式的左侧是整数，因此就有

这就是 的一个有效不等式。

Gomory割平面法

在求出整数规划对应的线性松弛问题的解之后, 若线性松弛问题的最优解都是整数, 那么该最优解就是整数规划的最优解. 下面讨论最优解不全为整数的情况. Gomory 割平面法的思想是, 当得到的线性松弛问题的最优解不全是整数时, 想办法添加新的约束条件把该最优解排除, 而不把约束集中的原整数可行解排除(将最优解割掉).

Gomory割平面实际上就是有效不等式.

不妨设线性松弛问题的最优解的基在前 列, 即最优解可以写成 形式. 假设 不是整数, 首先由约束条件得: 由于 故 在要求解为整数的前提下, 上式左边向下取整之后不发生变化, 于是不等式两边同时向下取整就有 有 由于 则 而显然 不符合该 , 因为代入 之后左边为 而右边是一个大于 的数, 而对于原线性松弛问题的所有的整数可行解, 它们满足上述讨论的每一步的约束, 那么它们自然满足 于是约束 就称为 Gomory 割平面, 把它添加到原线性松弛问题中继续求解, 直到新得到的最优解所有的分量都为整数.

添加新的变量把 Gomory 割平面写成标准形式: 需要注意的是, 新添加的变量并不是我们想要的变量, 它无需是整数.

如果最优解不在前 列, 设最优解/基变量对应的下标集为 非基变量对应的下标集为 则 Gomory 割平面为: 其中 且满足 其中 为 IP 对应的线性松弛问题最优解中的不是整数的那个.

如果有多个解不是整数, 可以选择每次只添加一个割平面, 也可以将所有的割平面添加进去.

混合整数割

上文的割平面适用于严格的整数规划问题, 对于混合整数规划问题, 它的约束集一般表述为 , 此时的有效不等式/割平面要复杂一些. 记记号 .

定理1 设 , 它的有效不等式为 其中 , 同时该有效不等式为 的一个刻面.

定理2 设通过单纯形法求解混合整数线性规划的最优解时得到的单纯形表中描述整数基变量 的等式约束为 , 为整数非基变量下标集, 为实数非基变量的下标集, 那么 的有效不等式为 这是所谓的Gomory混合整数割(平面).

证明上述定理仅需要通过分类讨论, 取整函数的性质和不等式的基本性质即可, 要证明构造的有效不等式为凸包的刻面, 还需要找到 个仿射无关的点使有效不等式等号成立(在有效不等式平面上).

多面体理论与强有效不等式