整数规划
$$
\max C^T x\
\text{s.t.}Ax = b\
x \in Z^+
$$
例子：
1. 背包问题
记有 $n$ 个物品，第 $i$ 个物体大小为 $s_i$，价值为 $v_i$ ， 背包大小为 K ， $ x_i = 1 $ 表示选中该物体， $x_i = 0$ 则不选。背包问题的整数规划为：
$$
\max \sum^n_{i=1} v_ix_i \
\text{s.t.} \sum^n_{i=1} s_ix_i \le K\
x_i \in {0,1}
$$
2. 装箱问题
记箱子大小为 $C$, 有 $n$ 个物品，第 $i$ 个物体大小为 $a_i \le C$，至多用 $n$ 个箱子 ， $ y_i = 1 $ 表示使用该箱子，$y_i = 0$ 则不使用。$x_{ij} = 1$ 表示第 $i$ 个物体放入箱子$j$ 。装箱问题的整数规划为：
$$
\min \sum^n_{i=1} y_i \
\text{s.t.} \sum^n_{i=1} x_{ij}a_i \le C\cdot y_i\
\sum^n_{i=1} x_{ij} \ge 1\
x_{ij} \in {0,1}, y_i \in {0,1}
$$
3. TSP问题
旅行商问题：求图的最短哈密尔顿回路，记 $G=(V, E)$ 是一个带权重的有向图，顶点集$V=(v_1, v_2, …, v_{n})$, $c_{ij}$为每条边的权重，$x_{ij}$ 表示是否取从 $i$ 点到$j$ 点的边 (有向) 。从图中任一顶点 $v_i$ 出发，经图中所有其他顶点一次且只有一次，最后回到同一顶点 $v_i$ 的最短路径。这个问题有点复杂， 首先引入变量 $ u_1, …, u_n$ , 给出整数规划：
$$
\begin{align}
\min \sum_{(i,j)\in E} &c_{ij}x_{ij} \
\text{s.t.} \sum_{j=1}^n x_{ij} &= 1, \forall j \in V \
\sum_{i=1}^n x_{ij} &= 1, \forall i\in V \
u_i - u_j + (n-1) x_{ij}&\le n-2, 2\le i,j \le n, i\neq j\
x_{ij} &\in{0,1}
\end{align}
$$
前两个约束表示对于每个点，出度和入度均为 1， 即每个点都经过一次。但这是不够的：考虑多圈的情况也满足每个点经过一次。因此引入第三个约束条件，我们需要证明：1）多圈的情况不满足这个约束；2）任意哈密尔顿回路满足约束
1）当出现多圈时，一定存在一个圈使第一个点 $v_1$ 不在圈中，设这个圈上有 $K$ 个点, $v_{a_1},…,v_{a_K}, v_{a_1}$ 依次连接。相关的约束为：
$$
u_{a_1} - u_{a_2} +(n-1)x_{a_1a_2} \le n-2\
u_{a_2} - u_{a_3} +(n-1)x_{a_2a_3} \le n-2\
…\
u_{a_{K-1}} - u_{a_K} +(n-1)x_{a_{K-1}a_K} \le n-2\
u_{a_K} - u_{a_1} +(n-1)x_{a_Ka_1} \le n-2\
$$
由于不含 $v_1$ 点，故对每条边约束均成立，且$x_{ij} = 1$，累加， ${u}$ 项抵消，得到$(n-1) K \le (n-2)K$ ,矛盾。故多圈时不存在满足条件的 $u$ ，无可行解。
2）对于哈密尔顿回路，圈中一定包含点 $v_1$，设点 $v_1, v_{a_2},…,v_{a_n}, v_1$ 依次连接，取变量为
$$
u_1 = 1 \quad (其实这个值可以任取，等于1好看:)\
u_{a_i} = i, i = 2,…,n\
x_{1,a_1}=x_{a_1,a_2} = …=x_{a_n,1} = 1
$$
可以检验这是一个可行解。
搜到了另一个方法，容易理解但是计算量会大很多，记录一下：
$$
\min \sum_{(i,j)\in E} c_{ij}x_{ij} \\text{s.t.} \sum_{j=1}^n x_{ij} = 1, \forall j \in V \\sum_{i=1}^n x_{ij} = 1, \forall i\in V \
\sum_{i\in S,j\in S}x_{ij} \le |S|-1,\forall S\subsetneq V, |S|>1\
x_{ij} \in{0,1}
$$
第三个约束表示不存在任何点集的真子集构成圈，即不可能出现多圈。但是约束的个数很多。
4. 最小覆盖与最大匹配问题（无权重）
最小覆盖问题：求最少的顶点集，使每条边至少有一个顶点在集合中。设有 $n$ 个点，$ x_i = 1 $ 表示选中该点， $x_i = 0$ 则不选。$$E = {(i,j)\vert 存在点i到j的边}$$ 为边集。整数规划为：
$$
\min \sum^n_{i=1} x_i \\text{s.t.} x_i + x_j \ge 1 ,\forall(i,j)\in E \ x_{ij} \in {0,1}
$$
最大匹配问题： 求最大的边集，使每个顶点最多是集合中的一条边的顶点。$$E = {(i,j)\vert 存在点i到j的边}$$ 为边集，$ y_e = 1 $ 表示选中该边， $y_e = 0$ 则不选。$V$ 为点集。整数规划为：
$$
\max\limits_{e \in E} y_e \ \text{s.t.} \sum_{i\in e}y_e \le 1\ y_e \in {0, 1}
$$
为什么要放在一起写呢？当然是因为他们两个有关系 : )
两个问题的变量 $x$ 都满足 $x \in {0,1}$ , 这里考虑两步放缩：
- 将 $x \in {0,1}$ 放缩为 $x \in (0,1)$
- 将 $x \in (0,1)$ 放缩为 $x \ge 0$
首先说明在任何情况下对于两个问题第二步放缩都是自然的：
- 对于最小覆盖问题，若最优解存在 $x_{ij}>1$ ，将其减小到 1，可以看出约束条件依然满足 ( $x>0$ )且目标函数值减小。
- 对于最大匹配问题，显然不存在 $y_e >1 $ 。
而对于第一步放缩，可以证明当图为二分图时，最优解一定在整数点(即0, 1)时取得(证明见下)
我们将两个问题的整数规划放缩为
最小覆盖：
$$
\min \sum^n_{i=1} x_i \\text{s.t.} x_i + x_j \ge 1 ,\forall(i,j)\in E \ x_{ij} > 0
$$
最大匹配：
$$
\max\limits_{e \in E} y_e \ \text{s.t.} \sum_{i\in e}y_e \le 1\ y_e > 0
$$
根据之前的知识， 我们发现两者互为对偶 !
因此，根据对偶定理，对于二分图而言，最小覆盖问题与最大匹配问题是可以相互转换的，它们最优解相等。而对于其他图，由于最优解不一定是整数解，在整数规划中无法使用强对偶定理。
求解
$$
\max C^T x\
Ax = b\
x \in Z^+
$$
转换为线性规划问题
$$
\max C^T x\
Ax = b \
x \ge 0
$$
1. $A$ 是全幺模矩阵
证明：当$A$ 时全幺模矩阵时，极点是整数，因此线性规划最优解是整数解，问题解决
全幺模矩阵： 任何非奇异子方阵是单位模矩阵。 ( 任何子阵的行列式为0、1或-1 )
回忆用单纯形法解线性规划，最终解为 $x_B = A_B^{-1}b$，若 $A_B^{-1}$ 和 $b$ 的元素都是整数，最优解也是整数。在整数规划中， $b$ 自然的是整数。若 $A$ 是全幺模矩阵，可以证明列交换后依然是全幺模矩阵，因此 $$\vert A_B\vert = 1$$，可以得到 $$A_B^{-1} = A_B^*/\vert A_B\vert $$ ， $$A_B^{-1}$$ 元素也都是整数。于是，该线性规划最优解是整数解。
为什么行列交换不会改变全幺模的性质？其实很简单，对于一个全幺模矩阵，任意子方针的行列式都可以看成一个元素乘以该元素的余子式，而行(列)交换只会改变一行(列)，且全幺模矩阵中元素只能为 0,1,-1，因此交换后的子方针的行列式依然为 0,1,-1。
这里介绍两个常见的全幺模矩阵：有向图的关联矩阵与二分图的关联矩阵。
有向图的关联矩阵：
使用数学归纳法证明：
k = 1：对于 $n = 1$ 的有向图，是全幺模矩阵。
k -> k+1：设对于任意有向图 $n \le k$ ，都是全幺模矩阵。对于任意有向图 $n = k + 1$ 的子方阵，根据关联矩阵的定义，每一列至多存在两个非 0 元素，且若存在，至多存在一个 1，一个 -1。
- 若该子方阵存在一列没有非 0 元素，那么该子方阵的行列式取值为 0；
- 若该子方阵存在一列只有一个非 0 元素，由于该元素为 1 或 -1，该子方阵行列式的绝对值等于该元素余子式的绝对值。将原有向图去掉该元素对应的点和边后，这个余子阵可以看作是新的n-1个顶点有向图的子方阵，根据归纳假设，余子式的行列式为 0，1 或 -1，因此该子方阵的行列式取值为 0，1 或 -1；
- 若该子方阵的每一列都有两个非 0 元素，对行进行累加得到零向量，即行向量线性相关，行列式为0。
故对于 $n = k+1$ 个顶点的有向图的任意子方阵，其行列式的取值仍为 0，1 或 -1。
因此，有向图的关联矩阵是全幺模矩阵。
二分图的关联矩阵：
使用数学归纳法证明：
k = 1：对于 $n = 1$ 的二分图 ，是全幺模矩阵。
k -> k+1：设对于任意二分图 $n \le k$ ，都是全幺模矩阵。对于任意二分图 $n = k + 1$ 的子方阵，根据关联矩阵的定义，每一列至多存在两个非 0 元素，且都为 1 。
- 如果该子方阵存在一列没有非 0 元素，那么该子方阵的行列式取值为 0；
- 如果该子方阵存在一列只有一个非 0 元素，由于该元素为 1，那么该子方阵行列式的绝对值等于该元素余子式的绝对值。将原二分图去掉该元素对应的点和边后，这个余子阵可以看作是新二分图的子方阵（二分图的子图仍然是二分图）。根据归纳假设，余子式的行列式为 0，1 或 -1，因此该子方阵的行列式取值为 0，1 或 -1；
- 如果该子方阵的每一列都有两个非 0 元素，设二分图可以被分为 $A$ 和 $B$ 两个集合，根据关联矩阵与二分图的定义，将集合 $A$ 中的点对应的行相加，减去集合 $B$ 中的点对应的行，将会得到零向量，行向量线性相关，行列式为0。
对于 $n = k+1$ 个顶点的二分图的任意子方阵，其行列式的取值仍为 0，1 或 -1。
因此，二分图的关联矩阵是全幺模矩阵。
然而，全幺模矩阵条件很苛刻，我们还需要可以解决普通整数规划的方法：
2. 割平面法
我们用单纯性法求解线性规划时，可以得到解的典则形式：
$$
x_i + \sum_{k=m+1}^n \overline a_{ik} x_k= \overline b_{ik}
$$
对于最优解，取非基变量 $x_k = 0$, 因此，当 $\overline b_{ik} $ 为整数，最优解为整数。若 $\overline b_{ik}$ 不是整数：
非基变量 $x_k \ge 0$，可以得到：$x_i + \sum_{k=m+1}^n \lfloor\overline a_{ik}\rfloor x_k\le \overline b_{ik}$
由于我们在求解整数规划，最终得到的解均为整数，因此上述式子左边也为整数，可以得到：$x_i + \sum_{k=m+1}^n \lfloor\overline a_{ik} \rfloor x_k \le \lfloor\overline b_{ik}\rfloor$
用上述式子减去解的典则形式得到：
$$
\sum_{k=m+1}^n (\lfloor\overline a_{ik} \rfloor - \overline a_{ik} )x_k \le \lfloor\overline b_{ik}\rfloor - \overline b_{ik}
$$
作为新的约束添加到线性规划中。
一条约束都可以看成变量空间中的一个超平面，这个方法实际上就是在最优解附近割掉一部分空间，使得
- 不割掉任何整数可行解：这点可以从前面得到约束过程中得到，任何整数解都满足约束。
- 至少割掉目前的非整数最优解：对于最优解，非基变量为零，约束左边为0，右边为负数，故不满足
可以证明经过有限步迭代后可以得到最优整数解（我也没证出来 : (
这里有个小Tips：在添加约束时，如果变量系数均为整数，约束右边也可以取整数下界而不会影响整数解。
3. Branch & Bound (分枝定界法)
将整数规划转化为线性规划：
$$
\max c^Tx\
Ax = b\
x \ge 0
$$
得到线性规划的最优解为 $$ x^*_{LP}$$， 设 $$x^*_i = \overline b_i $$ 不是整数，在整数解中， $ x_i $ 一定满足下面两个条件中的一个：
$$
x_i \ge\lfloor\overline b_i\rfloor +1\
x_i \le\lfloor\overline b_i \rfloor
$$
对这两种情况进行分类，即分别将这两个约束加入线性规划中，分别求解。这就是分支：原线性规划分别添加上面两个约束得到两个线形规划问题。经过有限步分支计算后，我们可以得到一个整数最优解。（别问，问就不知道为什么有限
首先，对于最大化问题，子线性规划的最优解一定小于它的父线性规划，即对于线性规划而已，最优解逐渐减小。因此，我们提出两个定义：
- 下界： 目前整数规划最优解，即在得到的整数解的的最大值。它的意思是，继续分支计算希望得到的解应该优于下界：若低于，则已经得到更好的解，没有意义了。初始值为 $-\infty$
- 上界： 叶节点中线形规划最优解的最大值。它的意思是我们无法再得到更好的解：比它好的解都在树的上方，不满足整数条件。
为了减少计算理，我们可以进行剪枝：
- 明枝：得到了整数解，停止分支 (继续分支得到的解会差于当前整数解，不是最优)
- 死枝：没有可行解，添加约束就更没有可行解了
- 枯枝：线性规划的解小于下界，已经在其他分支找到了更好的解不需要再这个分支里继续找了。
当所有的分支都结束时，得到了最优的整数解（下界）
