整数规划

整数规划问题我们说三件事：解整数规划的分支定界法和割平面法，解 0-1 整数规划的隐枚举法。

分支定界法

对于当前问题 \(P\)，我们用 Simplex 搞出了最优解，现在我们从最优解的解向量中挑出一个不是整数的维度 \(x_i^*\)，把 \(x_i\le [x_i^*]\) 和 \(x_i\ge [x_i^*]+1\) 分别作为条件 \(p_1,p_2\)，得到两个新问题 \(P+\{p_1\},P+\{p_2\}\)，递归求解下去

割平面法

对于当前问题，还是用 Simplex 先求，找到某个不是整数的基变量 \(x_i\)，在 Simplex Tableau 中找到它对应的行，抽出那个约束等式，将所有系数对 \(1\) 取 fmod（即结果在 \([0,1)\) 内），等号改成大于等于号，作为新增约束条件，迭代求解下去

隐枚举法

先给出试探可行解，得到一个目标函数值 \(z^*\)，显然最优解满足 \(z\ge z^*\)，把这当作一个约束条件（过滤条件）

画表，每行是一个解向量，每列分别检查是否满足各约束条件（过滤条件排在前面）

同一行中，如果左边的条件不满足，那么右边也没必要检验了

将变量重排序使得过滤条件中系数单增，可以提供一些优化