1. Integer Linear Programming
1.1. 整数规划
整数规划 (IP) 本质上就是一个带有额外整数约束的线性规划 (LP) 。
我们知道，标准的线性规划处理的是连续变量，比如生产5.25吨的产品，或者投资3.7万元。但在现实世界中，很多决策是不能被分割的，比如你不能雇佣3.5个员工，也不能建造0.7座工厂。整数规划就是为了解决这类问题而生的。
它的通用数学形式如下： $$\begin{array}{rl}\min_{x}&c^\top x\\mathrm{s.t.}&Ax=b,x\geq0\&x_i\in\mathbb{Z},\forall i\in J\subseteq{1,2,\ldots,n}\end{array}$$
- $\min_xc^\top x$: 这是目标函数。和标准LP一样，我们希望最小化（或最大化）一个关于决策变量 $x$ 的线性表达式。比如 $c$ 可以是成本向量，$x$ 是各项活动的水平，目标就是总成本最小。
- $\mathrm{s.t.~}Ax=b,x\geq0$: 这是线性约束。$A$ 是约束系数矩阵，$b$ 是资源或需求的限制。这部分也和LP完全一样，确保我们的决策在资源、技术、规则等限制条件内。
- $x_i\in\mathbb{Z},\forall i\in J\subseteq{1,2,...,n}$: 这是IP与LP最关键的区别整数约束。
根据整数变量的覆盖范围，IP可以分为两类：
- 纯整数规划 (Pure Integer Programming): 当 $J={1,2,...,n}$ 时，即所有决策变量都必须是整数 。例如，一个车辆调度问题，需要决定派出多少辆车，车的数量必须是整数。
- 混合整数规划 (Mixed Integer Programming): 当 $J$ 只是 ${1,2,...,n}$ 的一个真子集时，即部分变量是整数，部分变量是连续的 。这个在实际中非常常见。例如，一个投资决策问题，既要决定是否投资某个项目（一个0或1的整数决策），又要决定给这个项目投资多少钱（一个连续的金额）。
1.2. 二元整数规划 (Binary IP)
这是整数规划中一个极其重要且应用广泛的子类，它的特殊之处在于，决策变量只能取两个值：0 或 1 。
数学公式：$$\begin{gathered}\min_xc^Tx\\mathrm{s.t.~}Ax=b\x_i\in{0,1},\forall i\in{1,2,...,n}\end{gathered}$$ 这里的关键约束是 $x_i\in{0,1}$ 。
二元变量（0-1变量）是优化建模的“瑞士军刀”。它们不仅仅代表“是/否”，还可以用来构建复杂的逻辑关系。例如：
- 选择其一: $x_1+x_2≤1$ 可以表示项目1和项目2最多只能选一个。
- 依赖关系: $x_1≤x_2$ 可以表示只有当项目2被选中时（$x_2=1$），项目1才有可能被选中（$x_1$可以为1）。
- 通过这些技巧，许多非线性和逻辑问题都可以被转化为二元整数规划问题来求解。
计算复杂度: 虽然IP只是比LP增加了一个看似简单的整数约束，但问题的求解难度却发生了天翻地覆的变化。
- 线性规划(LP)问题有高效的多项式时间算法（如内点法），可以快速求解。
- 而整数规划(IP)问题是NP-hard的。这意味着在最坏情况下，求解时间会随着问题规模的增长而指数级增加。找到最优解可能非常耗时。
尽管求解困难，但IP（特别是混合整数线性规划，MILP）是运筹学和管理科学中最成功的技术之一。得益于过去几十年算法（如分支定界法、切割平面法）和计算机算力的巨大进步，现在强大的商业求解器（如Gurobi, CPLEX）已经可以解决成千上万个变量和约束的实际问题。这使得它在人工智能领域的应用也越来越广泛，例如供应链优化、任务调度、路径规划、资源分配等。
1.3. 一个例子
![[Pasted image 20250916184123.png]]
这是一个二维的线性规划问题，其数学表达如下： $$\begin{gathered}\max_xx_1+x_2\\mathrm{s.t.~}3x_1+8x_2\leq24\3x_1-4x_2\leq6\end{gathered}$$ 对于只有两个变量的LP问题，我们可以很直观地在二维平面上将其可视化。这个LP问题的最优解是 $(x_1,x_2)=(4,3/2)$ ，即这个点在图形上是可行域的一个顶点。
![[Pasted image 20250916184323.png]]
现在，我们在上一页的线性规划问题基础上，增加整数约束条件。
问题的数学形式变为一个纯整数规划 (IP) 问题： $$\begin{gathered}\max_xx_1+x_2\\mathrm{s.t.~}3x_1+8x_2\leq24\3x_1-4x_2\leq6\x_1,x_2\geq0\x_1,x_2\in\mathbb{Z}\end{gathered}$$ 那么这个问题就发生了很大的变化：
可行域的改变:
- 之前LP问题的可行域是整个橙色多边形区域。
- 现在IP问题的可行域不再是连续的区域，而是一系列离散的、孤立的整数点，这些点必须位于原先的橙色多边形内部或边界上。图中的橙色竖条可以理解为在每个整数 $x_1$ 的取值上，所有可能的整数 $x_2$ 组成的点集。
通过检验这些离散的整数点，可以发现能使目标函数 $x_1+x_2$ 达到最大值的点不止一个。这道题就有两个最优解：$(x_1,x_2)=(2,2)$ 和 $(x_1,x_2)=(3,1)$ 。
因此，直接将LP松弛问题的最优解四舍五入，是不可靠的，甚至完全是错误的。
1.4. 匹配问题 (Matching Problem)
我们来假设一个很贴近生活的场景：
- 场景: 一个约会网站上有
n位女士和n位男士 。 - 数据: 每位女士
i都对每位男士j打了一个分数 $v_{ij}$，代表她对这位男士的喜好程度 。 - 目标: 网站需要设计一个一对一的匹配方案，使得所有成功匹配的组合的总分数最高 。
用数学语言解决这个问题，我们遵循建模的三个核心步骤：决策变量、目标函数、约束条件。
- (1) 决策变量 (Decision Variables)
首先要确定我们需要做什么决策。这里的核心决策是“谁和谁匹配”。我们引入一个
二元决策变量 $x_{ij}$ 来表示这个决策 ：
- 如果女士 $i$ 与男士 $j$ 匹配，则 $x_{ij}=1$。
- 如果他们不匹配，则 $x_{ij}=0$。
通过定义 $n×n$ 个这样的0-1变量，我们就能描述任何一种可能的匹配方案。
- (2) 目标函数 (Objective Function)
我们的目标是最大化总匹配分数。总分就是所有成功匹配对的分数之和。用数学公式表达就是 ： $$\max_x\sum_{i=1}^n\sum_{j=1}^nv_{ij}x_{ij}$$ 我们遍历所有可能的配对 $(i,j)$，将他们的匹配分数 $v_{ij}$ 乘以决策变量 $x_{ij}$。如果他们被匹配 ($x_{ij}=1$)，他们的分数 $v_{ij}$ 就被计入总和；如果他们没被匹配 ($x_{ij}=0$)，他们的分数就乘以0，对总和没有贡献。
- (3) 约束条件 (Constraints)
为了保证匹配方案是“合理”的（即一对一匹配），我们需要加上一些规则：
- 每位女士必须且只能匹配一位男士 。 $$\sum_{j=1}^nx_{ij}=1,\quad\forall i\in[n]$$ 这个公式的意思是，对于任意一位女士 $i$，把她和所有男士 $j$ 的匹配变量 $x_{ij}$ 加起来，总和必须等于1。这确保了她不会被匹配给多个男士，也不会单身 。
- 每位男士必须且只能匹配一位女士。 $$\sum_{i=1}^nx_{ij}=1,\quad\forall j\in[n]$$ 同理，对于任意一位男士 $j$，把他和所有女士 $i$ 的匹配变量 $x_{ij}$ 加起来，总和也必须等于1 。
- 变量的性质 $$x_{ij}\in{0,1}$$ 最后，我们必须明确规定决策变量 $x_{ij}$ 只能取0或1，这是一个二元整数规划问题 。
因此这个问题的标准数学规划格式： $$\begin{gathered}\max_{x\in\mathbb{R}^{n\times n}}\sum_{i=1}^n\sum_{j=1}^nv_{ij}x_{ij}\\mathrm{s.t.~}\sum_{j=1}^nx_{ij}=1,\quad\forall i\in[n]\\sum_{i=1}^nx_{ij}=1,\quad\forall j\in[n]\x_{ij}\in{0,1}\end{gathered}$$ 这是一个二元优化问题 (binary optimization problem) ，因为其决策变量只能在 {0, 1} 中取值。
对这个问题，如果是一个 $n×n$ 的匹配问题，总共有 $n!$ 个方案，所以暴力求解是不行的。
- 这个看似简单的模型，是运筹学中“指派问题 (Assignment Problem)”的标准形式，它的应用远不止于约会网站。
- 资源分配: 将
n个工人分配给n项任务，其中 vij 是工人i完成任务j的效率或收益。 - 设备调度: 将
n架飞机分配给n条航线。 - 计算机视觉: 在连续的视频帧中跟踪多个目标，需要将前一帧检测到的
n个目标匹配到后一帧的n个目标上。 - 这个模型是解决许多领域中“一对一”资源优化配置问题的通用框架。
1.5. 0-1背包问题 (The 0-1 Knapsack Problem)
- 场景: 你有一个容量（或体积）为
b的背包 。 - 物品: 有
n个不同的物品可供选择 。 - 属性: 每个物品
i都有两个属性：体积 $a_i$ 和价值 $c_i$ 。 - 目标: 你需要决定往背包里装哪些物品，才能在不超过背包总容量的前提下，使得包内物品的总价值最高 。
我们将这个问题转化为一个二元整数规划模型：
- (1) 决策变量 (Decision Variables)
我们的决策是“拿”还是“不拿”某个物品。因此，我们为每个物品 $i$ 定义一个二元变量 $x_i$：
- $x_i=1$ 表示选择物品
i。 - $x_i=0$ 表示不选择物品
i。 - (2) 目标函数 (Objective Function)
我们的目标是最大化总价值。总价值是所有被选中物品的价值之和： $$\max\sum_{i=1}^nc_ix_i$$
- (3) 约束条件 (Constraints)
决策必须满足两条规则：
- 容量约束: 所有被选中物品的总体积不能超过背包的容量
b。 $$\sum_{i=1}^na_ix_i\leq b$$ 这个不等式计算了所有被选中物品的总体积，并要求它小于或等于背包容量b。 - 二元约束: 决策变量必须是0或1 。 $$x_i\in{0,1}$$
因此，0-1背包问题的完整整数规划模型如下： $$\begin{gathered}\max\sum_{i=1}^nc_ix_i\\mathrm{s.t.~}\sum_{i=1}^na_ix_i\leq b,\quad x_i\in{0,1}\end{gathered}$$
问题的计算复杂度: 0-1背包问题是一个经典的 NP完全 (NP-complete) 问题。这意味着目前没有已知的算法可以在多项式时间内找到它的最优解。但是，它有一个著名的伪多项式时间解法，即动态规划 (Dynamic Programming)。从IP的角度来建模，为解决这类组合优化问题提供了一个更通用的框架。
背包问题的变种:
- 分数背包问题 (Fractional Knapsack): 物品可以被分割。这个问题要简单得多，可以用贪心算法解决：不断地优先选择“性价比”（单位体积的价值，$c_i/a_i$）最高的物品即可。这是一个典型的线性规划问题。
- 无界背包问题 (Unbounded Knapsack): 每种物品有无限多件。这个问题也可以用动态规划解决。
背包问题不仅仅是一个理论问题，它也是许多现实世界资源分配问题的一个抽象模型。
- 项目选择: 一个公司有有限的预算（背包容量），需要从一系列项目中选择一部分来投资，每个项目都有其成本（体积）和预期回报（价值）。
- 广告投放: 在有限的广告预算下，选择在哪些渠道投放广告，以达到最大的营销效果。
- 云资源分配: 将不同资源需求（CPU, RAM）和业务价值的应用（物品）部署到一台有固定硬件资源的服务器（背包）上。
1.6. 松弛 (Relaxation)
IP中，有需要回答的两个核心问题：
- 整数规划(IP)与线性规划(LP)有何不同？
- 如何求解IP？它有哪些性质？
计算复杂性：整数规划是NP-hard问题 。
- 知识补充:
- NP-hard是计算复杂性理论中的一个概念。它意味着，我们目前找不到一个“高效”的算法（即多项式时间算法）来保证解决所有规模的IP问题 。随着问题规模（例如变量或约束数量）的增加，找到最优解所需的时间可能会呈指数级增长。
- 这正是IP与LP最根本的区别。LP问题是“容易的”（可以在多项式时间内解决），而IP问题是“困难的”。仅仅增加一个整数约束，就导致了问题难度的质变。
一个直观的想法：松弛 (Relaxation)
既然直接求解IP很困难，一个自然而然的想法是：我们能不能从一个更简单的问题入手？这就引出了松弛的思想。
- 核心步骤:
- 放宽约束: 我们可以暂时忽略掉棘手的整数约束，先把IP问题当作一个普通的LP问题来处理 。
- 求解LP: 解决这个被简化了的LP问题，得到一个最优解 。
- 寻找整数解: 然后，我们寄希望于在这个LP最优解的“附近”，能找到一个好的、甚至是最好的整数解 。
- 专业术语:
- 这个通过移除整数约束而得到的LP问题，被称为原IP问题LP松弛 (LP relaxation) 。
这是一个“貌似合理”的方法，在某些情况下可能效果不错，但在另一些情况下则可能完全失败
1.7. LP与IP之间的关系
核心逻辑：更少的约束意味着更大的可行域
- 我们可以把LP松弛问题的可行域想象成一个公园的全部区域（比如我们之前例子里的橙色多边形）。
- 而IP问题的可行域，则是这个公园里一些离散的、特定的长椅（那些整数坐标点）。
- 显然，“所有长椅”的集合，是“整个公园”区域集合的子集。
- 当你寻找“公园里的最高点”（LP最优解）时，这个最高点的高度，必然会大于或等于“所有长椅中的最高点”（IP最优解）。这个简单的比喻可以帮助你理解下面的所有关系。
基于上述核心逻辑，我们可以得到以下四条性质：
- 对于最大化问题，LP松弛的最优值是IP最优值的“上界” (Upper Bound) 。
- 解读: 在“公园”里找到的最高点，一定会比在“长椅”上能找到的最高点要高，或者一样高 。因此，LP松弛解给我们的IP最优解设定了一个无法超越的“天花板”。
- 对于最小化问题，LP松弛的最优值是IP最优值的“下界” (Lower Bound) 。
- 解读: 同理，在“公园”里找到的最低点，一定会比在“长椅”上能找到的最低点要低，或者一样低 。这为IP最优解提供了一个“地板价”。
- 如果LP松弛问题无解 (infeasible)，那么IP问题也一定无解 。
- 解读: 如果连“公园”这块地都不存在（LP无解），那么你自然不可能在里面找到任何一张“长椅”（IP也无解） 。
- 如果LP松弛问题的最优解恰好是整数，那么这个解也是原IP问题的最优解 。
- 解读: 如果你发现“公园”里的最高点，正好本身就是一张“长椅”，那么它理所当然也是所有长椅中最高的那个 。这时，我们已经找到了IP问题的最优解，可以直接收工了 。
因此，求解LP松弛总能给我们提供有用的信息 。
- 具体来说，它给出了最优值的一个界限（上界或下界） 。
- 并且，如果我们运气好，它可能直接就给出了IP问题的最优解 。
需要注意的是，无论是四舍五入还是取整，LP问题得到的解一定是不可靠的，取整可能导致解不可行，即便取整后的解是可行的，它也可能远非最优解。
我们必须使用系统性的、专门为整数规划设计的算法，才能保证找到真正的最优解。这里我们所谓的最优解有如下前提
- 我们不能指望任何IP算法在最坏情况下是高效的 。
- 原因很简单：我们正在求解的是NP完全 (NP-complete) 问题 。
这意味着，接下来的算法，其目标不是像解决LP问题那样，追求在多项式时间内一蹴而就。相反，它们是一些聪明的、系统性的搜索策略，旨在尽可能地避免“暴力枚举”，从而在实践中（即使不是在最坏理论情况下）能够高效地找到最优解。
当今求解整数规划的两种最流行、最核心的方法：
- 分枝定界法 (Branch and Bound methods)
- 切割平面法 (Cutting plane methods)
这节课只讲切割平面法。
2. Cutting Plane Method
2.1. 一个直观的例子
2.1.1. 算法规则
![[Pasted image 20250916193636.png]]
我们首先给出一个整数规划问题： $$\begin{gathered}\max\quad x_1+x_2\\mathrm{s.t.}\quad-5x_1+4x_2\leq0\6x_1+2x_2\leq17\x_1,x_2\geq0,\quad\mathrm{integer}\end{gathered}$$
- 图中的网格点代表了所有可能的整数解，蓝色点是满足所有约束的可行整数点 。白色圆圈是不可行整数点 。
- 我们的目标是在所有蓝色点中，找到一个能使 $x_1+x_2$ 最大的点。通过逐一检查（或在图上画出目标函数等值线），我们可以发现点 (2, 2) 是最优解 。
- 在(2, 2)点，目标函数值为 2+2=4 。这个点在图上用红色菱形高亮标出 。
![[Pasted image 20250916193832.png]]
接下来，我们对上面的IP问题进行松弛操作。我们通过移除整数约束来获得LP松弛 。这就得到了如下的LP问题： $$\begin{gathered}\max\quad x_1+x_2\\mathrm{s.t.}\quad-5x_1+4x_2\leq0\6x_1+2x_2\leq17\x_1,x_2\geq0\end{gathered}$$ 移除整数约束后，可行域从离散的点集扩展为图中蓝色的连续多边形区域 。LP问题的最优解一定会在这个多边形的顶点上取到。在这里这个LP问题的最优解值为 4.5 。
切割平面法的思路非常直观。它不是通过“分枝”来搜索，而是通过不断地“雕刻”LP松弛的可行域，一步步逼近最终的整数解。迭代过程总结为四个清晰的步骤：
- 求解LP松弛问题 (Solve LP relaxation) 。
- 这是我们的出发点。
- 检查解: 如果LP的解是整数，那么它就是原IP问题的最优解，算法结束 。
- 生成并添加切割 (Add a cut): 如果LP的解不是整数，我们就需要生成并添加一条新的线性约束 。这条约束被称为“切割 (cut)” 。
- 切割必须满足两个黄金法则 :
- 它必须排除 (exclude) 当前的非整数LP最优解 。换句话说，当前的LP解会违反这个新约束。这是为了保证算法能继续前进，而不是卡在原地。
- 它必须保留 (keeping) 所有可行的整数点 。这是为了保证算法的正确性，我们不能在“雕刻”过程中意外地把最终答案给削掉了。
- 我们在这里有一个关键的理论保证：我们总能找到至少一个有效的切割 。
- 切割必须满足两个黄金法则 :
- 循环: 将新生成的切割约束添加到LP问题中，然后返回第一步 (Return to step 1) ，在一个被“切割”后变小了的新可行域上重新求解。
我们用图来理解这个过程：
![[Pasted image 20250916194036.png]]
- 第一步: 求解这个LP，我们得到最优解是红点 (2,2.5)。
- 第二步: 解不是整数，算法继续。
- 第三步: 我们需要找到一个“切割”。图中的几条橙色线 (valid cuts) 就是有效的切割示例。你可以看到，每一条橙色线都满足：
- 红点 (2,2.5) 在橙色线的“外面”（被切掉的一侧）。
- 所有蓝色可行整数点都在橙色线的“里面”（被保留的一侧）。
- 第四步: 我们会选择其中一条橙色线作为新的约束加入到问题中，然后带着这个新的约束回去重新求解。
通过这个过程，LP可行域会越来越小，越来越贴近那些整数点的“形状”，最终LP的最优解将会落在一个整数点上。
2.1.2. 第一次迭代
- 添加第一个“切割”
紧接上一步，我们知道LP松弛的最优解是 (2,2.5)。现在，我们需要引入一个切割，将其从可行域中排除。
图中选择的切割是这条非常直观的约束： $$x_2\leq2$$ 于是，我们把它加入到原有的约束集合中，形成了一个新的LP问题： $$\begin{gathered}\max\quad x_1+x_2\\mathrm{s.t.}\quad-5x_1+4x_2\leq0\6x_1+2x_2\leq17\x_{2}\leq2\x_1,x_2\geq0\end{gathered}$$ ![[Pasted image 20250916194248.png]]
这是一个有效的切割，因为它没有违反我们之前说的两条关于有效切割的原则。
2.1.3. 第二次迭代
- 我们加入了第一个切割 $x_2≤2$。如果我们去求解那个新的LP问题，我们会发现其最优解出现在 $x_2=2$ 和 $6x_1+2x_2=17$ 这两条线的交点上，解出来是 $(x_1,x_2)=(13/6,2)$，约等于 $(2.167,2)$。
- 这个解的 x1 坐标依然不是整数，所以算法不能停止，必须继续迭代。
- 我们需要一个新的切割来排除点 $(13/6,2)$。一个简单有效的切割就是 $x_1≤2$，因为它能排除 $x_1=2.167$，但不会排除任何 $x_1$ 坐标为0, 1, 2的可行整数点。
![[Pasted image 20250916194459.png]]
现在，我们的LP问题包含了两个由算法生成的切割 $$\begin{gathered}\max\quad x_1+x_2\\mathrm{s.t.}\quad-5x_1+4x_2\leq0\6x_1+2x_2\leq17\x_{2}\leq2\x_{1}\leq2\x_1,x_2\geq0\end{gathered}$$ LP的解是整数，因此它也必须是原始整数问题的最优解，所以迭代停止，我们走到了最优解。
2.2. Gomory Cut
2.2.1. 定义
Gomory切割是一种著名的、用于创建有效切割的方法，其首次为整数规划提供了一个有限终止的算法。
Gomory切割的四个核心特性：
- 易于计算 (Cuts are easy to compute)
- Gomory切割可以作为求解LP问题的单纯形法 (simplex algorithm) 的副产品来计算。
- 这里的思想非常精妙。当单纯形法求解完一个LP松弛问题并得到非整数解后，其最终的单纯形表 (simplex tableau) 包含了描述这个最优解的一系列线性方程。Gomory发现，可以从任意一个基变量值为小数的行中，仅利用其系数的小数部分，就能构造出一个有效的切割不等式。这个过程完全是代数操作，不需要进行复杂的几何分析，因此计算上非常便捷。这也解释了为什么现代的IP求解器通常都是在高效的LP求解器基础上构建的。
- 保证收敛 (Guaranteed to find the optimal solution)
- 使用Gomory切割的切割平面法，保证能在有限数量的切割之后找到最优解。
- 这是一个强大的理论保证。它意味着算法不会无限循环下去，最终一定能给出答案。这证明了该方法的完备性和正确性。
- 潜在的性能问题 (Finite number may be very very large)
- Gomory切割的缺陷：虽然步数有限，但这个“有限”的数字可能非常、非常大。
- 这是理论与实践的差距。在某些问题上，纯粹的Gomory切割法收敛速度可能很慢。原因是它生成的切割有时可能非常“浅”，每次只能切掉可行域很小的一块，导致需要成千上万次迭代才能达到整数解。这也促使了后续更多种类的切割（如覆盖不等式、团不等式等）以及混合算法（如分枝切割法）的发展。
- 应用广泛 (Widely used in commercial solvers)
- Gomory切割或其变体在商业求解器中被广泛使用。
- 知识补充: 尽管有收敛速度的问题，但Gomory切割依然是现代求解器工具箱中不可或缺的一环。在先进的分枝切割 (Branch-and-Cut) 框架中，求解器会在搜索树的节点上，尝试用Gomory切割等方法来加强LP松弛。如果能快速生成一些“深”的切割，就可以有效收紧界限，加速剪枝，从而提高整体求解效率。
2.2.2. 一个实际的例子
2.2.2.1. 求解LP问题
我们给出一个一个纯整数规划问题，注意这是一个最小化 (minimization) 问题： $$\begin{aligned}\min_{x\in\mathbb{Z}^2}\quad-3x_1-2x_2\\mathrm{s.t.}\quad2x_1+x_2\leq3\5x_1+4x_2\leq10\x_1,x_2\geq0\end{aligned}$$ 其中 $x\in\mathbb{Z}^2$ 明确指出决策变量 $x_1$ 和 $x_2$ 必须是整数。
Gomory切割推导的前提条件
这个例子所具备的，也是Gomory切割基础理论所需要的两个属性：
- 所有变量都是整数。
- 这意味着它是一个纯整数规划问题，而非混合整数规划。Gomory切割的原始形式是针对纯整数规划问题设计的。
- 所有约束中的系数都是整数。
- 在约束 $2x_1+x_2\leq3$ 和 $5x_1+4x_2\leq10$ 中，系数 2, 1, 5, 4 都是整数。
这两个前提至关重要，因为Gomory切割的推导过程依赖于对数字进行整数部分和分数部分的分解。如果原始问题不满足这两个条件，推导会变得更复杂。
基于以上两个前提，我们可以得出一个关键的推论：这个问题的松弛变量 (slack variables) 也必须是整数。
- 为了使用单纯形法，我们首先需要将不等式约束转换为等式约束。这是通过为每个“小于等于”的不等式引入一个非负的松弛变量来实现的。
- 对于 $2x_1+x_2\leq3$，我们引入 $x_3$，得到 $2x_1+x_2+x_3=3$。
- 对于 $5x_1+4x_2\leq10$，我们引入 $x_4$，得到 $5x_1+4x_2+x_4=10$。
很显然这两个松弛变量都是整数。
这个结论是Gomory切割代数推导的基石。推导过程将从单纯形表的某一行方程出发，而这个方程中既包含原始变量 $(x_1,x_2)$ ，也包含松弛变量 $(x_3,x_4)$。正是因为我们确信在一个可行的整数解中，所有这些变量都必须是整数，我们才能进行后续的数学变换来构造出有效的切割。
接下来，我们先用单纯形法求解LP松弛问题：
- 将问题标准化
我们的问题是 $min−3x_1−2x_2$。在应用最大化的单纯形法时，我们通常将其转化为等价的最大化问题 $max~3x_1+2x_2$。
- 我们引入松弛变量 $x_3$,$x_4$ 后，得到标准形式：
- $max~z=3x_1+2x_2$
- $s.t. 2x_1+x_2+x_3=3$
- $5x_1+4x_2+x_4=10$
- 第一个表格就是这个系统的矩阵表示。最后一行 $[−3,−2,0,0,0]$ 代表了目标函数 $z−3x_1−2x_2=0$。
第一个表格：初始状态
| Basis | x1 | x2 | x3 | x4 | SOL |
|-------|----|----|----|----|-----|
| x3 | 2 | 1 | 1 | 0 | 3 |
| x4 | 5 | 4 | 0 | 1 | 10 |
| | -3 | -2 | 0 | 0 | 0 |
第一次迭代 (Pivot on 2)
- 知识补充 (如何选择主元 Pivot?):
- 选择主元列: 我们看最后一行（目标函数行），找最负的数。这里是-3，它所在的 $x_1$ 列就是主元列。这表示，当前如果增加 $x_1$ 的值，目标函数 z 会增长得最快。$x_1$ 为进基变量。
- 选择主元行: 用SOL列的数，分别除以主元列对应位置的正数，进行“最小比率测试”：$min(3/2,10/5)=min(1.5,2)=1.5$。最小比率1.5出现在第一行（$x_3$ 所在行），所以第一行是主元行。$x_3$ 称为出基变量。
- 主元: 主元列和主元行的交叉点，即元素2，就是本次迭代的主元。
- 执行: 接下来，我们执行行变换，通过高斯消元，将主元位置变为1，主元列的其他位置变为0。
第一次迭代后
| Basis | x1 | x2 | x3 | x4 | SOL |
|-------|----|-----|-------|----|-----|
| x1 | 1 | 1/2 | 1/2 | 0 | 3/2 |
| x4 | 0 | 3/2 | -5/2 | 1 | 5/2 |
| | 0 |-1/2 | 3/2 | 0 | 9/2 |
现在 $x_1$ 进入了基变量，替换了 $x_3$。
第二次迭代 (Pivot on 3/2)
1. **选择主元列**: 看最后一行，唯一的负数是 -1/2，所以 $x_2$ 列是主元列，$x_2$ 是新的**进基变量**。
2. **选择主元行**: 再次进行最小比率测试：$min((3/2)/(1/2),(5/2)/(3/2))=min(3,5/3)$。最小比率是 5/3，出现在第二行（$x_4$ 所在行）。所以第二行是主元行，x_4 是**出基变量**。
3. **主元**: 本次迭代的主元是 **3/2**。
- 执行: 我们再次执行行变换。
最终状态 (最优解)
| Basis | x1 | x2 | x3 | x4 | SOL |
|-------|----|----|--------|--------|-------|
| x1 | 1 | 0 | 4/3 | -1/3 | 2/3 |
| x2 | 0 | 1 | -5/3 | 2/3 | 5/3 |
| | 0 | 0 | 2/3 | 1/3 | 16/3 |
找到最优解
- 终止条件: 我们观察最后一行，所有的系数（2/3,1/3）都大于等于0。这表示，无论再换入哪个非基变量（$x_3$或$x_4$），都无法再让目标函数值增大了。单纯形法达到最优，算法终止。
- 读取解:
- 基变量的值就显示在SOL列：$x_1$=2/3, $x_2$=5/3。
- 非基变量（$x_3,x_4$）的值默认为0。
- LP松弛的最优目标值显示在右下角：z=16/3。
2.2.2.2. 构造切割
步骤一：选择一个“源”方程
- 我们首先需要从最终的单纯形表中，选择一个基变量值为非整数的行。
- 上一页的解是 $x_1$=2/3, $x_2$=5/3。两个都是非整数，所以我们任选一行即可。
- 我们这里选择第一行，即对应基变量 $x_1$ 的那一行。该行所代表的方程是： $$x_1+\frac{4}{3}x_3-\frac{1}{3}x_4=\frac{2}{3}$$
步骤二：整数与非负部分的分离
这是Gomory切割的精髓所在。我们将方程中所有的系数和右边的常数，都分解成一个整数部分和一个非负小数部分。
- 对于正数很简单：$4/3=1+1/3$。
- 对于负数，我们需要保证小数部分非负。所以，$−1/3$ 不能分解为 $0−1/3$，而应该分解为：$−1/3=−1+2/3$。这里的整数部分是 $⌊−1/3⌋=−1$。
将原方程 $x_1+(\frac{4}{3})x_3+(-\frac{1}{3})x_4=\frac{2}{3}$ 进行分解: $$(1+0)x_1+(1+\frac{1}{3})x_3+(-1+\frac{2}{3})x_4=0+\frac{2}{3}$$ 现在，我们将所有整数系数的项移到一边，所有小数系数的项移到另一边，得到： $$(x_1+x_3-x_4)+(\frac{1}{3}x_3+\frac{2}{3}x_4)=\frac{2}{3}$$
步骤三：推导出不等式 $$\underbrace{(x_1+x_3-x_4)}\text{部分A}+\underbrace{(\frac{1}{3}x_3+\frac{2}{3}x_4)}\text{部分B}=\frac{2}{3}$$
- 分析A部分: 在任何一个可行的整数解中，我们知道所有的变量（包括原始变量 $x_1$ 和松弛变量 $x_3,x_4$）都必须是整数。因此，由整数加减组成的A部分也必须是一个整数。
- 分析B部分: 因为 $x_3,x_4≥0$，且它们的系数 $1/3,2/3$ 也都是非负的，所以B部分必须是一个非负数 (≥0)。
现在我们的方程可以解读为： 一个整数 + 一个非负数 = 2/3。
如果我们现在丢掉非负部分，那么剩下的整数部分必然小于或等于右边的值： $$x_1+x_3-x_4\leq\frac{2}{3}$$ 最后一步，也是最关键的一步: 我们已经知道 $(x_1+x_3−x_4)$ 必须是一个整数，同时它又必须小于或等于 2/3。那么，满足这个条件的最大整数是多少？是 0。
因此，我们可以把这个不等式变得更“紧”，得到最终的切割： $$x_1+x_3-x_4\leq0$$
步骤四：将切割加入问题
这个不等式 $x_1+x_3−x_4≤0$ 就是我们找到的第一个Gomory分数切割 (Gomory fractional cut)。
- 我们可以验证，它确实排除了当前的LP解 $(x_1,x_3,x_4)=(2/3,0,0)$，因为 $2/3+0−0=2/3$，不满足 $≤0$。
- 同时，它保留了所有可行的整数解（因为它是从整数解必须满足的性质推导出来的）。
最后，我们将这个新的约束添加到原始问题中，形成一个更强的新IP问题，准备进行下一轮的求解。
2.2.2.3. 新约束添加回单纯形表
步骤一：将切割转化为等式
- 我们上一页得到的Gomory切割是一个不等式：$x_1+x_3−x_4≤0$。
- 单纯形法在计算时处理的是等式。因此，我们需要引入一个新的松弛变量（这里记为 $x_5$），将不等式转化为等式： $$x_1+x_3-x_4+x_5=0$$ 这个新的松弛变量 $x_5$ 同样需要是非负整数。
步骤二：将新约束行添加到单纯形表
- 我们将上一页最终的、最优的单纯形表拿过来，然后在基变量下方直接追加一个新行，用来表示这个切割等式。
- 这个新行的基变量就是我们新引入的 $x_5$。
- 这就得到了第一个表格：
| Basis | x1 | x2 | x3 | x4 | x5 | SOL |
|---|---|---|---|---|---|---|
| x1 | 1 | 0 | 4/3 | -1/3 | 0 | 2/3 |
| x2 | 0 | 1 | -5/3 | 2/3 | 0 | 5/3 |
| x5 | 1 | 0 | 1 | -1 | 1 | 0 |
| 0 | 0 | 2/3 | 1/3 | 0 | 16/3 |
步骤三：通过高斯消元恢复表格的规范形式
- 在一个规范的单纯形表中，每个基变量（这里是 $x_1,x_2,x_5$）所对应的列，应该是一个单位矩阵的列向量（即在它自己的那一行是1，在其他所有行都是0）。
- 观察上表，基变量 $x_2$ 和 $x_5$ 的列都满足这个要求，但基变量 x1 的列是
[1, 0, 1, 0]，在 $x_5$ 那一行出现了一个不为0的数1，这破坏了规范形式。 - 执行高斯消元:
- 为了恢复规范形式，我们需要把 $x_1$ 列的那个多余的
1消成0。 - 我们可以通过一个简单的行变换来实现：新第三行 = 旧第三行 - 第一行。
- 执行了这个操作后的结果如下：
- 为了恢复规范形式，我们需要把 $x_1$ 列的那个多余的
| Basis | x1 | x2 | x3 | x4 | x5 | SOL |
|---|---|---|---|---|---|---|
| x1 | 1 | 0 | 4/3 | -1/3 | 0 | 2/3 |
| x2 | 0 | 1 | -5/3 | 2/3 | 0 | 5/3 |
| x5 | 0 | 0 | -1/3 | -2/3 | 1 | -2/3 |
| 0 | 0 | 2/3 | 1/3 | 0 | 16/3 |
现在我们得到了一个规范的、但状态特殊的单纯形表。
- 知识补充 (当前表格的状态):
- 原始不可行 (Primal Infeasible): 注意到
SOL列出现了负数（x5=−2/3）。由于所有变量都要求非负，这表示当前表格对应的基解是不可行的。这很正常，因为我们的切割已经把原来的最优解“切掉”了。 - 对偶可行 (Dual Feasible): 同时，观察最后一行（目标函数行），它的所有系数（2/3,1/3）都是非负的。在单纯形法中，这个状态被称为对偶可行。
- 原始不可行 (Primal Infeasible): 注意到
- 下一步:
- 当一个单纯形表处于“原始不可行”但“对偶可行”的状态时，我们不需要从头开始计算，而是可以直接使用对偶单纯形法 (Dual Simplex Method) 来进行优化，使其恢复到原始可行状态。
2.2.2.4. 对偶单纯形法求解新问题
我们从上一页得到的单纯形表开始。它的状态是：
- 原始不可行:
SOL列有负数 ($x_5$=−2/3)。 - 对偶可行: 目标函数行（最后一行）所有系数都非负。
(1) 选择主元行 (Pivot Row)
- 原始单纯形法是先选列，而对偶单纯形法先选行。
- 我们在
SOL列中寻找最负的数。这里只有 $x_5$=−2/3 是负数。 - 因此，$x_5$ 必须离开基变量，以恢复解的可行性。第3行（$x_5$所在行）被选为主元行。
(2) 选择主元列 (Pivot Column)
- 接下来，我们要在主元行中寻找负系数，这里是 $x_3$ 列的 -1/3 和 $x_4$ 列的 -2/3。
- 我们用目标函数行的对应系数，除以主元行对应系数的绝对值，来进行“比率测试”。 $$j^*=\arg\min_{j\mathrm{~s.t.~}a_{3j}<0}\left{\frac{c_j}{|a_{3j}|}\right}$$
- 对于 $j=3$ 也就是 $x_3$ 列，比率为 $\frac{2/3}{|-1/3|}=2$
- 对于 $j=4$ 也就是 $x_4$ 列， 比率为 $\frac{1/3}{|-2/3|}=1/2$
- 我们选择最小的比率，即 1/2。它对应的列是 $x_4$ 列。
- 因此，$x_4$ 列被选为主元列，$x_4$ 将进入基变量。
(3) 执行主元变换
- 主元就是主元行和主元列交叉处的元素 -2/3。
- 接下来，执行高斯消元行变换，结果如下：
| Basis | x1 | x2 | x3 | x4 | x5 | SOL |
|---|---|---|---|---|---|---|
| x1 | 1 | 0 | 3/2 | 0 | -1/2 | 1 |
| x2 | 0 | 1 | -2 | 0 | 1 | 1 |
| x4 | 0 | 0 | 1/2 | 1 | -3/2 | 1 |
| 0 | 0 | 1/2 | 0 | 1/2 | 5 |
- 状态分析:
- 原始可行:
SOL列的所有值 $(1, 1, 1)$ 现在都是非负的。 - 对偶可行: 目标函数行的所有系数 $(1/2, 0, 1/2)$ 也是非负的。
- 此时，表格既是原始可行又是对偶可行，说明我们已经找到了当前LP问题的最优解。
- 原始可行:
- 读取解:
- 基变量的值为 $x_1=1,x_2=1,x_4=1$。
- 目标函数最优值为 5。
- 原始决策变量的解是 $(x_1,x_2)=(1,1)$。
2.2.3. 普遍情况的 Gomory Cut 过程
- 准备工作：通用的最优单纯形表
推导的起点，是一个已经求解完毕的、最优的LP松弛问题的单纯形表。
- 基变量: $x_{i_1},...,x_{i_m}$ (表格左侧，构成了单位矩阵)。它们的解值是 $x_{i_1}^,...,x_{i_m}^$。
- 非基变量: $x_{j_1},...,x_{j_{n-m}}$ (表格顶部，它们在当前LP解中的值都为0)。
- 基本假设: 当前的LP最优解 $x_B^$ 不是一个纯整数解。我们从中选择任意一个值为非整数的基变量，记为 $x_r^$ (其中 r 是 $i_1,...,i_m$ 中的一个)。
- Gomory切割的通用推导
步骤一：写下来源方程
我们从单纯形表中 $x_r$ 所在的那一行，可以写出一个等式。这个等式对所有满足原始约束的解都成立： $$x_r+\sum_{j\in N}v_{rj}x_j=x_r^*$$ 这里的 $N$ 代表所有非基变量的索引集合，$v_{rj}$ 是表格中对应的系数。
步骤二：分解与重组 (Gomory的核心技巧)
我们将方程中的每个系数 $v_{rj}$ 和右侧的 $x_r^∗$ 都分解为其整数部分 $\lfloor\cdot\rfloor$ 和小数部分 $f$。 $$v_{rj}=\lfloor v_{rj}\rfloor+f_{rj}$$ $$x_r^=\lfloor x_r^\rfloor+f_r$$ 注意: 小数部分 $f$ 必须是非负的 ($f≥0$)。
代入原方程并重新整理，将整数部分和非整数部分分开： $$x_r+\sum_{j\in N}\lfloor v_{rj}\rfloor x_j-\lfloor x_r^*\rfloor=f_r-\sum_{j\in N}f_{rj}x_j$$
步骤三：运用整数性质（关键的逻辑飞跃）
现在，我们考虑一个任意的可行整数解。对于这样的解：
- 左边 (LHS): 所有的变量 $x_r,x_j$ 都必须是整数。所有的 $⌊⋅⌋$ 项本身也都是整数。所以，由一堆整数进行加减运算得到的LHS必然是一个整数。
- 右边 (RHS): 既然LHS是整数，那么RHS也必须是一个整数。
步骤四：运用非负性质
我们再来分析RHS: $f_r-\sum_{j\in N}f_{rj}x_j$
- $f_r$ 是 $x_r^∗$ 的小数部分。因为我们假设了 $x_r^∗$ 是非整数，所以 $0<f_r<1$。
- $f_{rj}$ 是系数 $v_{rj}$ 的非负小数部分，所以 $f_{rj}≥0$。
- $x_j$ 是非负变量，所以 $x_j≥0$。
- 因此，$∑f_{rj}x_j≥0$。
- 这意味着RHS的值 $f_r−(一个非负数)≤f_r$。因为 $f_r<1$，所以RHS的值必然严格小于1。
步骤五：合并推论，得出切割
现在我们得到了关于RHS的两个结论：
- 它必须是一个整数。
- 它必须严格小于1。
满足这两个条件的唯一可能是：这个整数小于或等于0。 所以，我们得出不等式： $$f_r-\sum_{j\in N}f_{rj}x_j\leq0$$ 整理一下，就得到了最终的 Gomory分数切割: $$\sum_{j\in N}f_{rj}x_j\geq f_r$$ 这等价于这个表达形式： $$\sum_{j\in N}(v_{rj}-\lfloor v_{rj}\rfloor)x_j\geq x_r^-\lfloor x_r^\rfloor$$ 这个推导过程非常优美，它仅仅利用了“解必须是整数”这一基本事实，就从一个等式中凭空创造出了一个所有整数解都必须满足、但当前LP解又不满足的新的线性约束。
2.2.4. 可行性证明
首先，我们知道Gomory分数切割最简洁的表达形式，通过定义 $v_{rj}=\lfloor v_{rj}\rfloor+f_{rj}$ 和 $x_r^=\lfloor x_r^\rfloor+f_r$ (其中f代表非负小数部分)，Gomory切割可以被写作： $$\sum_{j\in N}f_{rj}x_j\geq f_r$$ 下面我们证明这个切割不违反有效切割的条件：
法则一：不排除任何可行的整数解
- Gomory切割不会排除任何可行的整数解 ($x\in\mathcal{F}_{I}$)。
- 因为之前的整个推导过程，就是建立在“假设x是一个可行整数解”的前提之上的。我们从整数解必须满足的性质出发，推导出了这个不等式。因此，这个不等式是所有可行整数解的一个固有属性，它们必然会遵守这个约束，也就不可能被这个约束所“排除”。
法则二：排除当前的LP最优解
- Gomory切割会排除当前LP松弛问题的最优解 $x^∗$。
- 前提1: 我们只在基变量 $x_r^$ 为非整数时才生成切割。这意味着它的小数部分 $f_r=x_r^-\lfloor x_r^*\rfloor$ 必然大于0 ($f_r>0$)。
- 前提2: 在当前的LP最优解 $x^∗$ 中，所有非基变量的值都为0。即 $x_j^*=0,\forall j\in N$。
- 代入验证: 我们将LP最优解 $x^∗$ 代入Gomory切割不等式的左边 (LHS)： $$\sum_{j\in N}f_{rj}x_j^*=\sum_{j\in N}f_{rj}(0)=0$$
- 比较: 切割的左边在 $x^∗$ 点的值是0，而右边 $f_r$ 的值大于0。
- 结论: 我们得到 $0<f_r$，这意味着在 $x^∗$ 点，不等式 $∑f_{rj}x_j^∗≥f_r$ 不成立（因为 $0\not\geq f_r$）。因此，$x^∗$ 被这个切割成功地“排除”了。
最后两点总结了这两个属性在算法流程中的重要作用：
- 在不丢失任何（整数）解的情况下，缩小了可行域。这是对上述两个属性的完美概括。我们通过增加约束让问题变得更“紧”，同时保证了最终答案一定还在我们考虑的范围之内。
- 它排除了当前的 $x^∗$ ，使得后续的LP求解不会再找到这个解。这一点确保了算法的前进性。如果不排除当前的解，那么下一次迭代求解LP时，我们还会得到完全相同的结果，算法就会陷入死循环。通过“切掉”当前的非整数解，我们迫使单纯形法在下一次迭代中去寻找一个新的、不同的最优解。