整数规划

\[ \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$, 因此，当 $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} \]

作为新的约束添加到线性规划中。

一条约束都可以看成变量空间中的一个超平面，这个方法实际上就是在最优解附近割掉一部分空间，使得